CS 70

Collisions

  • Hedgehog speaking

    Just so I'm clear, can someone explain to me what the problem is?

  • Horse speaking

    Here's what I was wondering: What if we insert “cereal” into our table?

  • LHS Cow speaking

    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.

  • Horse speaking

    See? Bucket 3 already has “avocado” in it.

  • LHS Cow speaking

    Right, that's a collision. The hash function puts “cereal” and “avocado” in the same bucket.

  • Hedgehog speaking

    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

Brainstorm some possible ways we can handle collisions

  • LHS Cow speaking

    So what do you think? How can we put cereal in our table?

  • Duck speaking

    Can we put multiple keys in one bucket?

  • LHS Cow speaking

    Great idea! That strategy is called separate chaining.

  • RHS Cow speaking

    That will be our focus for today!

  • LHS Cow speaking

    Any others? Say we decide to only have one key per bucket.

  • Cat speaking

    Could we put it in a different bucket?

  • LHS Cow speaking

    Sure! That strategy is called open addressing.

  • RHS Cow speaking

    We'll study that in a different lesson.

  • LHS Cow speaking

    For now, let's dive into separate chaining!

(When logged in, completion status appears here.)