Collisions

A collision occurs when more than one key is mapped to the same array index.

Collisions are rare events if they are the results of a well-designed hash function. But, they are inevitable as the set of possible keys is usually vastly larger than the capacity of the hash table (range of array indices).

Example

There are two main collision handling techniques:

Open addressing – locate the next available (open) position.
Chaining – store multiple entries in each position.

Resources

To understand why collisions are inevitable, consult these references:

Counting hash collisions with the birthday paradox by Matt Might.
The Pigeonhole Principle: how do pigeons and pigeonholes relate to cryptographic hashing functions and the number of hairs on people's heads? by SteemIt!
Hashtables, Pigeonholes, and Birthdays by Coding Horror!

CS226 Homepage

Collisions