Practice question · True or false
A hash table serves a workload of 90% lookups by key and 10% requests for the smallest key well, because the 90% case is O(1).
Hints
- How would a hash table find the smallest key?
- Weigh the cost of the 10% against the saving on the 90%.
Show the answer
False
Why
False. A hash table has no order, so 'smallest key' is a full O(n) scan, the 10% dominates. A balanced BST gives O(log n) for both operations and wins overall. Choosing by the most frequent operation alone is the trap; the cost of the rare operation has to be weighted in.
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…
- Sort each requirement by whether a hash table alone is enough for it.
- 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.