What is Double Hashing Algorithm?
Double hashing is a collision resolving technique in Open Addressed Hash tables. Double hashing uses the idea of applying a second hash function to key when a collision occurs. Double Hashing is one of the best techniques available for open addressing because the permutations produced have many of the characteristics of randomly chosen permutations.
Image Reference: Geeks for Geeks
Double Hashing Algorithm Flowchart
Image Reference: Geeks for Geeks
Double Hashing PseudoCode:
<![CDATA[1. Insert 76.
h1(76) = 76 mod 11 = 10
h2(76) = 76 mod 9 = 4
The h (76, 0) = (10 + 0 x 4) mod 11
= 10 mod 11 = 10
Where T [10] is free, so insert key 76 at this place.
2. Insert 26.
h1(26) = 26 mod 11 = 4
h2(26) = 26 mod 9 = 8
Where h (26, 0) = (4 + 0 x 8) mod 11
= 4 mod 11 = 4
Where T [4] is free, so insert key 26 at this place.
3. Insert 37.
h1(37) = 37 mod 11 = 4
h2(37) = 37 mod 9 = 1
Where h (37, 0) = (4 + 0 x 1) mod 11 = 4 mod 11 = 4
As T [4] is not free, the next probe sequence is
h (37, 1) = (4 + 1 x 1) mod 11 = 5 mod 11 = 5
Where T [5] is free, so insert key 37 at this place.
4. Insert 59.
h1(59) = 59 mod 11 = 4
h2(59) = 59 mod 9 = 5
Where h (59, 0) = (4 + 0 x 5) mod 11 = 4 mod 11 = 4
Since, the value of T [4] is not free, the next probe sequence is
Where h (59, 1) = (4 + 1 x 5) mod 11 = 9 mod 11 = 9
Since T [9] is free, so insert key 59 at this place.
5. Insert 21.
h1(21) = 21 mod 11 = 10
h2(21) = 21 mod 9 = 3
Where h (21, 0) = (10 + 0 x 3) mod 11 = 10 mod 11 = 10
Since T [10] is not free, the next probe sequence is
Where h (21, 1) = (10 + 1 x 3) mod 11 = 13 mod 11 = 2
Since T [2] is free, so insert key 21 at this place.
6. Insert 65.
h1(65) = 65 mod 11 = 10
h2(65) = 65 mod 9 = 2
Where h (65, 0) = (10 + 0 x 2) mod 11 = 10 mod 11 = 10
Since T [10] is not free, the next probe sequence is
Where h (65, 1) = (10 + 1 x 2) mod 11 = 12 mod 11 = 1
Since T [1] is free, so insert key 65 at this place.
Thus, after the insertion of all keys the final hash table is:
]]>
Double Hashing Implementation in Java:
<![CDATA[public class Double_hashCodeMethodExample1 {
public static void main(String[] args) {
Double d1 = new Double(0.78);
System.out.println("1. Hash Value = " +d1.hashCode());
Double d2= new Double(79.0);
System.out.println("\n2. Hash Value = " +d2.hashCode());
//passing decimal value
Double d3 = new Double(79.0001);
System.out.println("\n3. Hash Value = " +d3.hashCode());
//passing negative integer
Double d4 = new Double(-79.098);
System.out.println("\n4. Hash Value = " +d4.hashCode());
}
}
]]>
Output:
<![CDATA[ 1. Hash Value = -1330324172
2. Hash Value = 1079230464
3. Hash Value = -482480461
4. Hash Value = 1637418694]]>
1 Upvotes
2 Downvotes