A Common-Sense Guide to Data Structures and Algorithms

Dealing with Collisions

Of course, hash tables are not without their complications.

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

thesaurus["dab"] = "pat"

First, the computer would hash the key:

DAB = 4 * 1 * 2 = 8

And 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 ...