Sort each description by the collision-resolution strategy it describes.
Groups: Chaining · Open addressing
- A lookup ends by scanning the short list at one bucket
- Each bucket holds a small list of all the keys that landed there
- The number of stored elements can exceed the number of buckets
- When the chosen bucket is taken, a fixed rule probes a different bucket
- Every key is stored directly in the bucket array itself
Hints
- One strategy stores extra keys outside the bucket array; the other keeps everything inside it.
- Ask which strategy could still work when there are more keys than buckets.
Show the answer
Chaining: Each bucket holds a small list of all the keys that landed there, The number of stored elements can exceed the number of buckets, A lookup ends by scanning the short list at one bucket
Open addressing: When the chosen bucket is taken, a fixed rule probes a different bucket, Every key is stored directly in the bucket array itself
Chaining hangs a list off each bucket, so it can hold more elements than buckets and finishes a lookup by scanning that list. Open addressing keeps every key inside the array and moves on to another bucket by a fixed rule, so it cannot hold more elements than buckets. Either way the collision must be handled, or values would overwrite each other.
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.