Always reach for the asymptotically-optimal data structure — challenged

Most developers instinctively gravitate towards hash maps for data structures. They tout an O(1) lookup time, seemingly unbeatable. But is this always the case? In practical production systems, the answer can be a resounding no.

Real-world testing has shown that a simple flat array with linear scanning often outperforms hash maps. This isn't due to an erroneous understanding of Big-O notation, but because Big-O only describes the general behavior of an algorithm, not the constant factors that matter in real-world scenarios.

Hash maps incur a hashing cost with every lookup. Their bucket arrays are scattered across memory, leading to frequent cache misses. In contrast, a compact flat array fits neatly into one or two cache lines. Modern CPUs are smart enough to prefetch such data, giving it a performance edge.

Chandler Carruth, a prominent figure in the field, demonstrated this phenomenon at CppCon 2014. He showed that for small but realistic datasets, linear search could outpace hash map lookups. This wasn't theoretical speculation; it was backed by concrete, measured wall-clock time results.

When considering data structures for production use, it's crucial to profile and understand the actual size of the data you're dealing with. Most of the time, you're not working with large N. Instead, it's small N – think of a short config list, a few dozen enum values, or an in-memory cache with just 20 entries. These are the typical scenarios you'll encounter in most applications.

Big-O notation is a useful theoretical tool, but it should not dictate your choice of data structures in real-world applications. Always profile your code and optimize for the constants that matter in your specific context. Reach for the asymptotically-optimal data structure only if it truly makes a difference in your particular use case.