PadhaikoAll subjects

Past exam question: 2062 Baishakh (Regular / Back), Q9

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

Define 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:

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.)

Answer:

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.

All past exam questions for Data Structure and Algorithms