Mainly , a collision is resolved by Probing (a collision resolving strategy) in Hashing.
Linear probing --> Rehash(key) = (n + 1) % table size .
Quadratic probing --> Rehash(key) = (n+k*k) % table size. [ k needs to be increased till the collision is resolved like k = 1,2,3,.. ]
Example - (Quadratic probing) --> table size = 11 & --> function = (key) mod 11
Keys --> 31 , 19 , 2 , 13 , 25 .
--> 31 mod 11 = 9
--> 19 mod 11 = 8
--> 2 mod 11 = 2
--> 13 mod 11 = 2 (already element there so collision) .
= (2 + 1*1) mod 11 = 3 (empty collision resolved) .
--> 25 mod 11 = 3 ( element already there collision) .
= (3 + 1*1) mod 11 = 4 (empty collision resolved).
0--> |
1--> |
2--> 2 |
3--> 13 |
4--> 25 |
5-->
|
6--> |
7--> |
8--> 19 |
9--> 31 |
10--> |
--> Others can be done in similar way .