1. One-Liner
Open addressing resolves collisions by searching other indices in the same array—no separate chains—using a probe sequence.
2. The Problem It Solves
You want one array, cache-friendly layout, and no pointer chasing; classic for compact maps when load factor stays <1 and tombstones handle deletes.
3. The Core Idea
If slot h(k) is taken, try h(k)+f(i) for i=1,2,… per policy (linear, quadratic, double hashing) until empty or found.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Hash | Start index i0 = h(k) % m |
| 2. Probe | On collision, next slot via probe rule |
| 3. Insert | First empty or tombstone slot |
| 4. Delete | Mark tombstone so probes don’t break |
5. Dry Run Example
Linear probe, table size 5, insert keys hashing to 1,1,1: occupy 1,2,3 sequentially.
6. Key Properties
| Property | Value |
|---|---|
| Clustering | Primary/secondary risks with linear/quadratic |
| Load | Must keep α < 1 |
| Delete | Tombstones needed |
7. Where It Is Used
| Domain | Use |
|---|---|
| Embedded / GPU | Compact tables |
| Python | dict implementation details differ; concept in teaching |
8. Interview Tips
Explain clustering; double hashing reduces clustering; rehash when probe lengths grow.
9. Comparison with Other Algorithms
| Scheme | Collision |
|---|---|
| Open addressing | Probe in-array |
| Chaining | External lists |
| Cuckoo | Two choices + eviction |
10. Complexity
| Metric | Value |
|---|---|
| Average | O(1) for low α, good hash |
| Worst | O(n) long probe chains |
Implementation Example (PYTHON)
class LinearProbe:
def __init__(self, m=16):
self.m, self.t = m, [None] * m
def _h(self, k): return hash(k) % self.m
def put(self, k, v):
i = self._h(k)
for s in range(self.m):
j = (i + s) % self.m
if self.t[j] in (None, 'DEL') or self.t[j][0] == k:
self.t[j] = (k, v); return
def get(self, k):
i = self._h(k)
for s in range(self.m):
j = (i + s) % self.m
e = self.t[j]
if e is None: return None
if e != 'DEL' and e[0] == k: return e[1]
return None