dictionary – Blog of Anders Rune Jensen

Hashtables in javascript

I was looking into some performance problems with knockout yesterday and starting digging into the code. In particular I was wondering why it would take their mapping plugin several seconds to wrap an array of 500 objects. Profiling lead me to look deeper into the code, and the following code stroke me as very strange:

Basically this is a hash implementation of only put and get operations using two arrays. I don’t think I need to tell you how bad the performance of this will be once you start adding lots of items 🙂

The reason why they didn’t just use an ordinary object to store their values, was that their keys were objects and not just simple strings or integers. I started wondering what other people did with this problem. There must be a library for this. And low an behold there was.

Then I started thinking, why don’t you just jsonize the object and then store that as the key in a plain js object. Both things should be really fast, since every new browser nowadays has a very fast JSON implementation.

With the 3 implementations in hand I did a simple benchmark. Generate 10.000 objects, store them in the hashtable with the object as a key. Followed by getting all the objects again.

Using Firefox 12: naive double array: 1370ms, json: 77ms, jshashtable: 170. Using Chrome 19 and IE9 the performance gap is very similar. Chrome is of course a tad faster.

Update: reran the benchmark using suggestions from Tim.

Code is available here.

One of the nice things about reading is that it enhances ones vocabulary, but only if one can learn the new words that one meets. I’ve always dreaded using a dictionary because one has to manually find the right page, and for them to contain all relevant words they need to be huge. When one is used to computers, this just seems terribly inefficient. Luckily now there are many online dictionaries. Sadly they don’t help very much when one is lying on the sofa or in bed and reading. This is where I think the kindle really shines. When reading a book on the kindle, one can instantly look up a new word without leaving the page. This alone is often compelling reason enough to buy it as an ebook than to buy it in paperback.

And if the book you’re reading is a physical book, you can still use the Oxford dictionary that comes with the device to look up words just by typing them in. And because the device is very power efficient, one never has to worry about it running out of power any time soon.

Read my review of the kindle for more information on the device.