Past exam question: 2062 Baishakh (Regular / Back), Q9
Open in the Padhaiko appDefine clustering in rehashing method. Is it possible to remove clustering by quadratic probing? Explain. Outline an algorithm to delete a key from a hash table when the linear probing is used for inserting keys.
Solution
Clustering & Quadratic Probing:
- Clustering: In open-addressing ("rehashing") hash tables, primary clustering (in linear probing) is the tendency of colliding keys to form long contiguous runs of occupied slots; any key hashing inside a block must scan to its end and extends the block further.
- Does Quadratic Probing Remove Clustering?
- It eliminates primary clustering, because consecutive probes jump by quadratic offsets instead of filling adjacent slots sequentially.
- However, it does not remove secondary clustering: two distinct keys that share the exact same initial hash still follow the exact same probe sequence. (Only double hashing eliminates both.)
Deletion Algorithm in Linear Probing (Using DELETED Tombstone Sentinel): In linear probing, resetting a deleted slot directly to EMPTY would break search probe chains for keys inserted past that slot. Instead, mark freed slots as DELETED (TOMBSTONE):
Algorithm LINEAR_DELETE(HT, m, key):
1. h0 = key % m
2. For i = 0 to m - 1:
idx = (h0 + i) % m
If HT[idx] == EMPTY:
Return FALSE // key not in table; stop probing
If HT[idx] == key:
HT[idx] = DELETED // tombstone preserves later probe chains
Return TRUE
3. Return FALSE
(Search skips over DELETED slots and stops only at EMPTY, while insertion can reuse DELETED slots.)
Clustering is the buildup of occupied probe runs; quadratic probing eliminates primary clustering but still exhibits secondary clustering for keys sharing the same initial hash. Deletion in linear probing replaces the removed key with a DELETED (tombstone) marker so subsequent probe chains remain unbroken.