Hashing

Hash Collision

First learned this at Mari, but I still don’t understand. Update: slowly understanding more now.

A hash collision occurs when different input elements map to the same bucket.

Collisions are actually more common than you intuitively think. See the Birthday Paradox $\to$ 99% chance even around 70 people

Unless you want to make a gazillion buckets, we need to make a hash function to reduce the Hash Collisions.

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

CS240