Closed Addressing: Separate Chaining with Linked Lists

This chapter explores the mechanics of collision resolution in hash tables. We begin by analyzing how Double Hashing mathematically eliminates the issue of secondary clustering. We then compare the four primary collision resolution strategies, evaluate their trade-offs, and examine why industry-standard containers—such as C++'s std::unordered_map—rely on Separate Chaining as their core internal implementation.

1. The Evolution of Collision Resolution

When multiple keys map to the same index in a hash table, a collision occurs. The strategy chosen to resolve these collisions dictates the performance, memory footprint, and complexity of the hash table.

Collision resolution strategies are broadly divided into two paradigms:

1. Open Addressing (Closed Hashing): All elements are stored directly within the hash table array. If a collision occurs, we probe alternative slots within the array according to a specific sequence.
2. Closed Addressing (Open Hashing / Separate Chaining): Each slot in the hash table array points to an auxiliary data structure (typically a linked list) that holds all keys hashing to that same index.

2. Resolving Secondary Clustering: Double Hashing

In Quadratic Probing, if two keys hash to the same initial index, they follow the exact same probe sequence. This phenomenon is known as Secondary Clustering.

Double Hashing resolves this by using a second, independent hash function to calculate the step size (probe increment). The probe sequence formula is:

Where:

• $k$ is the key.
• $i$ is the collision iteration step ($i = 0, 1, 2, \dots$).
• $h_1(k)$ is the primary hash function determining the starting index.
• $h_2(k)$ is the secondary hash function determining the step size.
• $m$ is the size of the hash table.

Because the step size $h_2(k)$ depends directly on the key $k$, two keys that share the same initial index $h_1(k)$ will have completely different step sizes. This causes their probe paths to diverge immediately, eliminating secondary clustering.

3. Step-by-Step Mathematical Walkthrough

Let us trace how Double Hashing handles collisions using the exact parameters and values from the lecture.

System Configuration

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

We will insert three keys that all collide at the same initial index: $47$, $52$, and $87$.

Step 1: Inserting Key $47$

1. Calculate Initial Slot ($i = 0$):

Index 2 is already occupied. 2. Calculate Next Slot ($i = 1$):

• Calculate step size: $h_2(47) = 47 \pmod 6 = 5$
• Apply combined formula:

3. Action: Insert key $47$ into Index 7.

Step 2: Inserting Key $52$

1. Calculate Initial Slot ($i = 0$):

Index 2 is occupied (Collision). 2. Calculate Next Slot ($i = 1$):

• Calculate step size: $h_2(52) = 52 \pmod 6 = 4$
• Apply combined formula:

3. Action: Insert key $52$ into Index 6.

Step 3: Inserting Key $87$

1. Calculate Initial Slot ($i = 0$):

Index 2 is occupied (Collision). 2. Calculate Next Slot ($i = 1$):

• Calculate step size: $h_2(87) = 87 \pmod 6 = 3$
• Apply combined formula:

3. Action: Insert key $87$ into Index 5.

Visualizing the Divergent Probe Paths

Even though all three keys ($47$, $52$, $87$) targeted Index 2 initially, their secondary hash functions calculated different step sizes, distributing them across the table without forming clusters:

4. The Trade-offs of Double Hashing

While Double Hashing provides excellent distribution and avoids both primary and secondary clustering, it introduces distinct engineering challenges:

• High Computational Overhead: Every collision requires evaluating a second hash function ($h_2(k)$). If the hash functions are mathematically complex, this increases CPU cycles per insertion/lookup.
• Design Complexity: Designing a secondary hash function $h_2(k)$ that never evaluates to $0$ (which would cause an infinite loop at the same index) and is relatively prime to the table size $m$ is difficult.
• Cache Misses: Because the step size can be large and pseudo-random, probing jumps across arbitrary memory locations, leading to frequent CPU cache misses.

5. Synthesis of Collision Resolution Techniques

6. Real-World Implementation: Why std::unordered_map Uses Separate Chaining

In C++, the standard library container std::unordered_map is designed to provide average $O(1)$ time complexity for search, insertion, and deletion.

Internally, std::unordered_map is implemented using Separate Chaining.

Why Separate Chaining is Preferred in Standard Libraries

1. Simple and Robust Deletion: In Open Addressing, deleting an element is highly problematic. You cannot simply clear the slot, as doing so would break the probe chain for other elements inserted after it. Instead, you must write a dummy value (a "tombstone" or DELETED marker). Over time, these markers clutter the table and degrade lookup performance. In Separate Chaining, deletion is a standard, clean linked list node removal.
2. Graceful Performance Degradation: As the load factor $\alpha$ (ratio of elements $n$ to buckets $m$) approaches or exceeds $1.0$, Open Addressing tables experience severe performance degradation and eventually fail to find empty slots. Separate Chaining can handle load factors $\alpha > 1.0$ without failing, though search times will gradually transition from $O(1)$ to $O(n)$ if the chains grow too long.
3. No Complex Probe Calculations: Separate Chaining avoids the CPU-heavy calculations of quadratic steps or secondary hash functions during collisions.

7. C++ Implementation of Separate Chaining

Below is a complete, production-grade implementation of a Hash Table using Separate Chaining. This code demonstrates how buckets, linked lists, and hash functions work together to resolve collisions.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

class SeparateChainingHashTable {
private:
    int bucket_count;
    // Vector of linked lists to store keys
    std::vector<std::list<int>> table;

    // Primary hash function
    int hashFunction(int key) const {
        return std::abs(key) % bucket_count;
    }

public:
    // Constructor
    explicit SeparateChainingHashTable(int buckets) : bucket_count(buckets) {
        table.resize(bucket_count);
    }

    // Insert a key into the hash table
    void insert(int key) {
        int index = hashFunction(key);
        
        // Prevent duplicate entries in the same bucket
        auto& bucket = table[index];
        if (std::find(bucket.begin(), bucket.end(), key) == bucket.end()) {
            bucket.push_back(key);
            std::cout << "Inserted " << key << " at index " << index << "\n";
        } else {
            std::cout << "Key " << key << " already exists at index " << index << "\n";
        }
    }

    // Search for a key in the hash table
    bool search(int key) const {
        int index = hashFunction(key);
        const auto& bucket = table[index];
        return std::find(bucket.begin(), bucket.end(), key) != bucket.end();
    }

    // Delete a key from the hash table
    void remove(int key) {
        int index = hashFunction(key);
        auto& bucket = table[index];
        auto it = std::find(bucket.begin(), bucket.end(), key);

        if (it != bucket.end()) {
            bucket.erase(it);
            std::cout << "Removed " << key << " from index " << index << "\n";
        } else {
            std::cout << "Key " << key << " not found at index " << index << "\n";
        }
    }

    // Display the hash table structure
    void display() const {
        for (int i = 0; i < bucket_count; ++i) {
            std::cout << "Bucket " << i << ":";
            for (const auto& key : table[i]) {
                std::cout << " -> " << key;
            }
            std::cout << " -> nullptr\n";
        }
    }
};

int main() {
    // Initialize a hash table with 5 buckets
    SeparateChainingHashTable ht(5);

    // Insert values that will cause collisions
    ht.insert(32); // 32 % 5 = 2
    ht.insert(42); // 42 % 5 = 2 (Collision resolved via chaining)
    ht.insert(78); // 78 % 5 = 3
    ht.insert(64); // 64 % 5 = 4
    ht.insert(96); // 96 % 5 = 1

    std::cout << "\n--- Hash Table State ---\n";
    ht.display();

    std::cout << "\n--- Search Operations ---\n";
    std::cout << "Search 42: " << (ht.search(42) ? "Found" : "Not Found") << "\n";
    std::cout << "Search 100: " << (ht.search(100) ? "Found" : "Not Found") << "\n";

    std::cout << "\n--- Deletion Operation ---\n";
    ht.remove(42);
    ht.display();

    return 0;
}

8. Summary and Key Takeaways

• The Core Goal of Hashing: We want to design hash functions and collision resolution strategies that minimize collisions and distribute keys uniformly across the table.
• Double Hashing Mechanics: By using a secondary hash function $h_2(k)$ to calculate the step size, Double Hashing ensures that keys with the same initial hash index follow different probe paths, successfully resolving Secondary Clustering.
• Double Hashing Overhead: The primary drawbacks of Double Hashing are its computational cost (evaluating two hash functions per collision) and the complexity of designing a safe, non-zero secondary hash function.
• C++ Standard Library Choice: C++'s std::unordered_map uses Separate Chaining to handle collisions.
• Why Separate Chaining Wins in Production: It allows for clean, simple deletion without leaving "tombstone" markers, and its performance degrades gracefully even when the load factor exceeds $1.0$.
• Memory vs. Cache Locality: While Open Addressing offers better cache locality because all elements reside in contiguous memory, Separate Chaining's structural simplicity and robust deletion make it the preferred choice for general-purpose standard libraries.