Data Structures in JavaScript

http://blog.benoitvallon.com/category/data-structures-in-javascript/

by shawndumas • 10 years ago

147 24 10 years ago

blog.benoitvallon.com

drabiega• 10 years ago

It looks like this is a teaching exercise more than anything, but it should be noted that the implementations are not great. For instance, the set uses an array based implementation instead of hash based.

In JavaScript the hash based implementation is pretty trivial to write and some quick testing in node shows that it is dramatically faster.

Kinnard• 10 years ago

Could you share your test code?

vkjv• 10 years ago

Unless by "hash based" you mean just using `new Set()`, I'm not aware of a way to do this generically. Using a `{}` for this would only work for a set of strings and things that can be uniquely coerced into strings. Otherwise, looping over arrays is your only option.

Care to elaborate?

nkoren2• 10 years ago

Using a `{}` for this would only work for a set of strings and things that can be uniquely coerced into strings.

The code they use has the same limitation. It adds / removes / ensures the uniqueness of elements in the set by using Array.indexOf(...), which only works for strings and things that can be uniquely coerced into strings.

So, given this limitation, using an Object-based set would be vastly more performant.

mistercow• 10 years ago

You can do it the way a lot of libraries do where you require that anything you want in a set implement an interface for hashing and equality testing. Then you use an object with hashes for keys and arrays for values.

aaco• 10 years ago

Google Closure Library does this in goog.structs.Set with an interesting generic solution.

A string key for the underlying map is generated based on the data type of the element being added in the set. If you're adding an object into the set, the object is mutated so that it stores a unique ID. The object's unique ID is used to form the string key that will identify this object in the set.

Note how goog.structs.Set.getKey_ is used in the add() method: https://github.com/google/closure-library/blob/v20160125/clo...

This is how the library obtains the unique ID of an object: https://github.com/google/closure-library/blob/v20160125/clo...

ChrisDutrow• 10 years ago

Yeah, I thought that was strange to use a list for the set implementation too. Average set addition and search should be O(1) if using a hash table. O(n) is a problem. Glad they put that clearly at the top though.

tlb2• 10 years ago

And the Queue has an O(n) remove operation, because it just uses Array.unshift. There are plenty of implementations with O(1) remove, like http://code.stephenmorley.org/javascript/queues/

eastbayjake• 10 years ago

It seems like cheating to do a Hash Table using JavaScript objects, since it's basically giving you all the hashing magic for free. It'd be cool if the example actually used an array and a hash function -- even a black box one -- to show how collisions and lookups are handled. (When I've implemented Hash Tables in JavaScript in the past, I've also included functionality to rehash the entire table into a larger array as it gets more than 25-50% full... but can't remember off the top of my head what's the mathematically optimal point to rehash.)

masklinn• 10 years ago

When I've implemented Hash Tables in JavaScript in the past, I've also included functionality to rehash the entire table into a larger array as it gets more than 25-50% full... but can't remember off the top of my head what's the mathematically optimal point to rehash.

The load factor (entries/bucket before you resize) varies greatly depending on the hashmap's addressing and collision resolution. Robin-hood hashing allows ridiculously high open-addressing load factors for instance (above 0.9 on an open-addressing linear-probed map, an open-addressing hash table can't go beyond 1), meanwhile separate-chaining allows load factors way above 1 (buckets are sequences and conflicting entries are appended to the sequence)

gravypod3• 10 years ago

I've been toying around with the idea in my head of building a small OS kernel in Javascript. I'd use grub to boot into it, ductape [0] to start an os.js or something, and then just implement everything from there.

These data-structure implementations make me feel that, even though it is crazy, it might just work. This seems to have come out very clean and easy to implement.

[0] http://duktape.org/

woah• 10 years ago

But why?

gravypod3• 10 years ago

It would be simple to get anyone into OS development. The only easier language I can find to teach someone is Python, and that doesn't have such an easily portable runtime.

JavaScript is great because you can learn it in the afternoon and master it in a few years and has a nice subset of lisp-like features.

It would be a toy to prototype in. Easy to use, and easy to modify. Nothing serious.

d0m• 10 years ago

For me it'd be a great way to learn about OS with something I'm already really familiar with, and also something that I can easily hack on. I.e. Similar reasons why I much more prefer stumpwn to ratpoison.

kenOfYugen• 10 years ago

You should check out runtime.js [1] if you haven't. Instead of duktape it uses v8. I'd like to see an equivalent project using spider monkey so that C/C++ code could be compiled into efficient JS. Check out this speech if you haven't already: The Birth & Death of JavaScript [2]

[1] https://github.com/runtimejs/runtime [2] https://www.destroyallsoftware.com/talks/the-birth-and-death...

jestar_jokin• 10 years ago

Maybe implementing a virtual machine would be more suitable? You can practice a lot of the same essentials.

- Memory management can be simulated by have a fixed length array, representing your total RAM, and somehow marking index ranges as "reserved". - You can simulate some hardware devices by exposing browser capabilities. Each, you could print a character, by writing to a virtual port or register (actually implemented as an array), then later in your VM update loop, reading the values in the array, interpreting the instructions, and updating the DOM as approprite.

And all from the comfort of your browser!

You could check out some emulators that have been ported to JavaScript; these are simulating hardware like the NES, and have the capability to run operating systems.

Data Structures in JavaScript

Related Stories