Collisions
Just so I'm clear, can someone explain to me what the problem is?
Here's what I was wondering: What if we insert “cereal” into our table?
Let's take a look…
Here's our table...
bucket | key |
---|---|
0 | |
1 | toast |
2 | bacon |
3 | avocado |
4 | pancakes |
5 | |
6 | cheese |
7 | sausage |
8 | steak |
9 |
Now let's insert cereal
:
The sum of the ASCII values is 99 + 101 + 114 + 101 + 97 + 108 = 620.
The hash value is (620 % 13) + (620 % 7) + (620 % 5) = 13.
So the bucket would be 13 % 10 = 3.
See? Bucket 3 already has “avocado” in it.
Right, that's a collision. The hash function puts “cereal” and “avocado” in the same bucket.
So what are we supposed to do? Find a better hash function?
In general, collisions are inevitable, however awkward they might be to deal with.
Just as maintaining balance was the core problem for binary-search trees, resolving collisions is the core problem for hash tables!
Collision Resolution Strategies
So what do you think? How can we put cereal in our table?
Can we put multiple keys in one bucket?
Great idea! That strategy is called separate chaining.
That will be our focus for today!
Any others? Say we decide to only have one key per bucket.
Could we put it in a different bucket?
Sure! That strategy is called open addressing.
We'll study that in a different lesson.
For now, let's dive into separate chaining!
(When logged in, completion status appears here.)