- 2068 Magh · 5 marks
Hashing and collision resolution techniques
Short answer
Hashing computes a record’s address directly from its key using a hash function, giving O(1) average access. Collision resolution methods include open addressing (linear probing, quadratic probing, double hashing) where all keys stay in the table, and separate chaining where each slot holds a linked list.
Define hashing and discuss different collision resolution techniques in hashing.
Hashing is a technique where the address of a record is computed directly from its key using a hash function h(k), for example h(k) = k mod m in a table of size m. It gives O(1) average-time insertion and search. A collision occurs when two different keys give the same address, and it must be resolved.
Collision resolution techniques
1. Open addressing: every key stays in the table; if h(k) is full, a probe sequence is followed.
- Linear probing: (h(k) + i) mod m. Simple but causes primary clustering.
- Quadratic probing: (h(k) + i²) mod m. Less primary clustering, some secondary clustering.
- Double hashing: (h1(k) + i·h2(k)) mod m. Best distribution.
2. Separate chaining: each table slot points to a linked list of all keys hashing to it.
Example (m = 10, h(k) = k mod 10, keys 31, 41, 51):
| Method | 31 | 41 | 51 |
|---|---|---|---|
| Linear probing | 1 | 2 | 3 |
| Quadratic probing | 1 | 2 | 5 (1+4) |
| Chaining | slot 1 list: 31 → 41 → 51 |
Chaining never overflows but needs pointers; open addressing saves memory but needs a table larger than the number of keys.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Collision resolution techniques in hashing · Data Structure and Algorithm, chapter 8 · asked 3×
- Chaining for collision resolution · Data Structure and Algorithm, chapter 8
- Linear, quadratic probing and double hashing · Data Structure and Algorithm, chapter 8