How Hashing Works

"There are only two hard things in Computer Science: cache invalidation and naming things." — Phil Karlton

There is a third hard thing hiding behind the joke, and you use it a hundred times a day without noticing: turning a name into a place. When you write user["email"] or seen.has(x), something has to translate that key — a string, a number, an object — into an address it can jump to directly. Do it well and lookups are instant no matter how much data you have. Do it badly and your "fast" map quietly degrades into a linear scan. That machinery is hashing, and it is the single most useful idea you can carry into a coding interview: a startling number of "make this faster" problems are solved by the same move — remember it in a hash map instead of searching for it again.

Core Concepts

Start with the problem. You have a pile of key–value pairs and you want to look one up by key. In a plain array, finding a key means checking entries one by one — O(n). Keep the array sorted and binary search gets you to O(log n), but now every insert has to shuffle elements to stay sorted. Both scale with n. We want something that does not care how big n is: given a key, go straight to its value.

The trick is to make the key compute its own address. If keys were small integers — say, always 0 to 9 — this is trivial: use an array of size 10 and store the value for key k at index k. Reading it back is arr[k], one step, O(1). Hashing is what makes that trick work for any key: strings, big numbers, objects.

The mechanism: key → integer → bucket

Two stages turn an arbitrary key into an array index:

1. A hash function maps the key to an integer — the hash code. This is a deterministic scramble: same key in, same number out, every time.
2. That integer is squeezed into the range of a fixed-size array (the bucket array) with modulo: index = hashCode % numberOfBuckets.

Store the pair at that index; to read it back, recompute the index the same way and look. Here is a tiny string hash so you can watch keys land in buckets:

Five names, five different buckets, computed directly from the letters — no searching. The multiplier 31 mixes the characters so that "Ada" and "Ana" land far apart despite sharing letters; that mixing is the whole art of a hash function.

What makes a hash function good

Three properties, and each one is load-bearing:

• Deterministic — the same key must always produce the same code, or you could never find what you stored.
• Uniform — codes should spread evenly across the buckets. This is the property people underestimate. If a hash sends most keys to the same few buckets (clustering), those buckets grow long and lookups slow down — you have quietly rebuilt the O(n) scan you were trying to escape.
• Fast — hashing happens on every single operation. A brilliant distribution that takes a millisecond to compute is worthless for a hash map (cryptographic hashes like SHA-256 are uniform but deliberately slow, so they are the wrong tool here).

Uniformity is why we multiply by a prime like 31 and why table sizes are chosen with care. A lazy hash — say, "use the first letter" — clusters every "S" name into one bucket. Distribution, not cleverness, is the goal.

Collisions are not a bug — they are a certainty

Squeeze many possible keys into a fixed number of buckets and, sooner or later, two different keys produce the same index. This is the pigeonhole principle: if you have more pigeons than holes, some hole holds two pigeons. There are billions of possible strings and only a handful of buckets in our example above — collisions are guaranteed, not unlucky. A hash map is not defined by avoiding collisions; it is defined by handling them gracefully. Two strategies dominate:

Separate chaining — each bucket holds a small list. On collision, you append to that bucket's list; on lookup, you hash to the bucket and scan its (short) list. Simple, forgiving, and the model most people picture. Let us build a minimal one and watch it work:

Notice get still scans a bucket — but a bucket, not the whole map. As long as buckets stay short, that scan is effectively constant.

Open addressing — keep one flat array and, on collision, probe for the next free slot by a fixed rule. Linear probing tries index+1, index+2, …; quadratic probing tries index+1, index+4, index+9, … to avoid long runs clumping together; double hashing uses a second hash function to decide the step size. Lookup replays the same probe sequence until it finds the key or an empty slot. Open addressing packs everything into one contiguous array — friendlier to the CPU cache and memory — but it is fussier: deletions need "tombstone" markers, and it degrades sharply as the table fills.

Load factor and resizing — how O(1) is kept honest

The load factor is n / numberOfBuckets — average items per bucket. As you insert more keys into a fixed number of buckets, chains lengthen and every operation creeps toward O(n). The fix is to grow the table: when the load factor crosses a threshold (commonly 0.75), allocate a larger bucket array — usually double — and rehash every existing key into it, because the bucket index depends on numberOfBuckets and that number just changed.

Rehashing is an O(n) event. But it happens rarely — each resize doubles capacity, so the cost is spread thin across all the cheap inserts between resizes. This is amortized analysis (the same reasoning that made dynamic-array append O(1) amortized): occasional expensive operations, averaged over the many cheap ones, give an O(1) amortized cost per insert. Keep the load factor bounded and hashing stays fast; let it climb and it does not.

The honest complexity: average O(1), worst case O(n)

Say it plainly, because interviewers listen for exactly this nuance: hash-map get, put, and delete are O(1) on average and O(n) in the worst case. The worst case is when every key collides into one bucket — then the structure is just a list wearing a map's clothing, and every operation scans it. In practice a good hash function plus a bounded load factor makes that case astronomically unlikely, which is why we rely on O(1) daily. But "unlikely" is not "impossible": adversaries have crashed real servers by deliberately sending keys that all collide (a hash-flooding denial-of-service attack), which is why serious runtimes now randomize their hash seed. The average case is the promise; the worst case is the fine print — and knowing both is the difference between reciting "hash maps are O(1)" and actually understanding them.

Common Mistakes

• Claiming hash maps are "always O(1)." They are O(1) average, O(n) worst case. In an interview, say both — the qualifier is the point being tested.
• Forgetting to re-index on modulo change. The bucket is hashCode % numBuckets. After resizing you must rehash every key, because the index depended on the old bucket count. Skip it and lookups silently miss.
• Using mutable objects as keys. If a key's contents (and thus its hash) change after insertion, you can never find it again — it now hashes to a different bucket than where it lives. Keys must be effectively immutable.
• Ignoring the load factor. A map that never resizes turns into a linked list as it fills; a map that resizes too eagerly wastes memory. The threshold (~0.75) is a deliberate time-vs-space trade.
• Assuming iteration order. A hash map's storage order follows bucket indices, not insertion — treat ordering as unspecified unless the structure explicitly guarantees it (some, like JavaScript's Map, do; most classic hash tables do not).
• Reinventing the hash function. "First character" or "string length" cluster horribly. Use the language's built-in keying (or a proven polynomial hash); do not hand-roll a weak one.

Interview Corner

Chapter Summary

• Hashing gives O(1) average lookup, insert, and delete by key — the mechanism behind every Map, Set, and object.
• The pipeline is key → hash function → integer → % buckets → bucket index, letting you jump to a value instead of scanning for it.
• A good hash function is deterministic, uniform, and fast; poor uniformity causes clustering, which drags operations back toward O(n).
• Collisions are inevitable (pigeonhole principle) and are resolved by separate chaining (a list per bucket) or open addressing (probe for a free slot: linear, quadratic, double hashing).
• Load factor (n / buckets) governs speed; crossing the threshold triggers a resize + rehash, which is O(n) but rare — giving O(1) amortized inserts.
• Be honest about complexity: hash operations are O(1) average, O(n) worst case (all keys collide) — stating both is an interview signal.

Editorial reflection — it is tempting to treat hashing as a solved black box — and most days you should, because the runtime's version is better than the one you'd write. But the engineers who understand what is inside the box are the ones who reach for it at the right moment, choose keys that stay findable, and know why the "instant" lookup occasionally isn't. Learn the mechanism not to reimplement it, but so that when a profiler points at a slow map, you already know which of the machine's assumptions just broke.