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

Get A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.