Why is a hash map keyed by timestamp wrong for "latest slot at or before a given time"?

## The requirement that breaks the default A booking service stores appointment slots keyed by timestamp. Exact lookups — "is there a slot at exactly 14:00?" — are answered in expected O(1) by a hash map, and for a while the hash map looks like the obviously correct choice. Then a requirement arrives: given a requested time, return the latest slot at or before it. Nothing about the data changed, but the structure is now the wrong one, and the code that results looks like this: ``` # slots: hash map from timestamp -> slot_id best = NONE for t in keys(slots): if t <= requested: if best == NONE or t > best: best = t ``` Every key is inspected for a single query. The hash map has not slowed down; it simply never offered this operation, and the scan is the price of asking for it anyway. ## Why hashing cannot answer it A hash function's job is to spread keys uniformly across buckets so that distinct keys rarely collide. Good spreading means 13:59 and 14:00 land in unrelated buckets — that is not an unfortunate side effect, it is the goal. There is therefore no cheap way to walk from a key to its neighbour in value order, because the structure does not know what "neighbour in value order" means. Two consequences follow: predecessor and successor queries cost O(n), and so does any range query ("all slots between 09:00 and 12:00") and any ordered iteration. It is also worth being precise about what the hash map *does* promise. Exact lookup is O(1) *expected* and amortized across resizes, not O(1) unconditionally: with many keys hashing to the same bucket the worst case is O(n), and if an adversary can choose the keys they can provoke it. "Hash lookup is O(1), so it is always the fastest choice" is wrong twice over — about the bound, and about the set of operations the bound covers. ## The structures that do answer it **Balanced search tree.** Keys are held in order; each node's left subtree is smaller and right subtree larger. A predecessor query walks down from the root, remembering the last node not greater than the target — O(h) where h is the height, and a balancing rule (red-black, AVL) keeps h in O(log n). It also gives successor, ordered iteration, and a range scan of k results in O(log n + k). Inserts and deletes are O(log n). The cost against a hash map is roughly a factor of log n on the exact-lookup path, plus pointer chasing that is less cache-friendly than a contiguous block. **Skip list.** Same operation set and the same O(log n) expected bounds, achieved with randomised levels instead of rotations. It is often chosen when concurrent access matters, because the local updates are simpler to make safe. **Sorted array with binary search.** Predecessor is a binary search for the insertion point, then step one back: O(log n) with excellent constants and locality, because the whole search touches one contiguous block. Ranges are trivially a slice. The catch is mutation: inserting into the middle shifts on average n/2 elements, so this is the right choice when the slot table is built once and read many times, or rebuilt periodically, and the wrong one when slots are created and cancelled continuously. **Bucketing by time.** If slots are dense and the domain is bounded — say, one entry per five-minute interval of a day — an indexed array of buckets answers predecessor by walking backwards from the computed index, which is O(1) when the data is dense and degrades toward O(n) when it is sparse. Cheap, but it is a bet on the distribution. ## Mainstream libraries have made different calls This is one of the places where ecosystems visibly diverge: the Java and C++ standard libraries both ship an ordered map backed by a balanced tree alongside the hash map, so the fix is a one-word type change, whereas Python and Go ship only the hash-based map and leave ordered lookup to a sorted sequence with binary search or to an outside library. The concept is the same everywhere — the point is that ordered lookup is a *different structure*, not a flag on the one you already have. ## How to spot it in a requirement The cue is a comparison where you expected an equality. "At or before", "the next one after", "everything between", "the smallest that is at least", "in order" — every one of these is an order query, and every one of them disqualifies a pure hash map. Conversely, if the only comparison in the requirement is equality on a key, ordering buys nothing and you should not pay log n for it. Some designs genuinely need both profiles, and then the real decision is whether to accept O(log n) from one ordered structure or to maintain a hash index next to it — a second structure that every mutation path must keep consistent.