Manjula Dube

To implement a hash table, we create a class.

The constructor contains an object in which we’re going to store the values, the length of the values, and the entire size of the hash table: meaning how many buckets the hash table contains. Somewhere in these buckets, we can store our data.

Next, before we can do anything else, we need to implement our hashing function. One example of a hashing function:

Let’s say we have the string “Hello” and we create a hash table with the size of 10. “Hello” has the size of 5, so 5 % 10 becomes 5! The string “Hello” is now stored in the bucket with hash 5. If later on, we want to see where the key/value pair with the key “Hello” has been stored, it would return the same hash as the length of “Hello” hasn’t changed, and neither has the size of the hash table!

To add a key/value pair, we first need to calculate the hash with the key provided. If this hash is brand new (meaning that no other key/value pair used it yet and it’s not in the values object), we initialize an empty object for that hash. Next, we check whether the hash has a property with the same key name! If that’s not the case, it means we will add a new key/value pair, and the length of the hash table grows. Lastly, we add the key/value pair to the right hash.

Searching in a hash table goes very fast. As with an array we have to go through all of the elements until we find it, with a hash table we simply get the index. This means that its runtime is constant, O(1).

First, we calculate the hash again. As the length of the string and the size of the hash table haven’t changed, the hash remains the same. Then, we check whether the hash is within the object, and whether that hash points to the key we’re looking for. If that’s the case, return the value that that pair stores, else nothing gets returned.