Collisions

  • Explain what collision (in the context of hashing) is and when it happens.

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: