O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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:

images/chapter8/blazing_fast_lookup_with_hashes_Part4.png

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required