Past exam question: 2079 Ashwin (Back), Q9(b)
Open in the Padhaiko appDiscuss linear probing in detail.
Solution
Concept and Mathematical Formula of Linear Probing: Linear Probing is an open-addressing (closed hashing) collision resolution technique where all records are stored directly inside the hash table array (load factor ).
When inserting a key , if the primary home slot is already occupied by a different key (a collision), the algorithm systematically probes sequentially adjacent slots in a cyclic fashion until an empty slot is discovered.
Hash Function with Probe Sequence:
where:
- is the primary hash function (typically ).
- is the probe step counter ( is the initial probe, is the first alternate slot, etc.).
- is the total capacity of the hash table.
Core Table Operations Under Linear Probing:
- Insertion (
insert(k)):- Compute .
- Inspect slot index: if empty (or marked
DELETED), place key at that position and return success. - If occupied, increment and check slot .
- Repeat until an available slot is found or all slots have been probed (Table Full).
- Searching (
search(k)):- Probe slots sequentially starting at .
- If the slot contains key , return the index (Successful Search).
- If an unoccupied (
NULL) slot is reached, search terminates immediately as key was never inserted (Unsuccessful Search). - If a slot marked
DELETEDis encountered, probing must continue because the target key could have been inserted past this slot before the deletion took place.
- Deletion (
delete(k)and the Tombstone Concept):- When key is located, its slot must not be cleared to
NULL, as doing so would prematurely terminate future searches for keys that collided and probed past this location. - Instead, the slot is marked with a special sentinel value:
DELETED(tombstone). - Insertions treat
DELETEDas available, while searches continue through it.
- When key is located, its slot must not be cleared to
Illustrative Numerical Walkthrough: Consider a hash table of size with . Insert keys: :
- Insert 15: . Slot 1 is empty place 15 at slot 1.
- Insert 22: . Collision at slot 1!
- Probe : . Slot 2 is empty place 22 at slot 2.
- Insert 8: . Collision at slot 1!
- Probe : slot 2 is occupied (22).
- Probe : . Slot 3 is empty place 8 at slot 3.
Table contents: [_, 15, 22, 8, _, _, _].
Primary Clustering Problem and Performance:
- Primary Clustering: The fundamental disadvantage of linear probing is the formation of contiguous blocks of occupied slots. Any key that hashes to any slot within a cluster extends the length of the cluster by one, increasing the likelihood of future collisions (the rich-get-richer effect).
- Time Complexity:
- With a low load factor (), average search and insertion take time:
- As the table approaches full capacity (), cluster lengths grow to , degrading performance to linear search .
- Advantage: Exceptional CPU cache locality because adjacent array elements are loaded into the L1/L2 hardware cache lines simultaneously.
Linear Probing resolves hash collisions by checking successive slots using:
- Operations: Sequential probing on insert and search; deletions require a
DELETEDtombstone to maintain probe continuity. - Trade-offs: Offers superior CPU cache performance and simple implementation, but suffers from primary clustering, which degrades runtime to at high load factors.