Open addressing: probes, deletion and full tables
Contract and connection
Continue separate chaining's dictionary and load-factor concepts. Open addressing stores at most one live record per slot inside the table. Each slot is EMPTY (never occupied since the current table was initialized), LIVE, or DELETED (tombstone). For m slots the live load α=n/m is at most 1. Hash and equality operations cost O(1).
1. Follow the entire probe sequence
Linear probing uses h(k,i)=(h0(k)+i) mod m for i=0,...,m−1. It visits every slot once. Search follows the sequence: a matching LIVE key succeeds; another LIVE key or DELETED slot continues; EMPTY means absent. If m probes complete without a match, report absent. Explicit probe limits avoid infinite loops in a full table or one with no EMPTY slots.
To insert with unique-key semantics, remember the first DELETED slot but continue searching for an existing key. On finding the key, update it. On reaching EMPTY, insert in the remembered tombstone if any, otherwise there. If the entire sequence is scanned, use the remembered tombstone; if none exists, report full or resize. Inserting immediately at a tombstone can create a duplicate whose original lies later in the sequence.
2. Trace deletion correctly
Take m=7, h0(k)=k mod 7, linear probing. Insert 10,17,24: they occupy indices 3,4,5. Delete 17 by marking slot 4 DELETED. Search 24 probes 3,4,5 and succeeds. If slot 4 were incorrectly changed to EMPTY, that search would stop at 4 and falsely report absence. Now insert 31: scan 3,4,5,6; after reaching EMPTY at 6 and proving no duplicate along this search path, place 31 in remembered slot 4.
Tombstones preserve searches but accumulate probe cost. Live α can be small while nearly every slot is LIVE or DELETED. Rehashing into a clean table removes tombstones; merely decrementing n does not shorten the historical probe paths.
3. Probe families and coverage
Linear probing has primary clustering: contiguous occupied runs attract more insertions. Quadratic probing, for example (h0(k)+i²) mod m, can fail to visit all slots. With m=8 and h0=0 it visits only 0,1,4,1,0,..., so an empty slot elsewhere need not be reachable.
Double hashing uses (h1(k)+i h2(k)) mod m. The step must be nonzero modulo m and coprime to m to visit all slots. For m=10, step 4 visits only 0,4,8,2,6 before repeating, whereas step 3 visits all ten. A prime m with step in 1,...,m−1 ensures coprimality. “Two hash functions” by itself is not a coverage guarantee.
4. Cost assumptions and pitfalls
Under ideal uniform probing and α<1, the expected unsuccessful-search probe count is at most 1/(1−α), for a model without accumulated tombstones. This is an upper bound under a stated probabilistic assumption, not an exact count for linear probing. At α=0.75 it gives an upper bound of 4. Linear probing's clustering needs separate analysis. Worst case is Θ(m) probes; with maintained m=Θ(n), that is Θ(n).
Space is Θ(m). Unlike chaining, an entirely live full table cannot accept a new distinct key without resizing. Search can still succeed or terminate after at most m probes. A deleted slot is reusable storage but not a search terminator. Always state whether deletion markers are present before using load-factor formulas.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. After deleting 17 from slots 3:10,4:17,5:24, slot 4 should be:
A. EMPTY B. DELETED C. Always 0 D. Removed from array
Answer: B
A: Would break search for 24.
B: Tombstone preserves the probe chain.
C: 0 might be a legitimate key.
D: Changing array length changes hash indices.
P02. Linear probing, m=7, start 6: first three indices?
A. 6,7,8 B. 6,0,1 C. 6,1,3 D. 0,1,2
Answer: B
A: Indices wrap modulo 7.
B: (6+i) mod 7 gives 6,0,1.
C: This is not step-one probing.
D: The first index is 6.
P03. Double hashing m=10, step 4 visits how many distinct slots?
A. 2 B. 4 C. 5 D. 10
Answer: C
A: Cycle length is m/gcd(m,step).
B: The step is not the cycle length.
C: 10/gcd(10,4)=5.
D: Step and capacity are not coprime.
P04. When insertion meets a tombstone before checking for duplicate key, it should:
A. Immediately insert and stop B. Remember it and continue C. Mark it EMPTY and stop D. Never reuse it
Answer: B
A: Could duplicate a key later in the probe path.
B: Continue until existing key, EMPTY, or full bounded scan.
C: Would break other searches.
D: Tombstones are reusable after proper checking.
P05. Ideal uniform probing without tombstones, α=0.75: unsuccessful expected upper bound?
A. 0.25 B. 0.75 C. 3 D. 4
Answer: D
A: This is empty fraction.
B: This is load factor.
C: This is α/(1−α), not the stated bound.
D: 1/(1−0.75)=4.
P06. A full linear-probing table, absent key: correct termination?
A. Wait for EMPTY forever B. At most m probes C. One probe always D. Search must succeed
Answer: B
A: No EMPTY exists.
B: After all m slots are checked, absence is known.
C: Collisions require additional probes.
D: A full table does not contain every possible key.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in