# Collision Resolution Strategies

Collision Resolution Strategies is the important topic of the Data structure. Moreover, Freestudy9 has all kind of important topic and information about the subject.

Collision resolution is the main problem in hashing.

If the element to be inserted mapped to the same location, where an element already inserted then we have a Collision Resolution Strategies and it must be resolved.

There are several strategies for Collision Resolution Strategies. The most commonly used are :

**Separate chaining**– used with open hashing**Open addressing**– used with closed hashing

**Separate chaining **

- In this strategy, a separate list of all elements mapped to the same value maintained.
- Separate chaining based on collision avoidance.
- If memory space is tight, separate chaining should avoid.
- Additional memory space for links wasted in storing an address of linked elements.
- Hashing function should ensure even distribution of elements among buckets; otherwise, the timing behavior of most operations on the hash table will deteriorate.

**Open Addressing **

Separate chaining requires additional memory space for pointers. Also, Open addressing hashing is an alternate method of handling collision.

So, In open addressing, if a collision occurs, alternate cells tried until an empty cell is found.

- Linear probing
- Quadratic probing
- Double hashing.

*Linear Probing *

*Linear Probing*

- In linear probing, whenever there is a collision, cells searched sequentially (with wraparound) for an empty cell.
- Also, 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.

- Linear probing is easy to implement but it suffers from “
**primary clustering**“ - When many keys mapped to the same location (clustering), linear probing will not distribute these keys evenly in the hash table. These keys will stored in a neighborhood of the location where they are mapped. Moreover, This will lead to clustering of keys around the point of collision

*Quadratic probing *

*Quadratic probing*

- One way of reducing “primary clustering” to use quadratic probing to resolve the collision.
- Suppose the “key” mapped to the location j and the cell j already occupied. So, In quadratic probing, the location j, (j+1), (j+4), (j+9), … examined to find the first empty cell where the key to insert.
- This table reduces primary clustering.
- It does not ensure that all cells in the table will be examined to find an empty cell. Thus, it may possible that key will not insert even if there an empty cell in the table.

*Double Hashing*

*Double Hashing*

- This method requires two hashing functions f1 (key) and f2 (key).
- The problem of clustering can easily handle through double hashing.
- Function f1 (key) known as primary hash function.
- In case the address obtained by f1 (key) is already occupied by a key, the function f2 (key) evaluated.
- Moreover, The second function f2 (key) used to compute the increment added to the address obtained by the first hash function f1 (key) in case of the collision.
- The search for an empty location made successively at the addresses f1 (key) + f2(key), f1 (key) + 2f2 (key), f1 (key) + 3f2(key),…

**Related** **Terms**

Data Structure, Hashing Functions, Hash Table Data Structure, Engineering Study.

## Leave a Reply