PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q9(b)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

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

Core Table Operations Under Linear Probing:

  1. 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).
  2. 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 DELETED is encountered, probing must continue because the target key could have been inserted past this slot before the deletion took place.
  3. 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 DELETED as available, while searches continue through it.

Illustrative Numerical Walkthrough: Consider a hash table of size with . Insert keys: :

Table contents: [_, 15, 22, 8, _, _, _].

Primary Clustering Problem and Performance:

Answer:

Linear Probing resolves hash collisions by checking successive slots using:

All past exam questions for Data Structure and Algorithms