Double Hashing

Abstract

Double Hashing is an advanced Open Addressing strategy designed to eliminate Primary Clustering. By using a second hash function to determine the “skip” or offset, it ensures that keys which hash to the same initial index follow different probe sequences, leading to a more uniform distribution.

• Category: Open Addressing Strategy
• Stores: Internal key allocations distributed within a bounded flat array.
• Built on top of: Contiguous arrays.
• Typical use cases: Tables requiring maximum memory distribution with high lookups and zero external memory allocations.

---

Core Structure

Keys reside directly within the backing array. Rather than probing adjacent cells sequentially by a constant 1, collisions trigger a personalized step offset size generated by a secondary hash function:

$S(k,i)=(H_1(k)+i\cdot H_2(k))(\mathrm{mod}M)$

• $H_1(k)$: The primary hash function determining the starting position.
• $H_2(k)$: The secondary hash function determining the step size.
• Constraint: $H_2(k)$ must return a value greater than 0 and should ideally be relatively prime to the table size $M$ to ensure the probe sequence visits every slot in the array.

Key Idea

Even if two keys collide at the same initial index $H_1(k)$, their secondary hash $H_2(k)$ will likely be different, sending them along entirely distinct probe sequences across the array.

---

Data Structure Operations

Insert(k)

Calculates a primary index and a personalized jump offset, probing the array until an open slot, a tombstone, or a duplicate key is reached.

• Time Complexity: $O(1)$ average; $O(M)$ worst-case.

Algorithm 55 Double Hashing Insertion

procedure InsertDoubleHash($k, arr, m$)

$index \gets$ H1($k$)

$offset \gets$ H2($k$)

$start \gets index$

while $\text{true}$ do

if $arr[index] == k$ then

return $\text{false}$

if $arr[index] == \text{NULL or } arr[index] == \text{TOMBSTONE}$ then

$arr[index] \gets k$

return $\text{true}$

$index \gets (index + offset) \pmod m$

if $index == start$ then

EnlargeTable($arr$)

$index \gets$ H1($k$)

$offset \gets$ H2($k$)

$start \gets index$

---

Common Pitfalls

• Incompatible Table Sizes: Failing to verify that $H_2(k)$ is relatively prime to the table size $M$ can result in an incomplete search sequence that misses open slots despite the array having capacity.
• Zero Step Offset: Allowing $H_2(k)$ to output 0 causes an infinite self-looping stall on the same index during collision resolution.

---

Trade-offs Compared to Other Data Structures

Collision Resolution Method	Probe Sequence Mechanics	Probability of Clumping
Linear Probing	$(H_1(k)+i)(\mathrm{mod}M)$	High (Primary Clustering)
Double Hashing	$(H_1(k)+i\cdot H_2(k))(\mathrm{mod}M)$	Very Low
Random Hashing	$\text{PRNG}(k)\text{ sequence}$	Very Low

---

When to Reach for This Structure

Double Hashing is an Open Addressing strategy because keys are stored directly within the backing array. Reach for it when you want to eliminate primary clustering without incurring the execution overhead of tracking random number generator state updates.

---

Related Notes

• Open Addressing
• Closed Addressing