Objects and Hash Tables in Javascript

When constructing solutions as a programmer, time complexity should always be taken into consideration; the necessity of optimization is a simple fact of life. This process can be incredibly frustrating, especially for those who are just beginning to consider computation speed. However, there are structures for organizing and processing data which are significantly more efficient than the available alternatives. These structures represent a necessary tool for successful developers, one of which we will be exploring together: hash tables.

Array lookups have a linear time complexity, as searching for a particular element takes, in the worst case, looping through each element. If you are not familiar with time complexity and are curious, read this. Imagine if the user of our program was a data management firm, processing domestic information to better understand the relationship between rates of cancer and proximity to a large body of fresh water. They are planning on running several million inputs through our function, storing a profile for each individual with information on their health status and number of miles from a lake. How can these profiles be stored such that retrieving them is instantaneous (O(1): constant time)? We may implement a hash table, a particular data structure which utilizes javascript objects to create a numerically indexed structure to store key-value pairs (known as tuples). I’ll say that again: hash tables store key-value pairs an numerical indices generated by running the key through a hashing function.

The hashing function is the part of the program which takes a key and converts it to a number which will be the index at which to store it. Visualize a box, into which you empty a container of tuples, or key-value pairs. Output is an array storing the key-value pair at a numeric index. The manner by which the index is assigned varies contingent on the hash function’s implementation. Not all hashing functions are equal, some are better at creating an even distribution of key-value pairs. If every tuple is placed in the same index, then the time complexity will be comparable to that of a plain array, linear.

Here we initialize the HashTable class:

Hashing function example implementation below originally posted here:

The second part of hash table implementation is the logic dedicated to handling collisions, or the instances in which there are multiple values at a particular index, called the bucket. This is accomplished by looping through all tuples in the hash table’s index of interest to find the desired tuple.

There is a great deal of confusion regarding the comparison between objects and hash tables. This is much like an attempted comparison between apples and granny smith apples, one is a subset of the other with particular qualities. The advantages offered by hash tables include its ability to handle cases in which a key corresponds with a native object attribute and provides constant time lookup. Below is a retrieve method added to the prototype of our HashTable class with a constant lookup time on average:

It is hugely important as developers to understand what is happening in the black boxes used in our code in order to grow and implement ideas in new and creative ways. However, there is a data structure, bare objects, which offers the same advantages as a hash table in javascript without the tedious need for its complicated implementation. The workaround for this is to instantiate an object without any fall through context using the bare objects, introduced in ES5. In essence, the create method on the Object prototype allows for instantiation of a new object with the delegation chain specified. It follows that passing in null will instantiate an object with no native attributes. Read more about bare objects here.

There is an active debate in regards to whether javascript objects are all implemented as hash tables under the hood. The good news is, you don’t have to worry about that! Javascript abstracts unnecessary details in the pursuit of allowing design of more complex systems.

Keep coding!

Jacob