Collision in Hashing | Collision Resolution techniques

Collision in Hashing

When the hash value of a key maps to an already occupied Bucket of the hash table, it is called , Collision.


Collision Resolution techniques

Collision resolution techniques are the techniques used for resloving or handling the collision.

1. Seperate chaining (Open Hashing)- 

-> This technique creates a linked list to the slot for which collision occurs.

-> The new key is then inserted in the linked list.

-> These linked lists to the slots appear like chains.

-> That is why, this technique is called as Seperate Chaining.


2. Open addressing (Closed Hashing)- 

Unlike seperate chaining, All the keys are stored inside the hash table.
no key is stored outside the hash table.

Techniques are used for open addressing are:


1. Linear probing -  In linear probing,

1. When collision occurs, we linearly probe for the next bucket.

2. we keep probing until an empty bucket is found.


Advantage - It is easy to compute.

Dis-Advantages - 

1. The main problem with linear probing is clustering.
2. many consecutive elements from groups.
3. Then, it takes time to search an element or to find an empty bucket.


2. Quadratic probing -

1. when collision occurs, we probe for i²th bucket in  i^th

  iteration.
2. we keep probing until an empty bucket is found.



3. Double Hashing-  In double hashing,

1. We use another hash function hash2(x) and look for i * hash2(x) bucket in ith iteration.

2. It requires more computation time as two hash functions need to be computed.

       50,700,76,85,92,73,101     ( n%7 )

Conclusions-

-> Linear Probing has the best cache performance but suffers from clustering.

-> Quadratic probing lies between the two in terms of cache performance and clustering.


-> Double caching has poor cache performance but no clustering.