Hash maps: buckets, load factor and rehashing

The standard's interface practically requires separate chaining. There is an array of buckets; each bucket points to a chain of nodes; each node holds one key, one value and a link to the next node, and is allocated individually.

A lookup computes hash(key) % bucket_count (or a cheaper equivalent), reads the bucket, and walks its chain comparing keys. With a good hash and a reasonable load, chains are short and a lookup is: compute the hash, one load for the bucket, one or two loads for nodes. Each of those loads can be a cache miss because the nodes are scattered.

The load factor is size() / bucket_count(). The default maximum is 1.0. When an insert would exceed it, the map rehashes: it allocates a larger bucket array, typically about twice as many buckets, and relinks every node into its new bucket.

That rehash is the answer to the question's first suspect. It walks every element, so it costs time proportional to the size of the map, and it happens inside an ordinary insert. With hundreds of thousands of orders, the insert that triggers it takes far longer than the rest. If inserts and lookups share a thread, lookups queue behind it.

The fix is the same as for vectors: reserve(n) sizes the bucket array for n elements up front, so no insert below n triggers a rehash. max_load_factor can be lowered to trade memory for shorter chains.

The second suspect is the hash. libstdc++'s std::hash for integers is the identity: the hash of 4711 is 4711. With a bucket count that is a prime number, as libstdc++ uses, that is usually fine. But keys with structure can still collide badly. Exchange order ids often encode a session, a date or a counter in fixed bit fields, and if the varying bits are the ones the bucket index ignores, many keys share a bucket and chains get long.

Long chains are a slow path that appears only for some keys, which matches tens of microseconds for a few lookups. The cure is a hash that mixes all the bits, for example a multiply-and-shift or a library's integer mixer, and checking the distribution with bucket_size on a real day's ids.

There is a security version of the same problem: if an attacker can choose keys, they can pick ones that collide. That is less of a concern for exchange-assigned ids than for anything parsed from outside input.

• Cold nodes. A node not touched for a while has been evicted from the cache, so its lookup pays a full memory access, or two if the bucket is cold as well.
• Allocation on insert. Each insert allocates a node, with all the tail-latency risks of Module 1.
• Erase and reinsert churn scatters nodes further across the heap over the day.

Open-addressing tables store entries directly in one array. A key hashes to a slot; if that slot holds a different key, the table probes nearby slots in a fixed sequence until it finds the key or an empty slot.

Modern designs such as Abseil's Swiss tables also keep a small array of control bytes with a few bits of each key's hash, and use SIMD to compare sixteen of them at once, so most lookups decide with one or two cache-line reads. There is no per-element allocation; erasing leaves a marker (a tombstone) or shifts entries back.

The trade-offs: elements move when the table grows, so pointers into it are not stable; performance degrades sharply as the table fills, so the maximum load is kept below one; and deletion is more complicated than unlinking a node.

For the slow order lookups: reserve for the day's peak, use a mixing hash, and if that is not enough, move to an open-addressing table keyed by order id that stores handles into the order pool.