Chaining and Performance
Separate Chaining
Separate chaining stores all keys colliding at the same position in a single singly linked list.
For the sequence {47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21}, use h(key) = key % 11 and separate chaining to resolve collisions.
Separate chaining
KNOWLEDGE QUIZ
Chaining: head insertion and pointer changes
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
Performance Analysis
Average search length (ASL) measures hash-table lookup efficiency. The number of key comparisons depends on collisions. Three factors affect the number of collisions:
-
Whether the hash function distributes keys uniformly
-
The collision-resolution method
-
The load factor
For open addressing, a reasonable maximum load factor is usually no greater than 0.85; separate chaining can have a load factor above 1. An appropriate hash function can make expected lookup time a constant , almost independent of the number n of keys. This assumes a sufficiently small , so a hash table trades space for time.
Hash-table storage does not preserve key order, making ordered searches, range searches, and maximum/minimum queries inconvenient.
KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Chaining: head insertion and search cost
Start with 7 empty buckets and insert 32, 39, 46, 10, 17, 24 in order, using h(key) = key % 7. Use only separate chaining, inserting colliding nodes at the head.
- Calculate each bucket index, show changes to X.next and the bucket head, and draw the chain after each insertion.
- Draw the final hash table and calculate its load factor.
- Assume equally likely successful searches for all six keys. Counting only node-key comparisons, calculate ASL.