Dealing with Collisions

Hash tables are awesome but are not without complications.

Continuing our thesaurus example: what happens if we want to add the following entry into our thesaurus?

First, the computer would hash the key:

DAB = 4 * 1 * 2 = 8

Then, it would try to add "pat" to our hash table’s cell 8:

Uh-oh. Cell 8 is already filled with "evil"—literally!

Trying to add data to a cell that is already filled is known as a collision. Fortunately, there are ways around it.

One classic approach for handling collisions is known as separate chaining. When a collision occurs, instead of placing a single value in the cell, it places in it a reference to an array.

Let’s look more carefully at a subsection of our hash table’s underlying data storage:

In our example, the computer wants to add "pat" to cell 8, but it already contains "evil". So it replaces the contents of cell 8 with an array, as shown here:

This array contains subarrays, where the first value is the word and the second value is its synonym.

Let’s walk through how a hash table lookup works in this case. Say we look up the following word:

The computer takes the following steps:

1. It hashes the key: DAB = 4 * 1 * 2 = 8.

2. It looks up cell 8. The computer takes note that cell 8 contains an array of arrays rather than a single value.

3. It searches through the array linearly, looking at index 0 of each subarray until it finds our key ("dab"). It then returns the value at index 1 of the correct subarray.

Let’s walk through these steps visually.

We hash DAB into 8, so the computer inspects that cell:

Because cell 8 contains an array of subarrays, we begin a linear search through each subarray, starting at the first one. We inspect index 0 of the first subarray:

It doesn’t contain the key we’re looking for ("dab"), so we move on to index 0 of the next subarray:

We found "dab", which would indicate that the value at index 1 of that subarray ("pat") is the value we’re looking for.

In a scenario where the computer hits upon a cell that references an array, its search can take some extra steps, as it needs to conduct a linear search within an array of multiple values. If somehow all of our data ended up within a single cell of our hash table, our hash table would be no better than an array. So, it actually turns out that the worst-case performance for a hash table lookup is O(N).

Because of this, it’s critical that a hash table is designed in such a way that it will have few collisions and, therefore, typically perform lookups in O(1) time rather than O(N) time.

Luckily, most programming languages implement hash tables and handle these details for us. However, by understanding how it all works under the hood, we can appreciate how hash tables eke out O(1) performance.

Let’s see how hash tables can be set up to avoid frequent collisions.