Hashing - Open Addressing III: Double Hashing and Secondary Clustering

This chapter explores the phenomenon of Secondary Clustering, a key performance bottleneck that arises when using Quadratic Probing in open addressing. We will contrast secondary clustering with primary clustering, analyze why it occurs using concrete mathematical traces, and introduce Double Hashing as the definitive solution to eliminate redundant probe paths.

1. The Problem of Secondary Clustering

While Quadratic Probing successfully resolves the "continuous block" issue of Primary Clustering (by using non-linear step sizes), it introduces a different efficiency bottleneck known as Secondary Clustering.

Secondary clustering occurs when multiple keys hash to the same initial slot. Because the probe sequence formula relies solely on the initial hash value and the probe parameter $i^2$, any two keys that share the same initial hash index will traverse the exact same sequence of probe slots during collision resolution. This leads to redundant collision checks and significantly degrades insertion and search performance.

2. Mathematical Walkthrough of Secondary Clustering

To understand how secondary clustering manifests, let us trace the insertion of keys into a hash table of size $N = 10$ using Quadratic Probing.

The hash function formula for quadratic probing is:

Where:

• $h'(k) = k \pmod{10}$ (the primary hash function)
• $i$ is the probe attempt number ($i = 0, 1, 2, \dots$)

Step-by-Step Insertion of Key 34

1. Initial Probe ($i = 0$):

Status: Slot 4 is already occupied. Collision occurs.

2. Second Probe ($i = 1$):

Status: Slot 5 is already occupied. Collision occurs.

3. Third Probe ($i = 2$):

Status: Slot 8 is already occupied. Collision occurs.

4. Fourth Probe ($i = 3$):

Status: Slot 3 is already occupied. Collision occurs.

5. Fifth Probe ($i = 4$):

Status: Slot 0 is empty. Key 34 is stored at index 0.

Note on Calculation: The speaker calculates the probe index by adding the quadratic step directly to the key before applying the modulo operator: $(k + i^2) \pmod N$. This is mathematically equivalent to $( (k \pmod N) + i^2 ) \pmod N$ and yields the exact same probe sequence.

Step-by-Step Insertion of Key 24

Now, let us insert key 24. Note that $24 \pmod{10} = 4$, which is the exact same initial hash index as 34.

1. Initial Probe ($i = 0$): Index $24 \pmod{10} = 4$ (Collision)
2. Second Probe ($i = 1$): Index $(24 + 1) \pmod{10} = 5$ (Collision)
3. Third Probe ($i = 2$): Index $(24 + 4) \pmod{10} = 8$ (Collision)
4. Fourth Probe ($i = 3$): Index $(24 + 9) \pmod{10} = 3$ (Collision)
5. Fifth Probe ($i = 4$): Index $(24 + 16) \pmod{10} = 0$ (Collision)

Because 24 and 34 share the same initial hash index, 24 is forced to trace the identical path of collisions before finding an open slot. This shared path traversal is the core of the secondary clustering problem.

3. Primary Clustering vs. Secondary Clustering

4. Introduction to Double Hashing

To resolve secondary clustering, we must ensure that keys hashing to the same initial index do not follow the same probe path.

Double Hashing achieves this by using a second, independent hash function to determine the step size for each key. This means the step size is no longer a fixed constant (as in Linear Probing) or a simple function of the probe attempt $i$ (as in Quadratic Probing); instead, the step size is dynamically computed based on the key itself.

5. Mathematical Formulation of Double Hashing

The probe sequence formula for Double Hashing is defined as:

Where:

• $k$ is the key to be hashed.
• $i$ is the probe attempt number ($i = 0, 1, 2, \dots$).
• $h_1(k)$ is the primary hash function, which determines the starting slot.
• $h_2(k)$ is the secondary hash function, which determines the step size.
• $N$ is the total size of the hash table.

Crucial Rule for $h_2(k)$: The secondary hash function $h_2(k)$ must never evaluate to $0$. If $h_2(k) = 0$, the step size becomes $0$, causing the algorithm to get stuck in an infinite loop on the initial collision slot $h_1(k)$.

6. Step-by-Step Execution of Double Hashing

Let us trace an insertion workflow using Double Hashing on a table of size $N = 10$.

Setup Functions

• Primary Hash Function: $h_1(k) = k \pmod 5$
• Secondary Hash Function: $h_2(k) = k \pmod 6$
• Combined Formula: $h(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod{10}$

Step 1: Insert Key 32

• For $i = 0$:

• Result: Slot 2 is empty. Store 32 at index 2.

Step 2: Insert Key 47

• For $i = 0$:

Status: Slot 2 is occupied by 32. Collision detected!

• For $i = 1$: We must calculate the step size using the secondary hash function $h_2(47)$:

Now, apply the double hashing formula:

• Result: Slot 7 is empty. Store 47 at index 7.

7. Why Double Hashing Eliminates Secondary Clustering

To see how Double Hashing solves secondary clustering, let us introduce a third key, 52, which hashes to the same initial index as 32 and 47.

• Primary Hash: $h_1(52) = 52 \pmod 5 = 2$ (Collision at slot 2)
• Secondary Hash (Step Size): $h_2(52) = 52 \pmod 6 = 4$

Now, let us calculate the next probe index for 52 at $i = 1$:

Comparison of Probe Paths

Even though 47 and 52 start at the exact same slot (2), they diverge immediately on the very first collision because their step sizes are different ($5$ and $4$, respectively). This personalized step calculation completely eliminates secondary clustering.

8. Summary and Key Takeaways

• Secondary Clustering Cause: It occurs in Quadratic Probing because the probe sequence is determined solely by the initial hash index. Keys with identical initial hashes trace identical probe paths.
• Primary vs. Secondary Clustering: Primary clustering forms a single localized block of occupied slots (Linear Probing), while secondary clustering creates identical search paths across non-contiguous slots (Quadratic Probing).
• Double Hashing Solution: It solves secondary clustering by using a second hash function $h_2(k)$ to compute a unique step size based on the key itself.
• Double Hashing Formula: $h(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod N$.
• The Non-Zero Rule: The secondary hash function $h_2(k)$ must never return $0$ to prevent infinite loops during collision resolution.
• Performance Benefit: By ensuring that keys with the same initial hash index diverge immediately upon collision, Double Hashing minimizes probe lengths and keeps insertion/lookup times close to $O(1)$.