Hashing - DSA | Chapter: Open Addressing I: Linear Probing and Primary Clustering

This chapter explores the transition from Separate Chaining to Open Addressing as a collision resolution strategy in Hash Tables. We analyze the worst-case limitations of Separate Chaining, examine how modern languages optimize bucket structures, define the significance of the Load Factor, and walk through the mechanics, mathematical formulation, and performance pitfalls (specifically Primary Clustering) of Linear Probing.

1. The Limitations of Separate Chaining

In Separate Chaining, every index of the hash table points to a secondary data structure (typically a singly linked list) that stores all keys mapping to that same index. While simple to implement, this approach has a critical performance vulnerability in its worst-case scenario.

The $O(N)$ Worst-Case Search Time

If we insert $N$ elements into a hash table, and our hash function maps all $N$ elements to the exact same index (for example, if all keys end with the digit 3 and our hash function is $k \pmod{10}$ ), they will all be appended to the same linked list.

Structure & Concept Flow

Index 3

[ Key: 13 ] -> [ Key: 23 ] -> [ Key: 33 ] -> [ Key: 43 ] -> ... -> [ Key: N3 ]

In this scenario:

Insertion: Remains $O(1)$ if we insert at the head of the linked list.
Search/Deletion: Degenerates to $O(N)$ because we must traverse the entire linked list sequentially to locate or remove a target element.

This degradation defeats the primary purpose of using a hash table, which is to achieve near $O(1)$ average-time complexity for search, insertion, and deletion.

2. Optimizing Chaining with Self-Balancing Trees (AVL Trees)

To mitigate the $O(N)$ worst-case search time of linked-list chaining, we can replace the linked list at each bucket with a self-balancing binary search tree, such as an AVL Tree or a Red-Black Tree.

Structure & Concept Flow

Linked List Bucket (Naive) Self-Balancing BST Bucket (Optimized)

13 -> 23 -> 33 -> 43 23

/ \

13 33

Impact on Complexity

By using a self-balancing tree:

The worst-case search, insertion, and deletion time within a highly congested bucket is reduced from $O(N)$ to $O(\log N)$ , where $N$ is the number of elements in that bucket.

Real-World Language Implementations

Java (java.util.HashMap): Java utilizes this optimization. When the number of elements in a single bucket exceeds a specific threshold (known as the TREEIFY_THRESHOLD, which is defaults to 8), the linked list is automatically converted ("treeified") into a Red-Black Tree. If the number of elements in the bucket decreases below a certain threshold (known as the UNTREEIFY_THRESHOLD, which is 6), it converts back to a linked list to save memory.
C++ (std::unordered_map): Standard C++ libraries do not currently implement this treeification optimization. They continue to rely on singly linked lists for bucket chaining, meaning worst-case lookups can still degenerate to $O(N)$ if a poor hash function is used.

3. Understanding the Load Factor ( $\alpha$ )

The Load Factor ( $\alpha$ ) is a fundamental metric used to measure how full a hash table is. It serves as a health indicator for the table and dictates when the table should be resized (rehashed).

Mathematical Definition

\text{Load Factor } (\alpha) = \frac{N}{M}

Where:

$N$ = Total number of elements currently stored in the hash table.
$M$ = Size of the hash table (total number of available slots/buckets).

Practical Example

Consider a hash table of size $M = 10$ . If we insert $N = 9$ elements into this table:

\alpha = \frac{9}{10} = 0.9

A load factor of $0.9$ indicates that the table is $90\%$ full.

Note: In Separate Chaining, the load factor $\alpha$ can exceed $1.0$ because multiple elements can be chained at each index. However, in Open Addressing, because every slot can hold at most one element, the load factor $\alpha$ must always satisfy $0 \le \alpha \le 1$ .

4. Introduction to Open Addressing & Linear Probing

When separate chaining is undesirable due to the memory overhead of pointers or poor cache locality, Open Addressing is used. In Open Addressing, all elements are stored directly within the hash table array itself. No external structures (like linked lists or trees) are allowed.

The Core Rule of Open Addressing

Every slot in the hash table can hold at most one element. If a collision occurs at a calculated index, we must search ("probe") for another empty slot within the array according to a systematic sequence.

Linear Probing

Linear Probing is the simplest probing scheme in Open Addressing. When a collision occurs at index $h(k)$ , we sequentially scan the subsequent indices one by one (wrapping around to the beginning of the array if we reach the end) until we find an empty slot.

5. Mathematical Formulation of Linear Probing

To formalize this sequential search, we define a probing hash function that takes two arguments: the key $k$ and the probe attempt number $i$ (starting at $0$ ).

The Probing Function

h(k, i) = (h'(k) + i) \pmod{M}

Where:

$k$ is the key being inserted or searched.
$i$ is the probe index/attempt number ( $i = 0, 1, 2, \dots, M-1$ ).
$h'(k)$ is the base hash function (e.g., $k \pmod{M}$ ).
$M$ is the size of the hash table.

How the Probes Resolve

First Attempt ( $i = 0$ ): We check the natural hash location:

h(k, 0) = h'(k) \pmod{M}

Second Attempt ( $i = 1$ ): If a collision occurs, we check the next immediate slot:

h(k, 1) = (h'(k) + 1) \pmod{M}

Third Attempt ( $i = 2$ ): If that is also occupied, we check:

h(k, 2) = (h'(k) + 2) \pmod{M}

This linear progression continues until an empty slot is found or the entire table has been probed.

6. Step-by-Step Execution Trace

Let us trace the insertion of a dataset using Linear Probing.

Setup

Table Size ( $M$ ): $10$ (Indices $0$ to $9$ )
Base Hash Function: $h'(k) = k \pmod{10}$
Dataset to Insert: [98, 22, 34, 54, 64, 74]

Step-by-Step Insertion Flow

CODE

Empty Table (Size 10):
[ - , - , - , - , - , - , - , - , - , - ]
  0   1   2   3   4   5   6   7   8   9

1. Insert `98`

$h'(98) = 98 \pmod{10} = 8$
Probe $i = 0$ : $h(98, 0) = 8$ . Slot $8$ is empty.
Action: Place 98 at index $8$ .

CODE

[ - , - , - , - , - , - , - , - , 98 , - ]
  0   1   2   3   4   5   6   7    8   9

2. Insert `22`

$h'(22) = 22 \pmod{10} = 2$
Probe $i = 0$ : $h(22, 0) = 2$ . Slot $2$ is empty.
Action: Place 22 at index $2$ .

CODE

[ - , - , 22 , - , - , - , - , - , 98 , - ]
  0   1    2   3   4   5   6   7    8   9

3. Insert `34`

$h'(34) = 34 \pmod{10} = 4$
Probe $i = 0$ : $h(34, 0) = 4$ . Slot $4$ is empty.
Action: Place 34 at index $4$ .

CODE

[ - , - , 22 , - , 34 , - , - , - , 98 , - ]
  0   1    2   3    4   5   6   7    8   9

4. Insert `54`

$h'(54) = 54 \pmod{10} = 4$
Probe $i = 0$ : $h(54, 0) = 4$ . Collision! (Slot $4$ is occupied by 34).
Probe $i = 1$ : $h(54, 1) = (4 + 1) \pmod{10} = 5$ . Slot $5$ is empty.
Action: Place 54 at index $5$ .

CODE

[ - , - , 22 , - , 34 , 54 , - , - , 98 , - ]
  0   1    2   3    4    5   6   7    8   9

5. Insert `64`

$h'(64) = 64 \pmod{10} = 4$
Probe $i = 0$ : $h(64, 0) = 4$ . Collision! (Slot $4$ is occupied by 34).
Probe $i = 1$ : $h(64, 1) = 5$ . Collision! (Slot $5$ is occupied by 54).
Probe $i = 2$ : $h(64, 2) = (4 + 2) \pmod{10} = 6$ . Slot $6$ is empty.
Action: Place 64 at index $6$ .

CODE

[ - , - , 22 , - , 34 , 54 , 64 , - , 98 , - ]
  0   1    2   3    4    5    6   7    8   9

6. Insert `74`

$h'(74) = 74 \pmod{10} = 4$
Probe $i = 0$ : $h(74, 0) = 4$ . Collision! (Slot $4$ is occupied).
Probe $i = 1$ : $h(74, 1) = 5$ . Collision! (Slot $5$ is occupied).
Probe $i = 2$ : $h(74, 2) = 6$ . Collision! (Slot $6$ is occupied).
Probe $i = 3$ : $h(74, 3) = (4 + 3) \pmod{10} = 7$ . Slot $7$ is empty.
Action: Place 74 at index $7$ .

CODE

Final Table State:
[ - , - , 22 , - , 34 , 54 , 64 , 74 , 98 , - ]
  0   1    2   3    4    5    6    7    8   9

7. The Phenomenon of Primary Clustering

While Linear Probing is simple and highly cache-friendly, it suffers from a severe performance bottleneck known as Primary Clustering.

What is Primary Clustering?

Primary Clustering is the tendency for occupied slots in a linearly probed hash table to form long, contiguous blocks (clusters) over time.

CODE

[ - , - , 22 , - , [ 34 , 54 , 64 , 74 ] , 98 , - ]
  0   1    2   3         CLUSTERING        8   9

Why Does It Happen?

When keys hash to nearby or identical values, they compete for the same empty slots. As a cluster grows larger, the probability that a new key will hash into that cluster increases.

For instance, in our final table state above:

Any new key hashing to index $4, 5, 6,$ or $7$ will be forced to scan past the entire cluster to find the next available slot (which is index $9$ or $0$ ).
This causes the lookup and insertion times to degrade from $O(1)$ toward $O(N)$ as the table fills up.

8. Complete C++ Implementation of Linear Probing

Below is a complete, production-grade C++ implementation of a Hash Table using Linear Probing. It handles insertions, searches, and deletions.

Crucial Implementation Detail: When deleting an element in a linearly probed hash table, we cannot simply set the slot to "empty" (nullptr or -1). Doing so would break the probe chain for subsequent elements that were inserted after a collision. Instead, we must use a special marker called a Tombstone (or dummy node) to indicate that an element was deleted but the probe chain should continue.

C++

#include <iostream>
#include <vector>

class LinearProbingHashTable {
private:
    enum SlotState { EMPTY, OCCUPIED, DELETED };

    struct HashNode {
        int key;
        int value;
        SlotState state;

        HashNode() : key(-1), value(-1), state(EMPTY) {}
    };

    std::vector<HashNode> table;
    int capacity;
    int size;

    int hashFunction(int key) const {
        return std::abs(key) % capacity;
    }

public:
    explicit LinearProbingHashTable(int cap) : capacity(cap), size(0) {
        table.resize(capacity);
    }

    // Insert key-value pair
    bool insert(int key, int value) {
        if (size >= capacity) {
            std::cerr << "Hash Table is full!" << std::endl;
            return false;
        }

        int hashIndex = hashFunction(key);
        int i = 0;

        // Find the first available slot (either EMPTY or DELETED)
        while (table[(hashIndex + i) % capacity].state == OCCUPIED) {
            // If key already exists, update its value
            if (table[(hashIndex + i) % capacity].key == key) {
                table[(hashIndex + i) % capacity].value = value;
                return true;
            }
            i++;
            if (i == capacity) return false; // Table fully searched
        }

        int targetIndex = (hashIndex + i) % capacity;
        table[targetIndex].key = key;
        table[targetIndex].value = value;
        table[targetIndex].state = OCCUPIED;
        size++;
        return true;
    }

    // Search for a key
    bool search(int key, int& value) const {
        int hashIndex = hashFunction(key);
        int i = 0;

        while (table[(hashIndex + i) % capacity].state != EMPTY) {
            if (table[(hashIndex + i) % capacity].state == OCCUPIED &&
                table[(hashIndex + i) % capacity].key == key) {
                value = table[(hashIndex + i) % capacity].value;
                return true;
            }
            i++;
            if (i == capacity) break; // Traversed the entire table
        }
        return false; // Key not found
    }

    // Delete a key using Tombstone mechanism (DELETED state)
    bool remove(int key) {
        int hashIndex = hashFunction(key);
        int i = 0;

        while (table[(hashIndex + i) % capacity].state != EMPTY) {
            if (table[(hashIndex + i) % capacity].state == OCCUPIED &&
                table[(hashIndex + i) % capacity].key == key) {
                table[(hashIndex + i) % capacity].state = DELETED;
                size--;
                return true;
            }
            i++;
            if (i == capacity) break;
        }
        return false; // Key not found
    }

    // Display the current state of the table
    void display() const {
        for (int i = 0; i < capacity; i++) {
            if (table[i].state == OCCUPIED) {
                std::cout << "Index " << i << ": [" << table[i].key << " -> " << table[i].value << "]\n";
            } else if (table[i].state == DELETED) {
                std::cout << "Index " << i << ": [DELETED (Tombstone)]\n";
            } else {
                std::cout << "Index " << i << ": [EMPTY]\n";
            }
        }
    }
};

int main() {
    LinearProbingHashTable ht(10);

    ht.insert(98, 1001);
    ht.insert(22, 1002);
    ht.insert(34, 1003);
    ht.insert(54, 1004);
    ht.insert(64, 1005);
    ht.insert(74, 1006);

    std::cout << "--- Initial Hash Table State ---" << std::endl;
    ht.display();

    std::cout << "\n--- Deleting Key 54 ---" << std::endl;
    ht.remove(54);
    ht.display();

    std::cout << "\n--- Searching for Key 64 ---" << std::endl;
    int val;
    if (ht.search(64, val)) {
        std::cout << "Found Key 64 with Value: " << val << std::endl;
    } else {
        std::cout << "Key 64 not found!" << std::endl;
    }

    return 0;
}

9. Comparison: Separate Chaining vs. Linear Probing

Parameter / Feature	Separate Chaining	Linear Probing (Open Addressing)
Memory Allocation	Dynamic (allocates memory for new nodes on the fly).	Static (pre-allocates a fixed-size array).
Cache Friendliness	Poor (linked list nodes are scattered across the heap).	Excellent (contiguous array elements leverage CPU cache lines).
Space Overhead	High (stores pointers/references for each node).	Low (only stores keys/values within the array).
Load Factor ( $\alpha$ )	Can be $> 1.0$ .	Must be $\le 1.0$ (typically kept $< 0.7$ to avoid performance degradation).
Worst-Case Performance	$O(N)$ (can be optimized to $O(\log N)$ using self-balancing trees).	$O(N)$ (due to primary clustering when the table is nearly full).
Deletion Complexity	Simple (standard linked list node deletion).	Complex (requires Tombstones to avoid breaking probe chains).

10. Summary and Key Takeaways

Chaining Worst-Case: Separate Chaining has a worst-case lookup complexity of $O(N)$ if all keys hash to the same index.
Treeification: Modern languages like Java optimize Separate Chaining by converting long linked lists into self-balancing Red-Black trees when a bucket's size exceeds a threshold, reducing the worst-case lookup to $O(\log N)$ . C++ standard libraries do not currently implement this.
Load Factor: Defined as $\alpha = \frac{N}{M}$ . It represents the density of the hash table and is used to trigger rehashing operations.
Open Addressing: Stores all elements directly within the hash table array, eliminating pointer overhead and maximizing CPU cache efficiency.
Linear Probing Formula: Uses the probe sequence $h(k, i) = (h'(k) + i) \pmod{M}$ to find the next available slot sequentially.
Primary Clustering: The major drawback of Linear Probing, where contiguous blocks of occupied slots build up, causing search and insertion times to degrade toward $O(N)$ .
Tombstone Deletion: Deleting an element in Linear Probing requires marking the slot as DELETED (rather than EMPTY) to prevent breaking the probe chain for elements inserted further down the sequence.

Open Addressing I: Linear Probing and Primary Clustering

Hashing - DSA | Chapter: Open Addressing I: Linear Probing and Primary Clustering

1. The Limitations of Separate Chaining

The O(N)O(N)O(N) Worst-Case Search Time

2. Optimizing Chaining with Self-Balancing Trees (AVL Trees)

Impact on Complexity

Real-World Language Implementations

3. Understanding the Load Factor (α\alphaα)

Mathematical Definition

Practical Example

4. Introduction to Open Addressing & Linear Probing

The Core Rule of Open Addressing

Linear Probing

5. Mathematical Formulation of Linear Probing

The Probing Function

How the Probes Resolve

6. Step-by-Step Execution Trace

Setup

Step-by-Step Insertion Flow

1. Insert 98

2. Insert 22

3. Insert 34

4. Insert 54

5. Insert 64

6. Insert 74

7. The Phenomenon of Primary Clustering

What is Primary Clustering?

Why Does It Happen?

8. Complete C++ Implementation of Linear Probing

9. Comparison: Separate Chaining vs. Linear Probing

10. Summary and Key Takeaways

The $O(N)$ Worst-Case Search Time

3. Understanding the Load Factor ( $\alpha$ )

1. Insert `98`

2. Insert `22`

3. Insert `34`

4. Insert `54`

5. Insert `64`

6. Insert `74`