Double Hashing:
It is the technique which is used in open addressing. In this, we use two hash functions. The first function used, is similar to linear probing, table size or the "key-mod" but if the collision occurs, then we apply the second hash function.
Double Hashing :→
H1(key) = key mod table size
H2(key) = M – (key mod M) * M is a Prime number, where M is a prime number less than the table size.
There are two conditions which need to be considered.
1. The second hash function never evaluates to be 0.
2. All cells must be probed means it must be reachable to all cells.
For example, we have:
37, 90, 45, 22, 17, 49, 55.
Indexes |
Values |
0 |
90 |
1 |
17 |
2 |
22 |
3 |
|
4 |
|
5 |
45 |
6 |
55 |
7 |
37 |
8 |
|
9 |
49 |
37 % 10 = 7
90 % 10 = 0
45 % 10 = 5
22 % 10 = 2
17 % 10 = 7 (But since, 7th location is already occupied, we will apply our second hash function now)
H2(17) = 7 – 17 % 7 = 4 ( We chose 7 because the prime number smaller and less than the table size of 10 is 7)
So, we will move 17 from the original location of 7 to the four positions ahead, that is,
7+1= 8
8+1 = 9
9+1 = 0
0+1 = 1 (We are just moving 4 positions from the current position)
49 % 10 = 9
H2(55) = 7 – (55 % 7) = 7 – 6 = 1 ( So move position from 5th location to 6)