A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

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?

thesaurus["dab"] = "pat"

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