The Hash Function

Restricting the Key Size #

In the last lesson, we learned that an array could be used to implement a hash table in C++. A key is used to map a value on 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.

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. We can increase the array size by increasing their capacity exponentially, but the process still takes O(n) time because it will copy all the elements into the new array.

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.

What Hash Functions Do? #

Have a look at the following illustration to get the analogy of a hash function.