Hash Collision

Many key that goes into a hashing function can come out, that is map to the same integer.

• Example: $h(46)=2=h(12)$ if $h(k)=k$ mod $11$

Thus, we get collisions: that is when we want to insert $(k,v)$ into the table, but $T[h(k)]$ is already occupied.

Strategies

• Closed Hashing: Use some strategy to find another bucket in the table
• Open Hashing: Each bucket is actually a pointer to short linked list of records

We will look at strategies to resolve collisions!

Hashing with Chaining Probe Sequence Cuckoo Hashing