Sort each requirement by whether a hash table alone is enough for it.
Groups: A hash table handles this well · Needs an ordered structure instead
- Find the smallest id greater than a given one
- Delete the record stored under a known id
- Report every id between 1000 and 2000
- Print all records in ascending id order
- Check whether an id has already been used
- Fetch the record stored under a known id
Hints
- A hash table can answer questions about one key it is given, and nothing about how keys relate to each other.
- Three of these requirements mention a comparison between keys rather than a single exact key.
Show the answer
A hash table handles this well: Fetch the record stored under a known id, Check whether an id has already been used, Delete the record stored under a known id
Needs an ordered structure instead: Report every id between 1000 and 2000, Print all records in ascending id order, Find the smallest id greater than a given one
Exact-key fetch, membership and deletion are all single-key questions, which is precisely what hashing makes constant. Ranges, sorted output and successor queries all compare keys to one another, and hashing destroys that relationship by design. The dividing question is always: does the operation name one key, or a relation between keys?
Practise Choosing a Data Structure by Workload
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Choosing a Data Structure by Workload
- The lesson's rule is to choose a structure by which operations dominate the workload. Why is 'which structure…
- A hash table serves a workload of 90% lookups by key and 10% requests for the smallest key well, because the…
- Order the steps of choosing a data structure by workload, as the lesson describes it.
- A cache needs fast lookup by key and eviction of the least recently used entry. No single structure does…
- Select every statement the lesson supports about choosing structures.