Past exam question: 2066 Bhadra (Regular / Back), Q9
Open in the Padhaiko appWhat is clustering? Explain any three collision resolving scheme with example if applicable. What are the differences between hashing and binary tree search?
Solution
What is Clustering? In open-addressing hash tables, clustering is the tendency of colliding keys to form long contiguous runs of occupied slots (primary clustering in linear probing) or share identical probe chains (secondary clustering in quadratic probing), degrading average lookup time toward .
Three Collision Resolution Schemes (, ):
- Separate Chaining: Each bucket
HT[i]holds a linked list of colliding keys (e.g.,12, 22HT[2] -> 12 -> 22). - Linear Probing: Probes sequentially (e.g.,
12at slot2,22at(2+1)=3). - Quadratic Probing: Probes (e.g.,
12at slot2,22at(2+1)=3,32at(2+4)=6).
Hashing vs. Binary Search Tree (BST):
| Aspect | Hashing | Binary Search Tree (BST) |
|---|---|---|
| Average Search Time | (balanced) / (skewed) | |
| Ordering | Unordered; no range queries or sorted traversal | Sorted order; supports range queries, min/max, in-order |
| Memory Efficiency | Extra empty table slots needed for low load factor | Allocates exact nodes needed |
Clustering is the growth of contiguous occupied probe runs in open addressing. Three collision resolution schemes are separate chaining, linear probing, and quadratic probing. Hashing gives average lookup without ordering, while BSTs give balanced lookup with sorted traversal and range queries.