Double Hashing Algorithm

(334 Views)


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.

double hash PseudoCode

Image Reference: Geeks for Geeks

Double Hashing Algorithm Flowchart

double hashing algorithm flowchart

Image Reference: Geeks for Geeks

Double Hashing PseudoCode:

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:

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:

1. Hash Value = -1330324172 2. Hash Value = 1079230464 3. Hash Value = -482480461 4. Hash Value = 1637418694

Solution Worked 1 UpvotesUpvote

        

Solution Didn't Worked 1 DownvotesDownvote



Comments



Search

Play 2048 Game Online

Play Duckhunt Online

Need Help?

Looking for any Software or Tutorial?
Don't Worry, we will find it for you
Contact Now

Search Tags

    Double Hashing Pseudocode

    Algorithm for Double Hashing

    Double Hashing Flowchart

    Double Hashing in Java