Double Hashing: Collision Resolution in Hash Tables

In hash tables, mapping a large application key space into a finite table space of size $m$ makes collisions inevitable via the Pigeonhole Principle. When implementing hash tables using open addressing, all elements are stored directly within the table array itself—without auxiliary structures like linked lists or trees.

When a collision occurs, open addressing relies on a probing function to search for an unoccupied slot. While linear probing and quadratic probing offer straightforward collision resolution paths, both suffer from distinct clustering phenomena. Double hashing is an advanced open-addressing technique designed to mitigate these clustering problems by making the probe step size depend directly on the key.

---

Review: The Probing Mechanics of Open Addressing

In open addressing, inserting or querying a key $k$ uses a probe sequence defined by a probing function $P(k, i)$, where:

• $k$ is the key.
• $i$ is the attempt (probe) number, where $i \in \{0, 1, 2, \dots, m - 1\}$.
• $m$ is the total number of slots in the hash table.

The algorithm starts at attempt $i = 0$ (the primary slot). If that slot is occupied, the attempt index increments to $i = 1, 2, \dots$ until an empty slot is located or all $m$ slots have been evaluated.

flowchart TD
    A[Compute Primary Hash h1 of k] --> B{Is Slot Occupied?}
    B -- No --> C[Insert / Access Element]
    B -- Yes --> D[Increment Attempt i]
    D --> E[Compute Offset via Probing Function]
    E --> F[Check Next Slot]
    F --> B

1. Linear Probing

Linear probing inspects consecutive adjacent slots:

$P(k, i) = (h(k) + i) \pmod m$

• Mechanism: On collision, shift linearly by 1 to the right.
• Bottleneck: Primary Clustering. Contiguous blocks of occupied slots form rapidly. Any key that hashes into a cluster must probe through the entire run of occupied slots, extending the cluster further and degrading average lookup and insertion time from $O(1)$ to $O(n)$.

2. Quadratic Probing

Quadratic probing uses a non-linear polynomial step to break up contiguous runs:

$P(k, i) = (h(k) + c_1 i + c_2 i^2) \pmod m$

• Mechanism: The step size increases quadratically (e.g., $+1, +4, +9, +16, \dots$).
• Bottleneck: Secondary Clustering. While it prevents contiguous primary clusters, keys that hash to the exact same initial index ($h(k_1) = h(k_2)$) will trace identical probe sequences because the step progression depends strictly on $i$, not on the key itself.

---

The Core Architecture of Double Hashing

Double hashing eliminates secondary clustering by ensuring that the offset between probes is calculated by a second, independent hash function applied to the key.

Mathematical Formulation

$P(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod m$

Where:

• $h_1(k)$: Primary hash function, which yields the base slot index in the range $[0, m - 1]$.
• $h_2(k)$: Secondary hash function, which yields an offset (step size) in the range $[1, m - 1]$.
• $i$: The collision attempt counter ($0, 1, 2, \dots$).

Probe Sequence Progression

• Attempt 0: $P(k, 0) = h_1(k) \pmod m$ (Primary slot)
• Attempt 1: $P(k, 1) = (h_1(k) + 1 \cdot h_2(k)) \pmod m$
• Attempt 2: $P(k, 2) = (h_1(k) + 2 \cdot h_2(k)) \pmod m$
• Attempt $i$: $P(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod m$

Even if two distinct keys $k_1$ and $k_2$ collide on their primary hash ($h_1(k_1) = h_1(k_2)$), their secondary hashes ($h_2(k_1)$ and $h_2(k_2)$) will almost certainly differ. Consequently, their probe sequences diverge immediately, avoiding both primary and secondary clustering.

sequenceDiagram
    autonumber
    participant Hash as Key Space
    participant Table as Hash Table Index
    
    Note over Hash, Table: Keys k1 and k2 collide: h1(k1) == h1(k2)
    Hash->>Table: Primary Probe i=0 -> Slot h1(k1) [OCCUPIED]
    Note over Table: k1 evaluates h2(k1) = 3
    Note over Table: k2 evaluates h2(k2) = 7
    Hash->>Table: k1 Probe i=1 -> Slot (h1 + 1*3) mod m
    Hash->>Table: k2 Probe i=1 -> Slot (h1 + 1*7) mod m
    Note over Hash, Table: Probe sequences diverge completely

---

Design Criteria for the Secondary Hash Function

The choice of the secondary hash function $h_2(k)$ is critical to the correctness and performance of the hash table. It must adhere to three foundational constraints:

1. $h_2(k)$ Must Never Evaluate to Zero

If $h_2(k) = 0$ for any key:

$P(k, i) = (h_1(k) + i \cdot 0) \pmod m = h_1(k) \pmod m$

The step size collapses to zero. The probe sequence remains permanently stuck at the primary collision index, resulting in an infinite loop during insertion or lookup on collision.

Requirement: $h_2(k) \neq 0$ for all $k$.

2. $h_2(k)$ Must Be Coprime to the Table Size $m$

To ensure that every slot in the hash table can eventually be probed if the table becomes full, the sequence $\{i \cdot h_2(k) \pmod m\}$ must generate a complete permutation of the integers modulo $m$.

From number theory, $i \cdot h_2(k) \pmod m$ generates a complete cycle across all $m$ slots if and only if $\gcd(h_2(k), m) = 1$ ($h_2(k)$ and $m$ are relatively prime).

Two standard architectural strategies guarantee this:

1. Prime Table Size: Choose $m$ as a prime number. Then, define $h_2(k) = 1 + (k \pmod{m - 1})$ or $h_2(k) = R - (k \pmod R)$, where $R$ is a prime strictly smaller than $m$. Because $1 \le h_2(k) < m$, $\gcd(h_2(k), m) = 1$ is naturally satisfied.
2. Power-of-Two Table Size: If $m = 2^p$, design $h_2(k)$ to always produce an odd integer (e.g., $h_2(k) = 2 \cdot g(k) + 1$). Any odd integer is coprime to $2^p$.

3. Fast Computation and Quasi-Uniform Distribution

Because $h_2(k)$ is invoked whenever a collision occurs, its execution must be computationally lightweight. Cryptographic hash functions like SHA-256 or MD5 are excessively heavy for in-memory tables. Instead, fast non-cryptographic hashes (e.g., MurmurHash, xxHash) or simple integer arithmetic functions that distribute remainders uniformly are preferred.

---

Implementation Reference

The following Python implementation demonstrates double hashing with insertion, lookup, and deletion handling via tombstoning.

class DoubleHashTable:
    def __init__(self, capacity: int):
        # Capacity should ideally be a prime number
        self.capacity = capacity
        self.table = [None] * capacity
        self.size = 0
        self._TOMBSTONE = object()
        # Prime smaller than capacity for secondary hash
        self.prime_offset = self._find_smaller_prime(capacity)

    def _find_smaller_prime(self, n: int) -> int:
        for num in range(n - 1, 1, -1):
            if all(num % d != 0 for d in range(2, int(num**0.5) + 1)):
                return num
        return 3

    def _hash1(self, key: int) -> int:
        return key % self.capacity

    def _hash2(self, key: int) -> int:
        # Guarantees 1 <= step < prime_offset, ensuring step is never 0
        return self.prime_offset - (key % self.prime_offset)

    def insert(self, key: int, value: any) -> bool:
        if self.size >= self.capacity:
            raise OverflowError("Hash table is full")

        h1 = self._hash1(key)
        h2 = self._hash2(key)

        first_tombstone_idx = None

        for i in range(self.capacity):
            idx = (h1 + i * h2) % self.capacity
            slot = self.table[idx]

            if slot is None:
                target_idx = first_tombstone_idx if first_tombstone_idx is not None else idx
                self.table[target_idx] = (key, value)
                self.size += 1
                return True
            
            if slot is self._TOMBSTONE:
                if first_tombstone_idx is None:
                    first_tombstone_idx = idx
                continue

            # Update existing key
            if slot[0] == key:
                self.table[idx] = (key, value)
                return True

        if first_tombstone_idx is not None:
            self.table[first_tombstone_idx] = (key, value)
            self.size += 1
            return True

        return False

    def get(self, key: int):
        h1 = self._hash1(key)
        h2 = self._hash2(key)

        for i in range(self.capacity):
            idx = (h1 + i * h2) % self.capacity
            slot = self.table[idx]

            if slot is None:
                return None  # Key does not exist
            if slot is not self._TOMBSTONE and slot[0] == key:
                return slot[1]

        return None

---

Comparison: Collision Resolution Strategies

Attribute	Linear Probing	Quadratic Probing	Double Hashing
Formula	$(h_1(k) + i) \pmod m$	$(h_1(k) + c_1 i + c_2 i^2) \pmod m$	$(h_1(k) + i \cdot h_2(k)) \pmod m$
Offset Nature	Constant ($+1$)	Polynomial ($+i^2$)	Key-dependent ($+h_2(k)$)
Primary Clustering	High (forms long runs)	Eliminated	Eliminated
Secondary Clustering	High	Present (shared base hashes probe identically)	Eliminated
CPU Cache Locality	Excellent (linear array traversal)	Moderate (locality decreases with $i$)	Poor (random jumps across memory)
Compute Overhead	Minimal	Low	Moderate (evaluates two hash functions)

---

Trade-offs and Production Considerations

Advantages

1. Uniform Distribution: By incorporating $h_2(k)$, keys distribute uniformly across available slots, providing behavior closest to theoretical uniform hashing ($\{0, \dots, m-1\}^k$).
2. Short Probe Sequences: Because clustering is effectively eliminated, average probe counts remain lower than in linear or quadratic probing at high load factors (e.g., $\alpha > 0.7$).
3. Decoupled Key Paths: Colliding keys diverge instantly, avoiding the cascading probe traffic typical of linear schemes.

Disadvantages and Pitfalls

1. Loss of Cache Locality: High-performance systems benefit from CPU prefetching and cache lines when walking through memory linearly. Double hashing generates pseudorandom jumps across the array, causing frequent CPU L1/L2 cache misses.
2. Secondary Hash Overhead: Evaluating two independent hash calculations per collided key increases CPU cycles per operation relative to simple increment operations.
3. Deletions Require Tombstoning: Emptying a collided slot directly breaks the probe chain for keys inserted later. As with all open-addressing schemes, double hashing requires marker-based tombstoning, which necessitates periodic reorganization or rehashing when tombstone density increases.