Friday, February 6th, 2009

True JavaScript Hash Table

Category: JavaScript

While it’s great that JavaScript has a built-in hash-like mechanism, but it is limited to string keys. Tim Down recently filled us in on his project to create a more flexible hash table:

I occasionally want a proper hash table in JavaScript, by which I mean
something that can map an arbitrary key object with another arbitrary
value object. JavaScript does this for string keys, but not for
objects. My googling found nothing except lots of people wrapping an
ordinary JavaScript object and calling it a hash table. So I’ve
implemented my own, only about three years after making this point
before
, minus the actual code.

It looks for methods called hashCode and equals on keys, much like
Java’s Hashtable. Implementing these methods on your objects is not
required but vastly improves performance, particularly on large hash
tables, and gives you control over which keys are considered equal.

The other advantage of jshashtable is that you can use it like a
normal JavaScript object with string keys and get a reliable list of
its properties using the keys() method, without worrying about
filtering out properties defined by objects further up the prototype
chain.

This code snippet illustrates what happens when you try to use a non-string key:

Regular JavaScript objects:

  1. var key1 = new Object();
  2. var key2 = new Object();
  3. var o = new Object();
  4. o[key1] = "First";
  5. o[key2] = "Second";
  6. alert( o[key1] ); // Alerts "Second", not "First" - both keys are
  7. stored under the key "[object Object]"

But, with jshashtable, behold:

  1. var key1 = new Object();
  2. var key2 = new Object();
  3. var h = new Hashtable();
  4. h.put(key1, "First");
  5. h.put(key2, "Second");
  6. alert( h.get(key1) ); // Alerts "First"
  7. alert( h.get(key2) ); // Alerts "Second"

Handy.

Posted by Ben Galbraith at 9:00 am
5 Comments

+++--
3.1 rating from 43 votes

5 Comments »

Comments feed TrackBack URI

That’s a useful tool, you might wish to compare/contrast/steal/emulate from Flex’s Dictionary which is built on a similar principle:

http://livedocs.adobe.com/flex/3/langref/flash/utils/Dictionary.html

Comment by robinberjon — February 6, 2009

WebReflection – jshashtable uses hash codes for speed and equals methods for flexibility, and has several useful methods that are standard in hash tables in other languages, making the implementation more complicated than Relator. The compressed version is around 4.5K, and I’m quite sure I could cut that down, though that wasn’t my main focus for this release. Fair point about indexOf though.

The nostrademon hash table only seems to deal with string keys and therefore doesn’t solve the problem jshashtable solves.

Comment by timdown — February 6, 2009

Tim, I see JS as the perfect “KISS Oriented Language”, specially because we have to deal with hundreds of libraries every day and bytes are precious (think about iPhone like limited devices, as example)

What we have here? A way to associate a value to another generic value … well, you need two synchronized stacks for this and nothing else. At least this is my point of view and that’s what Relator does :-)

Comment by WebReflection — February 9, 2009

Andrea, I see your point. Where bytes are absolutely crucial and you only need to associate a few objects with each other, I agree your Relator is likely to be more appropriate. However, at the risk of repeating myself, in some of the applications I build I genuinely need the performance and flexibility provided by the way a hash table works, and I’m not sure you’ve read and understood what it actually is before dismissing it so loftily as “a good work but maybe not that worthy”.

Comment by timdown — February 9, 2009

I read it and I know it, but other languages patterns are not always appropriated for JavaScript, specially on client side (for Rhino or Jaxer it is a nice project, for instance). As summary, I hope next release will be smaller :-)

Comment by WebReflection — February 9, 2009

Leave a comment

You must be logged in to post a comment.