Collision Handling

A collision happens when two distinct keys hash to the same bucket. Since collisions are unavoidable, every hash table needs a strategy to store multiple keys in one slot.

The two main families are chaining and open addressing.

With separate chaining, each bucket holds a linked list of entries. On collision you simply append (or prepend) to that bucket's list.

• Buckets store list heads
• Lookups walk one short list