Linear search beats hash maps for small datasets, study of real systems shows

A software engineering analysis challenges the common assumption that hash maps are always the fastest lookup structure due to their O(1) complexity. For small, realistic datasets — such as short config lists or in-memory caches with a few dozen entries — flat arrays with linear scans can outperform hash maps in actual wall-clock time. Hash maps incur hashing costs and scattered memory access that cause frequent CPU cache misses, while small flat arrays fit within one or two cache lines and benefit from CPU prefetching. Chandler Carruth demonstrated this empirically at CppCon 2014, showing linear search beating hash-map lookup for small but realistic input sizes. The key takeaway is that Big-O notation describes asymptotic behavior, not constant factors, and developers should profile their code before optimizing for data scales their applications may never reach.