Linear Probing for Conflict Resolution in Hash Tables

In hash table design, mapping a vast or infinite universe of application keys into a bounded array of size $m$ inevitably causes collisions due to the Pigeonhole Principle. Collision resolution strategies generally fall into two categories:

1. Separate Chaining (Closed Addressing): Uses auxiliary data structures (such as linked lists or balanced trees) pinned to each bucket to store colliding keys outside the primary table array.
2. Open Addressing: Retains all key-value pairs directly inside the hash table array. If a collision occurs at a hashed index, the algorithm systematically probes alternative slots within the array until an available slot is discovered.

Linear probing is the simplest, most intuitive, and widely used probing strategy under open addressing. Despite its apparent simplicity, it delivers remarkable real-world performance due to low-level hardware optimizations.

---

1. The Probing Function Mechanics

In open addressing, an algorithm determines where to inspect next using a probing function. A probing function generates a permutation of table indices based on the key and the sequence of probe attempts.

The Mathematical Formulation

Linear probing defines the index for attempt $i$ (where $i \ge 0$) as:

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

Where:

• $k$ is the key.
• $h(k)$ is the primary hash function mapping the key to an initial slot index $[0, m - 1]$.
• $i$ is the attempt/probe counter ($i = 0, 1, 2, \dots, m - 1$).
• $m$ is the total capacity of the hash table.

When inserting or searching for a key, the algorithm first checks slot $h(k)$. If that slot is occupied by a different key, it inspects $(h(k) + 1) \pmod m$, then $(h(k) + 2) \pmod m$, wrapping around to index $0$ upon reaching the end of the array.

Initial Hash: h(k) = 3

Attempt 0: Index 3 (Occupied) -> Collision
Attempt 1: Index 4 (Occupied) -> Collision
Attempt 2: Index 5 (Occupied) -> Collision
Attempt 3: Index 6 (Empty)    -> Insert Key Here

---

2. Core Hash Table Operations

Insertion

To insert a key-value pair $(k, v)$:

1. Compute the home bucket index: $\text{idx} = h(k) \pmod m$.
2. Inspect slot $\text{idx}$:
   • If the slot is empty or marked as deleted, store $(k, v)$ and terminate.
   • If the slot already contains the key $k$, update its associated value $v$.
   • If the slot contains a distinct key, increment the probe sequence: $\text{idx} = (\text{idx} + 1) \pmod m$.
3. Repeat step 2 until an empty slot is found or $m$ attempts have been exhausted (indicating that the hash table is completely full).

flowchart TD
    A[Start Insert Key k] --> B["Compute idx = h(k) % m, attempt i = 0"]
    B --> C{"Is table[idx] empty or deleted?"}
    C -- Yes --> D["Store key-value at table[idx]"]
    D --> E[Done]
    C -- No --> F{"Does table[idx].key == k?"}
    F -- Yes --> G["Update value at table[idx]"]
    G --> E
    F -- No --> H["i = i + 1, idx = (idx + 1) % m"]
    H --> I{"i == m?"}
    I -- Yes --> J[Table Full Error / Resize]
    I -- No --> C

Key Lookup (Search)

1. Compute $\text{idx} = h(k) \pmod m$.
2. Inspect the entry at $\text{idx}$:
   • If the slot matches key $k$, return the value.
   • If the slot is completely empty (unoccupied and never populated), the search terminates immediately with a “Key Not Found” result. Because linear probing fills contiguous runs of slots without gaps, encountering an empty slot guarantees that the key was never inserted.
   • If the slot is occupied by a different key (or holds a tombstone), move to $(\text{idx} + 1) \pmod m$.
3. If all $m$ slots are probed without finding the key, the key is absent.

Deletion: The Necessity of Soft Deletes (Tombstones)

In open addressing, hard deletion (simply nullifying or clearing the slot) breaks the probing chain.

Consider three keys, $k_1$, $k_2$, and $k_3$, all hashing to index $2$:

• $k_1$ sits at index $2$.
• $k_2$ sits at index $3$.
• $k_3$ sits at index $4$.

If $k_2$ is hard deleted and reset to an empty state:

• A subsequent lookup for $k_3$ computes $h(k_3) = 2$.
• Index $2$ contains $k_1$ (mismatch, probe next).
• Index $3$ is now empty.
• The lookup logic assumes that because index $3$ is empty, $k_3$ was never inserted, prematurely terminating the search and producing a false negative.

Before Deletion:
[0] | [1] | [2: k1] | [3: k2] | [4: k3] | [5: Empty]

Hard Deleting k2 (BROKEN):
[0] | [1] | [2: k1] | [3: Empty] | [4: k3] | [5: Empty]
                      ^ Lookup for k3 stops here prematurely!

Soft Deleting k2 (CORRECT):
[0] | [1] | [2: k1] | [3: TOMBSTONE] | [4: k3] | [5: Empty]
                      ^ Lookup treats this as occupied, continues to [4]

To preserve search chain continuity, linear probing mandates soft deletion (tombstones):

• Deleted slots are marked with a sentinel value (e.g., TOMBSTONE).
• Search operations treat TOMBSTONE as an occupied slot and continue probing forward.
• Insert operations treat TOMBSTONE as an available slot and may reuse it to store incoming entries.

---

3. Why Linear Probing is So Fast: Hardware Cache Locality

On paper, linear probing looks inefficient because it sequentially scans an array during collisions. However, in practice, linear probing frequently outperforms quadratic probing, double hashing, and separate chaining.

The performance advantage stems from spatial locality of reference and modern CPU memory hierarchies:

+-------------------------------------------------------------------------+
| RAM (High latency: ~50-100ns)                                          |
+-------------------------------------------------------------------------+
                                | (Fetches entire 64-byte Cache Line)
                                v
+-------------------------------------------------------------------------+
| L1/L2 CPU Cache (Low latency: ~1-4ns)                                  |
| Slot 2 | Slot 3 | Slot 4 | Slot 5 | Slot 6 | Slot 7                     |
+-------------------------------------------------------------------------+
      |        |        |        |
      +--------+--------+--------+----> Probing adjacent slots hits CPU cache!

1. Cache Lines: Modern processors do not fetch individual words or bytes from main memory (RAM). Instead, they fetch data in fixed-sized chunks called cache lines (typically 64 bytes).
2. Sequential Memory Layout: A hash table backing array stores elements contiguously. Accessing slot table[i] fetches the surrounding elements (table[i+1], table[i+2], etc.) directly into L1/L2/L3 cache.
3. Zero RAM Roundtrips on Collisions: When linear probing resolves a collision by checking subsequent array entries, those entries often already reside inside the CPU cache line. The CPU performs sub-nanosecond cache lookups instead of stalling on high-latency RAM access.
4. Prefetching: Modern CPU hardware prefetchers detect linear memory access patterns automatically and proactively pull upcoming cache lines from RAM, drastically reducing pipeline stalls.

Chained hash tables, by contrast, store nodes via heap-allocated pointers. Traversing a linked list requires chasing pointers to arbitrary memory addresses, incurring frequent CPU cache misses.

---

4. Inherent Challenges and Trade-offs

While linear probing delivers exceptional cache efficiency, it introduces two distinct structural vulnerabilities.

1. Primary Clustering

Linear probing is susceptible to primary clustering—a phenomenon where occupied slots agglomerate into continuous, long blocks.

• When two or more keys collide or hash to adjacent slots, they create a small cluster.
• Any future key that hashes to any slot within that cluster will probe to the end of the cluster and append itself, making the cluster even longer.
• Larger clusters have a higher statistical probability of being struck by subsequent hashes, creating a self-reinforcing feedback loop.

Cluster Formation:
Initial: [ Empty ] [ k1 ] [ k2 ] [ Empty ] [ Empty ]
                      ^-- Cluster of length 2

Any key hashing to index 1 or 2 will be forced to slot 3:
Result:  [ Empty ] [ k1 ] [ k2 ] [ k3 ] [ Empty ]
                      ^-- Cluster expands to length 3

As the cluster grows, average search, insertion, and deletion times degrade from $O(1)$ toward $O(N)$.

2. High Sensitivity to Hash Function Quality

Linear probing depends heavily on uniform hash distribution across the full range $[0, m - 1]$:

• Poor Hash Functions: If a hash function generates clustered outputs within a narrow range (e.g., heavily biasing toward indices $10$ through $20$), linear probing deteriorates rapidly into a pure linear search.
• Recommended Hash Functions: High-entropy non-cryptographic hash functions such as MurmurHash3, xxHash, or CityHash are strongly preferred over basic modulo arithmetic or simplistic polynomial rolling hashes, as they guarantee near-uniform bit dispersion.

---

5. Complexity Summary

Metric	Average Case	Worst Case	Notes
Search Time	$O(1)$	$O(N)$	$O(N)$ occurs when clustering spans the entire table.
Insert Time	$O(1)$	$O(N)$	Requires resizing/re-hashing before the load factor $\alpha \to 1.0$.
Delete Time	$O(1)$	$O(N)$	Requires tombstone allocation.
Space Overhead	Minimal	Low	Zero pointer overhead; requires preallocated array capacity.

Note on Load Factor ($\alpha = \frac{N}{m}$): Open addressing performance degrades exponentially as $\alpha$ approaches $1.0$. Linear probing systems typically trigger a table resize and rehash when $\alpha$ reaches between $0.5$ and $0.7$ to prevent primary clustering from dominating search latencies.

---

6. Summary

• Open Addressing Paradigm: Resolves collisions directly within the hash table array without auxiliary pointer-based data structures.
• Sequential Inspection: Linear probing sequentially scans the immediate next slots using $h(k, i) = (h(k) + i) \pmod m$.
• Cache Friendly: Contiguous memory access patterns maximize L1/L2/L3 cache hits and benefit from hardware prefetching, providing $O(1)$ amortized speed in practice.
• Tombstones Required: Hard deletions break probing chains, requiring soft deletes (tombstones) to maintain search integrity.
• Vulnerabilities: Primary clustering and sensitivity to low-entropy hash functions remain the primary drawbacks, managed via uniform hash functions (like MurmurHash) and conservative load factors.