Collision resolution is the main problem in hashing.
There are several strategies for collision resolution. The most commonly used are :
1. Separate chaining - used with open hashing
2. Open addressing - used with closed hashing
1. Separate chaining
- In this strategy, a separate list of all elements mapped to the same value is maintained.
- Separate chaining is based on collision avoidance.
- If memory space is tight, separate chaining should be avoided.
- Additional memory space for links is wasted in storing address of linked elements.
- Hashing function should ensure even distribution of elements among buckets; otherwise the timing behavior of most operations on hash table will deteriorate.
2. Open Addressing
- Separate chaining requires additional memory space for pointers. Open addressing hashing is an alternate method of handling collision.
- In open addressing, if a collision occurs, alternate cells are tried until an empty cell is found.
- Linear probing Quadratic probing Double hashing
a) Linear Probing
- In linear probing, whenever there is a collision, cells are searched sequentially (with wraparound) for an empty cell.
- Fig. shows the result of inserting keys {5,18,55,78,35,15} using the hash function (f(key)= key%10) and linear probing strategy.
