Everyone reaches for the hash map. O(1) lookup — can't beat that, right? Wrong.
For most production lookups, a flat array with a linear scan is faster. I've seen this matter in real systems. Not because Big-O is a lie. Because Big-O describes the shape of the curve, not the constant factor. A hash map pays a hashing cost on every call. Its bucket array scatters across memory — cache miss after cache miss. A small flat array fits in one or two cache lines. The CPU prefetches it for you. Chandler Carruth demonstrated this concretely at CppCon 2014 — linear search beating hash-map lookup for small but realistic N. Not in theory. In measured wall-clock time.
Think about what most production lookups actually touch: a short config list, a few dozen enum values, an in-memory cache with 20 entries. That's not large N. That's small N, every time. Big-O tells you what happens as N grows unbounded. Most of your data will never get there. Profile before you optimize for an asymptote your code will never reach.
Top comments (0)