Collision resolution: open addressing and chaining
Collision resolution in hash tables using open addressing (linear/quadratic probing, double hashing) and separate chaining: definitions, assumptions, formulas for expected probes, worked insert/search examples, and Python implementations.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Hash tables give near O(1) average-time lookup for caches, symbol tables, routing tables, and indexing in databases. Collisions are unavoidable in finite tables, so knowing how to resolve them (open addressing and chaining) determines performance, memory use, and correctness under load.
Key ideas
- Hash function: A function h: U → {0, 1, …, m−1} that maps the universe of keys U to table indices. Good hash functions distribute keys uniformly.
- Collision: The event that two distinct keys k1 ≠ k2 have the same hash index: h(k1) = h(k2). Collisions are inevitable when |U| > m (pigeonhole principle).
- Load factor (α): α = n/m, where n is the number of stored keys and m is the table size. It measures table fullness. 0 ≤ α < 1 for open addressing; α ≥ 0 (unbounded) for chaining.
- Probe (or inspection): One access that checks a table slot (or a node in a chain) during search/insert/delete. We count expected number of probes to measure efficiency.
Collision resolution families
Separate chaining (chaining): Each table slot stores a pointer to a linked list (or dynamic array/bucket) of all keys whose hash is that slot. Insertion adds to the list; search scans only that slot’s list.
- Assumption (simple uniform hashing): For analysis, each key is equally likely to hash to any slot independently of others. This gives expected chain length α.
- Memory: Extra pointers/nodes per key.
- Delete: Simple (remove from list) without special markers.
- Diagram to draw: Draw an array of m boxes labeled 0..m−1. From some boxes, draw vertical linked lists with nodes containing keys; label each list’s length. Highlight α = average list length.
Open addressing: All keys stored directly in the array; on a collision, probe other slots according to a probe sequence until an empty slot is found.
- Probe sequence: For key k, a deterministic pseudo-random sequence of positions in 0..m−1 generated from k and method parameters; for some methods (e.g., double hashing with gcd(h2(k), m)=1) this sequence is a permutation, but in others (e.g., quadratic probing) it may not cover all m slots.
- Deletion requires tombstones (special markers) to not break search chains.
- Diagram to draw: Draw a single array 0..m−1. For a key k with h(k)=i, draw arrows from i to the next probed indices (i+1 mod m, etc.), number the probes (1st, 2nd, 3rd) until an empty slot.
Open addressing methods
- Linear probing: h_i(k) = (h(k) + i) mod m, i = 0, 1, 2, …. Simple and cache-friendly. Suffers from primary clustering: contiguous runs of occupied slots grow and attract more insertions.
- Quadratic probing: h_i(k) = (h(k) + c1·i + c2·i^2) mod m, i = 0, 1, 2, … with constants c1, c2 ≠ 0. Reduces primary clustering, but can suffer secondary clustering (keys with same h(k) follow the same probe sequence). In general it does not guarantee a full permutation of table indices; even with m prime, the probe sequence may visit only about m/2 distinct slots. To avoid premature insertion failure, keep α ≤ 0.5 or use double hashing; choose m prime (or odd) and c2 ≠ 0 to reduce short cycles.
- Double hashing: h_i(k) = (h1(k) + i·h2(k)) mod m, where h2(k) ≠ 0 mod m, often h2(k) = 1 + (k mod (m−1)). Approximates uniform hashing; avoids both primary and secondary clustering in practice. Works best with prime m.
Exact statements and commonly used results (with assumptions)
- Definition (Simple uniform hashing for chaining): Each key is equally likely to hash to each slot independently. Then expected chain length is α, and expected probes:
- Unsuccessful search: E[probes] = α (scan full expected list).
- Successful search (assuming new elements added at head and any position equally likely): E[probes] = 1 + α/2 (on average, half the list is examined before the match, plus 1 for the matching key comparison).
- Theorem (Expected probes in open addressing under uniform hashing): Assume uniform hashing over all m! probe permutations (i.e., every probe sequence is equally likely). Let α = n/m < 1.
- Unsuccessful search: E[probes] = 1 / (1 − α).
- Successful search: E[probes] = (1/α) · ln(1/(1 − α)). Sketch of derivation (unsuccessful): Probability that the first probed slot is occupied is α; that the first t distinct probed slots are all occupied is ∏_{j=0}^{t−1} (n−j)/(m−j) ≈ α^t for large m; summing this geometric-like tail yields 1/(1−α). Successful derivation integrates over insertion history; average over α′ from 0 to α gives (1/α)∫₀^α 1/(1−x) dx = (1/α) ln(1/(1−α)).
- Formulas specific to linear probing under simple assumptions (Knuth’s results): for α < 1,
- Unsuccessful search: E[probes] ≈ 0.5 · (1 + 1/(1 − α)^2).
- Successful search: E[probes] ≈ 0.5 · (1 + 1/(1 − α)). These are higher than the uniform-hashing bounds due to clustering.
When to prefer which
- Use chaining when: deletions are frequent; load factor may exceed 1; variable-length keys; simpler implementation; predictable O(α) worst-case per bucket (with good hash).
- Use open addressing when: memory is tight (no pointers); cache locality matters; easy serialization (contiguous array). Keep α well below 1 (commonly α ≤ 0.7) to maintain speed.
Deletion details
- Chaining: Remove node from list. Table slot pointer stays.
- Open addressing: Do not simply mark a slot empty; instead mark as a tombstone (DELETED). Search must treat tombstone as occupied and continue; insert may reuse tombstone. Periodic cleanup (rehash) removes tombstones.
Assumptions and pitfalls to state in exam answers
- State the hashing assumption (uniform hashing or simple uniform hashing) before quoting expected-probe formulas.
- For quadratic probing, mention the conditions (e.g., m prime and c2 ≠ 0) to ensure the probe sequence covers many slots; otherwise, insertion may fail before table is full.
- For double hashing, ensure h2(k) is relatively prime to m so the probe sequence cycles through all m slots.
Exact diagrams to draw and label
- Chaining diagram: Array of 10 boxes labeled 0..9. At indices 1, 4, 7 draw vertical linked lists with nodes labeled with sample keys (e.g., 21→31 at index 1). Label each arrow “next.” Write α = n/m next to the array.
- Open addressing probe path: Array of 10 boxes 0..9. For key 37 with h(37)=7, show 7 occupied, then arrow to 8, then 9, then 0, numbering each as 1st, 2nd, 3rd, 4th probe until an empty slot.
Connections to nearby syllabus topics
- Hash tables and hash functions: choose h(k), prime table size m, and universal hashing ideas.
- Rehashing and extendible hashing: how to grow tables when α is high (mention but do not re-teach).
- Algorithm analysis: use α to discuss average probes; worst-case is O(n) for both methods if hashing is adversarial.
Formulas
α = n / m
- α: load factor (dimensionless), n: number of stored keys (count), m: table size (count). Applies to both chaining and open addressing.
E_unsuccess_chain = α
- Expected probes for unsuccessful search in chaining under simple uniform hashing. Dimensionless count of inspections.
E_success_chain = 1 + α/2
- Expected probes for successful search in chaining under simple uniform hashing. Counts one access to the bucket plus average half-list scan.
E_unsuccess_open ≈ 1 / (1 − α)
- Expected probes for unsuccessful search in open addressing under uniform hashing. Valid for α < 1.
E_success_open ≈ (1/α) · ln(1/(1 − α))
- Expected probes for successful search in open addressing under uniform hashing. Valid for α < 1.
E_unsuccess_linear ≈ 0.5 · (1 + 1/(1 − α)^2)
- Expected probes for unsuccessful search in linear probing (Knuth’s approximation), α < 1.
E_success_linear ≈ 0.5 · (1 + 1/(1 − α))
- Expected probes for successful search in linear probing (Knuth’s approximation), α < 1.
h_linear_i(k) = (h(k) + i) mod m
- Probe i in linear probing. i starts at 0. m is table size (count).
h_quad_i(k) = (h(k) + c1·i + c2·i^2) mod m
- Probe i in quadratic probing. c1, c2 are non-zero constants; m commonly prime.
h_double_i(k) = (h1(k) + i·h2(k)) mod m
- Probe i in double hashing. Choose h2(k) so gcd(h2(k), m) = 1.
Worked examples
Example 1: Open addressing with linear probing — insertion and search Given: Table size m = 10, hash h(k) = k mod 10. Insert keys in order: 89, 18, 49, 58, 69. Then search for 58 and 89. Show probe sequences.
Steps:
- Insert 89: h(89) = 9 → slot 9 empty → place 89 at index 9. Probes used: 1 (index 9).
- Insert 18: h(18) = 8 → slot 8 empty → place 18 at index 8. Probes: 1 (index 8).
- Insert 49: h(49) = 9 → slot 9 occupied (89) → try (9+1) mod 10 = 0 → slot 0 empty → place 49 at index 0. Probes: 2 (indices 9, 0).
- Insert 58: h(58) = 8 → slot 8 occupied (18) → try 9 (occupied by 89) → try 0 (occupied by 49) → try 1 (empty) → place 58 at index 1. Probes: 4 (8, 9, 0, 1).
- Insert 69: h(69) = 9 → slot 9 occupied (89) → try 0 (49) → 1 (58) → 2 (empty) → place 69 at index 2. Probes: 4 (9, 0, 1, 2).
Final table (indices → key): 0→49, 1→58, 2→69, 3→·, 4→·, 5→·, 6→·, 7→·, 8→18, 9→89.
Search:
- Search 58: h(58)=8 → check 8 (18) ≠ 58 → 9 (89) ≠ 58 → 0 (49) ≠ 58 → 1 (58) found. Probes: 4.
- Search 89: h(89)=9 → check 9 (89) found. Probes: 1.
Comment: This shows a primary cluster at indices 8–2 (wrapping), causing longer probes for nearby keys.
Example 2: Chaining — expected probes and operations Given: m = 5, keys: 12, 22, 32, 14, 24, 44. Use h(k) = k mod 5. Insert in given order using separate chaining at head.
Insertions:
- h(12)=2 → slot 2: [12]
- h(22)=2 → slot 2: [22 → 12]
- h(32)=2 → slot 2: [32 → 22 → 12]
- h(14)=4 → slot 4: [14]
- h(24)=4 → slot 4: [24 → 14]
- h(44)=4 → slot 4: [44 → 24 → 14]
Final buckets: 0:·, 1:·, 2:[32→22→12], 3:·, 4:[44→24→14]. Here n=6, m=5, α = n/m = 6/5 = 1.2.
Expected probes (simple uniform hashing assumption):
- Unsuccessful search: E_unsuccess_chain = α = 1.2 probes (on average, you traverse a list of expected length α).
- Successful search: E_success_chain = 1 + α/2 = 1 + 0.6 = 1.6 probes (on average). Under the simple uniform hashing model with α = 1.2, E_success_chain = 1 + α/2 = 1.6. In this concrete table (two chains of length 3), a successful search examines on average 2 nodes (elements) from the head.
Delete example: Delete 22 by removing its node from the index-2 list: [32 → 12]. No tombstones are needed.
Example 3: Python implementations — open addressing (linear probing) and chaining Program: Two minimal classes supporting insert, search, and delete. Sample I/O shows operations and outputs.
Python code:
# Hash table with linear probing (open addressing)
class LinearProbingHash:
def __init__(self, m):
self.m = m
self.keys = [None] * m
self.values = [None] * m
self.tombstone = object() # unique marker
def _hash(self, k):
return hash(k) % self.m
def insert(self, k, v):
i = self._hash(k)
first_tomb = None
for _ in range(self.m):
if self.keys[i] is None:
# use earlier tombstone if any
target = first_tomb if first_tomb is not None else i
self.keys[target], self.values[target] = k, v
return True
elif self.keys[i] is self.tombstone:
if first_tomb is None:
first_tomb = i
elif self.keys[i] == k:
self.values[i] = v # update
return True
i = (i + 1) % self.m
return False # table full
def search(self, k):
i = self._hash(k)
for _ in range(self.m):
if self.keys[i] is None:
return None # stop at empty slot
if self.keys[i] is not self.tombstone and self.keys[i] == k:
return self.values[i]
i = (i + 1) % self.m
return None
def delete(self, k):
i = self._hash(k)
for _ in range(self.m):
if self.keys[i] is None:
return False
if self.keys[i] is not self.tombstone and self.keys[i] == k:
self.keys[i] = self.tombstone
self.values[i] = None
return True
i = (i + 1) % self.m
return False
# Hash table with separate chaining using Python lists for buckets
class ChainingHash:
def __init__(self, m):
self.m = m
self.buckets = [[] for _ in range(m)] # list of (key, value)
def _hash(self, k):
return hash(k) % self.m
def insert(self, k, v):
b = self._hash(k)
bucket = self.buckets[b]
for i, (key, _) in enumerate(bucket):
if key == k:
bucket[i] = (k, v)
return True
bucket.insert(0, (k, v)) # head insert
return True
def search(self, k):
b = self._hash(k)
for key, val in self.buckets[b]:
if key == k:
return val
return None
def delete(self, k):
b = self._hash(k)
bucket = self.buckets[b]
for i, (key, _) in enumerate(bucket):
if key == k:
del bucket[i]
return True
return False
if __name__ == "__main__":
# Demo
lp = LinearProbingHash(7)
for k in [10, 3, 17, 24, 31]:
lp.insert(k, str(k))
print(lp.search(24)) # expect '24'
print(lp.search(99)) # expect None
lp.delete(17)
print(lp.search(17)) # expect None
ch = ChainingHash(5)
for k in [12, 22, 32, 14, 24, 44]:
ch.insert(k, str(k))
print(ch.search(32)) # expect '32'
ch.delete(22)
print(ch.search(22)) # expect None
Sample exact output:
24
None
None
32
None
Notes:
- Python’s built-in hash() is used only for demo; in exams use the given modular hash.
- LinearProbingHash uses a tombstone to support correct search after deletions.
Example 4 (theory model answer): Compare open addressing and chaining with respect to load factor and expected probes. Model points to write:
- Define α = n/m. In open addressing, α must be < 1; in chaining, α can be ≥ 1 because lists can grow.
- Under uniform hashing:
- Open addressing: E_unsuccess ≈ 1/(1−α), E_success ≈ (1/α) ln(1/(1−α)). Performance degrades sharply as α → 1.
- Linear probing (specific): E_unsuccess ≈ 0.5(1 + 1/(1−α)^2), E_success ≈ 0.5(1 + 1/(1−α)).
- Chaining: E_unsuccess = α, E_success = 1 + α/2. Performance grows linearly with α, and α may exceed 1.
- Space: Open addressing stores only array entries. Chaining needs extra pointer/structure overhead per key.
- Cache locality: Open addressing often better (contiguous probes). Chaining may jump in memory.
- Deletion: Easy in chaining; tombstones needed in open addressing.
- Conclusion: Use open addressing for tight memory and when you can keep α ≤ 0.7; use chaining when deletions are frequent or α may become large.
Common mistakes
- Deleting in open addressing by setting slot to empty instead of a tombstone, which breaks later searches.
- Mixing up formulas: quoting 1/(1−α) for successful search in open addressing (it is for unsuccessful under uniform hashing).
- Ignoring clustering: claiming double hashing has same clustering as linear probing (it does not; it reduces clustering significantly).
- Using non-prime m with double hashing and choosing h2(k) that shares a factor with m, causing short cycles that never cover the table.
- For chaining expected probes, forgetting the leading “1 +” term in E_success_chain = 1 + α/2 (bucket access plus half-list on average).
- Not stating the hashing assumption (uniform or simple uniform) before presenting expected-cost results.
For your exam
- Short notes: linear/quadratic probing, double hashing; advantages/disadvantages; when to use each. Include formulas and conditions (e.g., gcd(h2(k), m)=1).
- Derivations: Expected probes under uniform hashing (outline integrals/sums). State assumptions clearly. For linear probing, quote the standard approximations with α.
- Numericals: Given m, h(k)=k mod m, and a sequence of keys, perform insertions using linear probing or chaining, show probe counts and final table. Draw the array and label indices, probe order, and chains.
- Programs: Implement a small hash table with open addressing or chaining (Python). Show sample I/O and exact output.
- Diagrams: Array 0..m−1, chains as linked lists, or probe path arrows with probe numbers.
- Full-marks answers: include assumptions, formulas with α, correct probe sequences with wrap-around, and clear diagrams.
Quick check
- Define load factor α and state its allowable range for open addressing and for chaining.
- Give the expected number of probes for an unsuccessful search under (a) chaining, and (b) open addressing with uniform hashing, both in terms of α.
- What is primary clustering, and which probing method best avoids it among linear probing, quadratic probing, and double hashing?
Answers: (1) α = n/m; open addressing requires 0 ≤ α < 1; chaining allows α ≥ 0 (can exceed 1). (2a) α; (2b) 1/(1−α). (3) Growth of long contiguous occupied runs due to linear probing; double hashing best avoids it.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?