Hash Tables (Part 1)

Hashtables are one of the most important basic data structures in a web browser. But most people don’t understand much about them. Even though you will rarely be called upon to build your own hashtable from scratch, it’s useful to know a little about how they work, and what kind of problems they can solve.

A hashtable is an associative array that uses a hash function to map items to pseudo-random slots in an array. With a good hash function, a hashtable can give fast, O(1) access for key-value lookups.

OK, so that’s a bunch of computer-science gobbledygook, but what are hashtables actually good for? Lots of things. Say you want to create a fast mapping from names to particular values, for example the mapping from id attributes to elements that is used by document.getElementById. Well, a hash map is just the thing. You can build a table that quickly maps from a string to the corresponding DOM node.

You can also use hashtables to implement “sets”. Say you quickly want to check if a tag is one of the set of HTML inline elements, so you can parse correctly. You can use a hashtable to build a set that quickly lets you check if a tag name is one of these tags.

Finally, hashtables are good for caches. Sometimes when you do a complex computation to determine a value, you want to be sure you can do that same computation quickly a second time. So you use a hashtable to map from the inputs to the already computed output.

So that’s a little about what hashtables are good for. Stay tuned for our next exciting episode, which will cover different hashtable algorithms, and which ones let you make the fastest possible hashtable.