Prefix Lookup Not Exact

An autocomplete service holds a set of stored strings. Each request supplies a query string q, and the service must return the alphabetically first stored string that is greater than or equal to q. Requests arrive faster than 10k per second and the stored set changes throughout the day.

A colleague proposes a hash set, arguing that a hash set is the fastest possible lookup structure. What is wrong with that?

The problem is mutability: hash sets cannot support deletion without tombstones, so a set that changes through the day will degrade.

A hash set implements the unordered-set operation find(x) = return an element equal to x, or nothing. This service needs find(x) = return the smallest stored element that is at least x, which is the sorted-set operation. A hash of a string tells you nothing about the hashes of the strings near it, so there is no way to recover the neighbour.

Nothing is wrong with the choice; you only need to also keep a sorted array alongside the hash set and binary search it on the rare miss.

The problem is throughput, not semantics: a hash set is $O(1)$ on average but $O(n)$ in the worst case, so the tail latency at 10k requests per second would be unacceptable.