The Hash Function

This is the first building block of a hash table. Let's see how it works.

Restricting the Key Size

A key is used to map a value in the array, and the efficiency of a hash table depends on how a key is computed. At first glance, you may observe that we can directly use the indices as keys because each index is unique.

One Problem

The only problem is that the key would eventually exceed the size of the array and at every insertion, the array would need to be resized. Syntactically, we can easily increase array size in JavaScript, but as we learned before, the process still takes O(n) time at the back end.

One Solution

In order to limit the range of the keys to the boundaries of the array, we need a function that converts a large key into a smaller key. This is the job of the hash function.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.