The hash table
Hash function, buckets, collisions and their two resolutions (chaining, linear probing), load factor and resizing, average and worst-case cost, the contract between equality and hashing of a key.
- 25 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- The numbers
- Scenarios
- Understand
A few cards from the deck
Hash function: what is it?
Show the answer
A function that turns a key into an integer, whose remainder modulo the table size gives the bucket where to store it.
It must be deterministic (same key, same value) and spread keys evenly. With
h(k) = k mod 7, key 24 goes to bucket 3.Table of 7 buckets,
h(k) = k mod 7, linear probing. We insert 10, 17 then 3, in that order. Which bucket does 3 go to?- Bucket 5
- Bucket 3
- Bucket 4
- Bucket 6
Show the answer
Bucket 5
10 takes bucket 3; 17 aims at 3, taken, and goes to 4; 3 aims at 3, then tries 4, both taken, and stops at 5.
In a properly sized hash table, search, insertion and removal cost … on average and … in the worst case.
Show the answer
In a properly sized hash table, search, insertion and removal cost O(1) on average and O(n) in the worst case.
The worst case happens when all keys land in the same bucket: the table then degenerates into a list.
Bucket: what is it?
Show the answer
A slot of the table identified by an index, which receives the keys whose hash leads to that index.
The array of m buckets is the only access structure: compute the index, look at that slot, without scanning the others.
A linear-probing table removes a key by simply emptying its bucket. Afterwards, searching for another key, inserted after it in the same run, fails. Which fix?
- Mark the bucket 'deleted', not empty
- Also empty the following buckets of the same run
- Change the hash function to avoid collisions
- Search for every key starting from bucket 0
Show the answer
Mark the bucket 'deleted', not empty
A lookup stops at the first empty bucket: if a removal creates one in the middle of a run, the keys after it become invisible. A deletion marker (tombstone) lets the lookup go on, and an insertion may reuse it.