Double Hashing Collision Resolution

Double Hashing is an advanced open addressing technique for resolving collisions in hash tables.

It uses two hash functions to determine the probe sequence, making it more efficient than linear or quadratic probing because it avoids clustering.

How Double Hashing Works?

When a collision occurs at index h1(key), instead of just moving linearly or quadratically, we use a second hash function h2(key) to calculate the step size for probing.

Hash Functions Used

Table size = m (preferably a prime number)

Primary hash function

• h1(key) = k mod  m

Secondary hash function (must not be 0)

• h2(key) = R − ( key mod  R )

where R < m, and R is also a prime.

Probe Formula

Indexi = ( h1 (key) + i × h2(key) ) mod m

where i = 1, 2, 3.... is the probe number.

Example: Double Hashing Hashing Collision

Keys to insert: 19, 27, 36, 10, 64

Table size m = 7

Choose R = 5 for secondary hash

Step 1: Define Hash Functions

• h₁(key) = key % 7

Insert 19

• h1(19) = 19 % 7 = 5
• Check index 5 → empty → Insert at index 5

Insert 27

• h₁(27) = 27 % 7 = 6
• Index 6 → empty → Insert at index 6

Insert 36

• h₁(36) = 36 % 7 = 1
• Index 1 → empty → Insert at index 1

Insert 10

• h₁(10) = 10 % 7 = 3
• Index 3 → empty → Insert at index 3

Insert 64

• h₁(64) = 64 % 7 = 1 → Collision! (Already has 36)
• h₂(64) = 5 - (64 % 5) = 5 - 4 = 1
• Use probing: i = 1 → (1 + 1×1) % 7 = 2 → empty → Insert at index 2

Final Hash Table

Time and Space Complexity of Double Hashing

Double Hashing is a collision resolution technique under open addressing in hash tables. It uses two hash functions to compute probe sequences and minimises clustering.

Time Complexity

Space Complexity

O(n) where n is the size of the hash table. The table is pre-allocated with empty slots (no dynamic memory like chaining).

Advantages of Double Hashing

Minimizes clustering (especially primary and secondary)

Better distribution across table

Provides nearly uniform probing

Disadvantages of Double Hashing

More complex than linear/quadratic probing

Requires careful selection of R

If h2(key) returns 0, probe will not move

When to Use?

When high performance is needed with fewer collisions

In hash-based data structures requiring uniform distribution

Numerical Question for of Double Hashing

1. Insert the following keys using double hashing into a table of size 11 and Secondary hash R = 7. Keys {10, 22, 31, 4, 15, 28, 17, 88, 59, 3, 6, 12, 32}. Use the given hash functions and resolve collisions using double hashing.

1. Insert the following keys using Double Hashing into a table of size 23 with Secondary Hash R = 9. Keys: {5, 14, 27, 41, 52, 66, 70, 85, 90, 102, 111, 120, 133, 145, 151}
   • h1(key) = key mod  23
   • h2(key) = 9−(key mod  9)
2. Insert the following keys using Double Hashing into a table of size 13 and Secondary Hash R = 5. Keys: {25, 38, 44, 59, 77, 91, 33, 50, 67, 29, 81}
   • h₁(key) = key mod  13
   • h₂(key) = 5−(key mod  5)
3. Insert the following keys using Double Hashing into a table of size 17 with Secondary Hash R = 7. Keys: {10, 21, 35, 48, 62, 70, 81, 93, 104, 119, 131, 144}
   • h₁(key) = key mod  17
   • h₂(key) = 7−(key mod  7)
4. Insert the following keys using Double Hashing into a table of size 19 and Secondary Hash R = 11. Keys: {22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132}
   • h₁(key) = key mod  19
   • h₂(key) = 11−(key mod  11)