Collisions
A collision occurs when more than one key is mapped to the same array index.
![](/img/22/hash08.png)
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).
![](/img/22/hash07.png)
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: