Hash maps

A hash map stores key-value pairs. A hash function turns each key into a number, and the number picks a bucket in an array. A lookup computes the hash, goes to that bucket, and compares keys. With a good hash and enough buckets, the average lookup is O(1), which is why hash maps are everywhere: caches, indexes, dedupe sets and symbol tables.

The average case is the one you should plan for, not the worst. The worst case depends on collisions, and collisions can be engineered.

The big idea

Two parts drive performance:

• Load factor is the number of entries divided by the number of buckets. As it rises, buckets hold more entries, and lookups scan more of them.
• Collision handling decides what happens when two keys land in the same bucket. Chaining stores a list per bucket. Open addressing probes other slots in the same array.

Most implementations resize when the load factor passes a threshold, often around 0.75, and rehash every entry into a bigger array. That resize is a latency spike, and it's why a hash map under heavy write load can stall for a moment.

Walking through it

Here is how a lookup goes in a chained table with 8 buckets:

key "user:42"  → hash → 0x9f3a...  → bucket 0x9f3a % 8 = 2
bucket 2: [("user:17", ...), ("user:42", ...)]
compare keys in the bucket → found "user:42"

Two keys share bucket 2, so the lookup compares up to two keys. At load factor 0.75, a typical lookup compares only a few keys. Nothing here is O(n), so the average stays constant.

Modern tables use open addressing with compact layouts. Google's Swiss table design, used in Abseil and Rust's standard HashMap, stores control bytes in a separate array, so most probes check a byte instead of a full key. This reduces cache misses, which is the same locality idea from arrays and memory layout.

When hash maps degrade

Assume an attacker controls keys, such as HTTP header names or JSON object fields. They can send many keys that all hash to the same bucket. The lookup cost then grows with the number of keys, so inserting n keys costs about n(n−1)/2 comparisons:

n = 100,000 colliding keys
comparisons ≈ 100,000 × 99,999 / 2 = 4,999,950,000

About five billion comparisons is enough to tie up a CPU core for seconds, and a few such requests can stall a server. This is hash flooding, and it was a real denial-of-service attack against many web frameworks in 2011.

The defense is a keyed hash. Each process picks a random secret key at startup, and the hash depends on it, so an attacker can't predict collisions. SipHash is the common keyed function for this. Languages that expose hash maps to untrusted input use it by default, and you should not swap it for a faster unkeyed hash on those paths.

Common mistakes

• Using a plain integer or a fast unkeyed hash for keys that come from users.
• Letting the load factor climb under write load, with no resizing budget.
• Assuming O(1) means fast enough for a hot path. Constant factors and cache misses matter.
• Iterating over a hash map and assuming a stable order.

Check yourself

• Why does a keyed hash stop hash flooding? Answer: the secret key is random per process, so an attacker can't compute keys that collide in the victim's table.
• Why does a lookup stay O(1) on average at a load factor of 0.75? Answer: each bucket holds about 0.75 entries on average, so a lookup compares only a few keys.

Key takeaways

• Hash maps give O(1) average lookups by mapping keys to buckets.
• The load factor and collision strategy set the real cost, and resizing causes pauses.
• Untrusted keys need a keyed hash, or an attacker can force O(n) lookups.

Further learning

Next, see heaps and top-k for keeping the largest items when you can't sort everything.