Practice question · Put in order
Order the steps a hash table takes to look up a value by its key, using chaining.
- Apply the hash function to the key to get an integer
- Search the short list held at that bucket for the matching key
- Reduce that integer modulo the number of buckets to get an index
- Jump straight to the bucket at that index
- Return the value stored alongside that key
Hints
- The lookup never scans the table; the index must be computed before anything is read.
- The list search only exists because collisions put several keys in one bucket.
Show the answer
- Apply the hash function to the key to get an integer
- Reduce that integer modulo the number of buckets to get an index
- Jump straight to the bucket at that index
- Search the short list held at that bucket for the matching key
- Return the value stored alongside that key
Why
Hashing and the modulo give an index with no memory reads at all, which is why the jump is direct; only then is the bucket's short chain searched. The whole cost is that final search, so keeping chains short, which is what the load factor and resizing control, is what keeps lookup constant on average.
Practise Hashing and Dictionaries
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.