Since your Hash Table has a fixed size (buckets) but the number of possible keys is infinite, at some point, two keys will map to the same slot. This is a collision. How you handle them determines the performance of your system.

Separate Chaining

Each bucket points to a linked list. Collisions are simply appended to the list.

Active Comparison

Appleh(k) = 2

Cherryh(k) = 2 (COLLISION)

Bucket 0

Bucket 1

Bucket 2

Apple

Cherry

Bucket 3

Bucket 4

Bucket 5

Bucket 6

Comparison Table

Separate ChainingO(1 + alpha)

+Safe - Table never 'fills up'+Simple to delete

Linear ProbingO(1)

+Memory efficient+Great cache locality

Quadratic ProbingO(1)

+Reduces primary clustering

Pro Tip: Load Factor ($\alpha$)

When using Open Addressing (Linear/Quadratic), performance plummets as the table fills up.

The rule of thumb: Once your table is 70% full ($\alpha \approx 0.7$), you MUST Resize (Rehash) the table into a larger array.

Double the Size: Typically move to the next Prime Number $m \times 2$.

Previous: Hash Functions Next: Hash Table Applications