Hash Functions: A Quick Review

Under the hood, a hash table stores its data inside an array or similar structure. However, while an array usually inserts new data at its end, a hash table uses another approach in how it decides where to insert each piece of data. We covered this concept back in Volume 1, but here I’ll remind you of the most pertinent details and then take the discussion further.

To keep things simple, I’ll use examples of inserting integers into the hash table. (You can explore inserting strings, though, in the exercises of this chapter.) Also, although hash tables generally store key-value pairs, I’m going to keep my examples simple by making the key and value the same piece of data. That is, if I say that I’m inserting the integer 17 into the hash table, both the key and value will be 17.

Now, let’s work with an example hash table that uses an array of size 10 under the hood. This means we’re storing each piece of data into one of 10 slots:

To decide which slot each value will go in, a hash table uses something called a hash function. A hash function is a function that converts a value into some number, known as the hash code. When we insert a value into the hash table, the hash table computes that value’s hash code, and then inserts the value into the index that matches that hash code.

Let’s look at an example of a simple hash function that works as follows: we take the value we’re inserting and, assuming it’s an integer, add up the sum of all its digits to produce a hash code.

For example, say we want to insert the integer 402 into the hash table. The hash function takes the 402 and adds up its digits:

4+0+2=6

This produces 6 as the hash code. Because of this, we store the 402 at index 6:

Next, say we want to insert 513. The hash function transforms the 513 into the hash code:

5+1+3=9

Because we get a hash code of 9, we insert the 513 into index 9:

Running a value through a hash function is known as hashing the value. In short, hashing transforms a value into an integer—namely, the hash code.

The power of hash tables lies in the fact that the value itself determines where the value is going to be stored. And this is precisely why hash-table search takes just O(1) time. To search for the value 513 in the future, we run it through the hash function, get the hash code of 9, and immediately know that we can find 513 at index 9.

Now, there’s an itty-bitty problem with our proposed hash function. That is, say that we want to insert the value 183.

When we hash it, we get:

1+8+3=12

This means we’d store 183 in index 12. But there isn’t an index 12 in our example hash table; the highest available index is 9.

To fix this, we can add another detail to our hash function: if the hash code has more than one digit, we then add those digits until we produce a hash code that is only a single digit. So, in this case, we’d hash the hash code of 12:

1+2=3

So, we’d insert 183 at index 3 of the array: