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

Get A Common-Sense Guide to Data Structures and Algorithms now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.