Every language you have ever used has a hash table hiding somewhere in it. Python calls it dict, Go calls it map, JavaScript objects and Ruby hashes are the same idea, C# has Dictionary<TKey, TValue>, and Rust offers HashMap. The names change; the machinery underneath is remarkably consistent. And yet most developers go through their entire careers using these structures daily without ever looking inside them — which is a shame, because the internals explain a long list of behaviors that otherwise look arbitrary. Why iteration order is unpredictable in one language and insertion-ordered in another. Why you cannot safely mutate a map while looping over it in Go. Why dictionary lookups in Python stay fast even when the dictionary holds a million entries.
This post walks through what actually happens when you insert and look up a key, why hash tables need to resize, and what happens when hashing goes wrong. None of it requires math beyond division.
The core trick: turn a key into an index
A hash table is an array with a detour. Instead of searching the array, you compute the key’s position from the key itself. The hash function chews the key — a string like "user:8241", a number, whatever — and spits out an integer. You take that integer modulo the array length, and that’s the slot you use:
index = hash(key) % capacityLookup is the same dance in reverse: hash the key, compute the slot, compare what you find there. If it matches, you are done. That is the entire pitch — a find operation that costs the same whether the table holds ten items or ten million, instead of scanning every one of them.
The hash function itself has one critical job: spread keys evenly. If every key lands in the same slot, you have built a linked list with extra steps. A good hash function makes similar-looking keys scatter unpredictably across the whole range of output values, and does it fast, because it runs on every single operation.
Collisions: the part that actually matters
Two different keys will eventually produce the same index — with more entries than slots it is mathematically forced, and even before that it is statistically inevitable. When that happens you have a collision, and everything interesting in hash table design flows from how you handle it.
Chaining
The classic approach: each array slot points to a small collection of entries. On collision, you append. On lookup, you hash, walk the short chain, and compare keys. Chains stay short on average — with a good hash function and a load factor kept under control, one or two entries per slot — so lookups stay effectively constant time.
Open addressing
The alternative keeps all entries inside the array itself. When a slot is taken, you probe for the next free one according to a fixed rule. The simplest rule, linear probing, just walks forward:
slot = hash(key) % capacity
while table[slot] is occupied and table[slot].key != key:
slot = (slot + 1) % capacityOpen addressing wins on cache locality — the entry you want is usually in the exact slot the hash points at, already in the CPU cache — which is why most modern implementations prefer it. Its weakness is clustering: long runs of occupied slots form, and each insertion into a cluster makes it longer. Linear probing amplifies the problem; quadratic probing and double hashing scatter subsequent probes to break clusters up.
Load factor and the resize dance
Both strategies degrade as the table fills. The threshold where an implementation decides to grow is the load factor — commonly somewhere between 0.6 and 0.75 for open addressing, higher for chaining. Cross it, and the table rebuilds itself at roughly double capacity.
The rebuild is the boring-sounding part that explains real behavior. Every entry must be rehashed and reinserted, because index = hash(key) % capacity — change the capacity, change every index. That makes resizing an O(n) pause on a structure famous for O(1) operations, and languages handle the cost differently. Go’s map internals grow incrementally, spreading the rehash across subsequent operations so no single one eats the whole bill. Others simply eat the occasional slow insert and rely on amortized analysis: spread over the table’s lifetime, inserts are still constant time on average. If you have ever seen a latency spike from one unlucky dict write, you have met the resize.
The behaviors the internals explain
Why iteration order seems random
A hash table stores entries where the hash function put them — slot 47, slot 8122, slot 190 — so walking the array in order walks them in hash order, which is arbitrary from your program’s point of view. That is why Go map iteration order famously varies run to run: Go deliberately randomizes the starting slot, because developers kept accidentally depending on the order in tests, and those tests broke when the implementation changed. Python used to have the same arbitrary order until 3.6, when it moved to a compact design that keeps a dense array of entries in insertion order alongside the sparse index — which is why dict iteration today reliably matches the order you inserted keys.
Why mutating during iteration is a trap
Once you picture the array of slots, the danger is obvious: an insert can trigger a resize, which rehashes everything into new slots, while your loop is holding positions in the old arrangement. Go’s runtime detects the mutation and panics. Python lets you read but not add keys during iteration, raising RuntimeError if the dictionary changes size. The rules differ, but they are protecting you from the same underlying machinery.
Why mutable keys are forbidden
Put a list into a dictionary key, mutate the list afterward, and the hash you recorded no longer matches the key’s current hash — the entry is now unreachable, filed under an index computed from data that no longer exists. This is why hash-based containers demand immutable (or at least hash-stable) keys, either enforced by the language — only hashable types can be Python dict keys — or by convention and crash.
HashDoS: when hashing becomes an attack surface
In 2011, a demonstration showed that because most runtimes hashed strings deterministically, anyone who could submit keys to a server could precompute keys that collide — turning every insertion into a chain walk and a small request flood into a CPU meltdown. Hash-flooding denial of service. The industry response was seed randomization: runtimes now initialize the hash function with a random per-process seed so attackers cannot predict collisions in advance. Java led the way for String.hashCode alternatives in its newer hash maps, Python adopted randomized string hashing (available earlier via -R, made default in 2012), and the technique is now table stakes across runtimes. There is a trade-off: within a single process, hashes stay consistent, so dictionaries work normally — but hash() values change between runs, which occasionally surprises anyone persisting them.
A note on identity vs equality
One subtle point: two keys that compare equal must hash equal — this is the contract every hash table depends on, because lookup compares the stored hash before it ever compares the key itself. In Python, 1 == 1.0 == True, and indeed all three hash identically and share a dictionary slot. Languages where equality is subtler — NaN, signed zero, case-folded strings — handle the corner cases explicitly. If you ever implement a custom key type, this contract is the one rule you cannot break: equal objects with different hashes make entries vanish.
Wrapping up
The next time a map misbehaves, you now have the vocabulary to interrogate it. Unpredictable iteration order? That is hash order leaking through. A latency spike on insert? Resize. A panic mid-loop? You mutated the arrangement underneath the iterator. Collisions, load factors, and the resize dance are not implementation trivia — they are the operating manual for the structure you use more than any other. Few investments pay off like understanding your most-used data structure this deeply.