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