Collision in data structure (specifically in hashing) is when two different keys are mapped to the same index (slot) of a hash table by the hash function.

What is collision in data structure?

  • In hashing, a hash function converts a key (like a number, string, or object) into an index of an array called a hash table.
  • A collision happens when two or more different keys produce the same hash value, so they want to occupy the same index in the table.
  • Collisions are unavoidable in practice because a hash table has a fixed number of indices, but the set of possible keys is usually much larger (pigeonhole principle).

Simple example

  • Suppose there is a hash table of size 10 and a hash function: h(key)=keymod 10h(key)=key\mod 10h(key)=keymod10.
  • Keys 15 and 25 both give 555 as the result, so they both try to go into index 5; that clash for index 5 is a collision.

Why collisions matter

  • Too many collisions slow down operations (search, insert, delete) because the program has to do extra work to find the correct element among multiple ones mapped to the same position.
  • Poorly handled collisions can break expected behavior (e.g., incorrect lookups or data loss if a new key overwrites an old one).

Collision resolution techniques

When collisions occur, data structures use special strategies to still store and retrieve everything correctly.

1. Chaining

  • Each index of the hash table stores a linked list (or some other dynamic structure) of all keys that hash to that index.
  • If several keys collide at index 5, they are all kept in the list at index 5 and are searched within that list when needed.

2. Open addressing

Instead of keeping multiple items in the same slot, the table searches for another empty slot according to a rule.

Common open addressing methods:

  • Linear probing : If index iii is occupied, try i+1,i+2,i+3,…i+1,i+2,i+3,\dots i+1,i+2,i+3,… (wrapping around) until an empty slot is found.
  • Quadratic probing : Try i+12,i+22,i+32,…i+1^2,i+2^2,i+3^2,\dots i+12,i+22,i+32,… away from the original index to reduce clustering.
  • Double hashing : Use a second hash function to decide the step size when probing for the next free slot.

3. Other ideas (less common in basic courses)

  • Probabilistic hashing / caching approaches sometimes replace the old record or drop the new one on collision, trading accuracy for speed and simplicity.
  • Advanced hash table designs and cryptographic hash functions aim to reduce collision probability, but can never completely remove collisions.

Mini FAQ style “Quick Scoop”

  • Q: Is collision an error?
    Not exactly; it is a normal event in hash tables that needs proper handling through collision resolution techniques.
  • Q: Can collisions be avoided completely?
    Only with very special “perfect hashing” for a known, limited key set; in general applications, collisions are inevitable.
  • Q: Where do collisions appear in real life code?
    In dictionaries/maps, sets, caches, symbol tables in compilers, and many library hash table implementations in modern programming languages.

TL;DR:
In data structures (especially hash tables), a collision occurs when two or more different keys produce the same hash value and try to use the same index; collisions are normal and are managed using techniques like chaining and open addressing so that data can still be stored and retrieved efficiently.

Information gathered from public forums or data available on the internet and portrayed here.