Every language gives you one, most people use it constantly, and its performance characteristics are widely misremembered. Worth twenty minutes.
The core trick
A hash map is an array plus a function. The function turns a key into a number; the number, modulo the array length, is an index. That is the entire idea:
index = hash(key) % capacity
Array indexing is genuinely constant time, so if the hash function distributes keys evenly, lookup is constant time too. Both halves of that sentence are load-bearing.
Collisions are the normal case
Two different keys will map to the same index. This is not an edge case — with 23 keys in a 365-slot table you are already more likely than not to have a collision, which is the birthday paradox wearing a different hat.
Two strategies dominate:
Chaining. Each bucket holds a list. Collide, and you append. Lookup finds the bucket, then walks the list. Simple, degrades gracefully, costs a pointer indirection per entry — which in cache terms is not free.
Open addressing. One entry per slot. On collision, probe for another slot by a defined rule (linear, quadratic, or double hashing). Everything stays in one contiguous array, which the CPU cache likes a great deal. The cost is clustering: linear probing creates runs of occupied slots that get longer and slower, and deletion becomes awkward because you cannot just empty a slot without breaking probe chains through it — hence tombstones.
Most modern standard libraries use open addressing with careful probing, because on real hardware cache locality beats theoretical elegance.
Load factor is the number that matters
Load factor is entries ÷ capacity. As it climbs, collisions rise non-linearly, and with open addressing the curve gets vicious near the top: at 0.9, average probe counts are several times what they are at 0.5.
So implementations resize — typically doubling capacity — when load factor crosses a threshold. Resizing means allocating a new array and rehashing every existing key, because the modulo changed.
That is the part worth internalising: a single insert is usually O(1), but occasionally it is O(n). Insertion is O(1) amortised, not O(1). If you are writing latency-sensitive code, that occasional rehash is a real spike, and it will happen during your busiest moment because that is when the map grew.
Practical consequence: if you know roughly how many entries you will have, pre-size the map. You skip every intermediate rehash, and it is usually a one-line change.
When O(1) stops being true
The constant-time claim assumes your hash function spreads keys evenly. Feed it keys engineered to collide and every entry lands in one bucket, turning lookups into a linear scan.
This is not hypothetical: hash-flooding attacks did exactly this to web frameworks by posting form fields whose names all hashed to the same bucket, turning cheap request parsing into quadratic work. The fix, now standard, is a per-process random seed mixed into the hash so an attacker cannot predict collisions. It is also why you must never rely on iteration order, and why hash values are not stable across runs.
What to take away
- Pre-size when you know the size.
- A key's
hashCode/__hash__must agree with its equality. Break that and entries vanish into a map that swears it has never seen them. - Never persist a hash value or depend on iteration order.
- If keys are small integers in a dense range, an array is faster and simpler than a hash map. People forget arrays exist.