GATE CS 1996 Q1.13 — Arrays, Stacks and Queues

The correct option is C.

Let's analyze the comparison between chained hashing (external hashing) and open addressing:

• Deletion (Option C):
  • In chained hashing, deleting an element is straightforward. We simply locate the node in the linked list corresponding to the hash bucket and delete it. This operation does not affect any other elements in the hash table.
  • In open addressing, deleting an element is complex. If we simply clear a slot, it can break the probe sequence for other keys that were placed after it. To prevent this, we must use a special marker (like DELETED or a "tombstone"), which increases the complexity of subsequent search and insert operations.
• Worst-case Search Complexity (Option A): In the worst case (where all $n$ keys hash to the same slot), both schemes have a search complexity of $O(n)$. Thus, chained hashing does not have a better worst-case complexity.
• Space Efficiency (Option B): Chained hashing requires extra memory to store pointers for the linked list nodes, whereas open addressing stores elements directly within the table slots. Therefore, open addressing is generally more space-efficient.