Hashing

Imagine a library where, instead of walking the shelves, a formula tells you the exact shelf a book sits on. You compute, you walk straight there, you grab it. That is a hash table: it runs the key through a hash function that spits out a number, and that number is the bucket where the value lives.

This is the magic behind the dictionaries, maps and sets you use every day. Insert, look up, delete — all in roughly constant time, no matter how big the table grows. No scanning, no sorting, just one arithmetic jump.

But the magic has a crack. Two different keys can hash to the same bucket — a collision — and when they pile up, that one-step lookup quietly starts to crawl. Understanding when and why is the whole story of hashing.

Below is a tiny hash table with a handful of buckets. Each key you add is run through a simple hash function and dropped into a bucket. When two keys land in the same bucket they chain together — that is a collision.

<p class="hint">{{hint}}</p>
<div class="row">
  <input id="key" type="text" placeholder="{{placeholder}}" maxlength="12" />
  <button id="ins" type="button">{{btn_insert}}</button>
  <button id="rand" type="button">{{btn_rand}}</button>
  <button id="resize" type="button" class="ghost">{{btn_resize}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div class="stats" id="stats"></div>
<div id="table" class="table"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.row { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .6rem; }
input { font: 500 14px system-ui, sans-serif; padding: .4rem .6rem; border: 1px solid #adb1b8;
        border-radius: 8px; width: 130px; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats { font-size: .92rem; font-weight: 600; margin: .3rem 0 .7rem; display: flex; gap: 1.2rem; flex-wrap: wrap; }
.stats .warn { color: #c92f3c; }
.stats .good { color: #0a7d33; }
.table { display: flex; flex-direction: column; gap: 4px; }
.bucket { display: flex; align-items: center; gap: 6px; }
.idx { width: 34px; height: 34px; flex: none; display: flex; align-items: center; justify-content: center;
       font: 700 14px ui-monospace, monospace; background: #e8eef3; color: #1d3557;
       border: 1px solid #cdd9e3; border-radius: 8px; }
.chain { display: flex; gap: 4px; flex-wrap: wrap; min-height: 34px; align-items: center; }
.chip { padding: .28rem .55rem; font: 600 13px system-ui, sans-serif; border-radius: 7px;
        background: #c9ccd1; border: 1px solid #adb1b8; }
.bucket.collide .chip { background: #e63946; border-color: #c92f3c; color: #fff; }
.bucket.collide .idx { background: #f7d6d9; border-color: #e0a8ad; }
.arrow { color: #888; font-size: .8rem; }

// Code not found

Watch the load factor (items ÷ buckets) climb as you insert. While it stays low, almost every bucket holds one item and lookup is effectively one step. Push it past 1 and chains grow, so a lookup must walk a list — drifting toward $O(n)$. Hit Resize and the table doubles its buckets, re-hashes everything, and the chains melt away. That trade — extra space for fast access — is hashing in one move.

How fast is a hash table, really? The honest answer has two numbers.

• Average case: $O(1)$. If the hash spreads keys evenly and the load factor α (items ÷ buckets) is kept bounded, the expected chain length is about α, so insert, find and delete all run in expected constant time. This is solved, well-understood textbook theory — not an open problem.
• Worst case: $O(n)$. Nothing stops every key from hashing to the same bucket. Then the table collapses into one long chain and a lookup scans all n items, just like an unsorted list.
• Collisions are unavoidable. By the birthday problem, collisions appear far sooner than intuition says: with only ~23 keys in a 365-bucket table the odds of some collision already exceed 50%. Hashing never promises no collisions — only that they stay rare and cheap.
• The defense is randomness. Universal hashing (Carter & Wegman, 1979) picks the hash function at random from a family, so no fixed set of keys can be engineered to always collide — turning the worst case into a bad-luck event with provably low probability.

So $O(1)$ is a statement about the average under a good hash and a controlled load factor. Keep α small and you live in the fast world; let it grow, or let an adversary pick your keys, and you slide toward the slow one. It is a vivid lesson in why P vs NP and complexity classes care about worst case versus average case.

"Find this exact thing, fast" is one of the most common demands in computing, and hashing is the default answer:

• Dictionaries and sets: every dict, map, HashMap or Set in your language is a hash table under the hood.
• Databases and indexes: hash indexes give $O(1)$ equality lookups; joins and grouping lean on hashing to bucket matching rows.
• Caches and deduplication: content is keyed by hash so identical data is stored once and found instantly (Git, build caches, CDNs).
• Compilers and interpreters: symbol tables map variable names to information through hashing on every single line you compile.
• Bloom filters and probabilistic structures: hashing also underpins compact membership tests where a little error buys huge space savings — see bloom filters.

Learn how a hash table degrades and recovers and you understand the load-factor knob behind nearly every fast data store you will ever touch.

Hashing is one of computing's best bargains: spend a little extra memory and a clever formula, and you get lookup that barely cares how much data you hold. The catch is honest and simple — that speed is an average, propped up by keeping collisions rare. Let the load factor climb, and the one-step jump degrades into a walk down a chain.

The fix is equally simple: watch α, resize in time, and pick a hash that scatters keys well. Do that and the table keeps its promise. It is a small structure with a big lesson — the gap between the typical cost and the worst cost, the same gap that runs through all of P vs NP and the study of algorithms.