A hash table is the reason Map.get(key), a Python dict lookup, and a Java HashMap all run in average O(1) time regardless of how many entries they hold. The mechanism is simpler than it gets credit for: an array of "buckets," plus a function that turns any key into an index into that array. This post builds that mechanism from scratch, with every number in it verified against the exact algorithm running in Hash Table Visualizer — nothing here is hand-waved.
The core idea: turn a key into an array index
An array gives O(1) access, but only by numeric index — arr[3], not arr["username"]. A hash table closes that gap with a hash function: a function that takes any key and deterministically produces a number, which then gets reduced to a valid array index with hash % numBuckets. Insert, lookup, and delete all become "compute the index, go straight there" instead of a search — which is exactly where the average O(1) comes from.
A real hash function, folded one character at a time
Hash Table Visualizer uses a classic polynomial rolling hash — the same shape of algorithm behind Java's String.hashCode() — folding in one character at a time:
function computeHash(key) {
let hash = 0;
for (const char of key) {
hash = (hash * 31 + char.charCodeAt(0)) % 1_000_003;
}
return hash;
}31 is the multiplier — a small odd prime, which spreads similar keys apart well in practice. 1,000,003 is a modulus applied after every character, genuinely prime, keeping the running number bounded instead of growing without limit for a long key. Tracing "map" through it by hand, character by character:
| Step | Char | Code | Running hash |
|---|---|---|---|
| 1 | m | 109 | (0 × 31 + 109) mod 1,000,003 = 109 |
| 2 | a | 97 | (109 × 31 + 97) mod 1,000,003 = 3,476 |
| 3 | p | 112 | (3,476 × 31 + 112) mod 1,000,003 = 107,868 |
With 8 buckets, "map" lands on 107,868 mod 8 = 4. Typing the same key into Hash Table Visualizer reproduces this exact trace, character reveal and all — it isn't a simplified stand-in for the real algorithm, it is the real algorithm.
Collisions are inevitable — separate chaining handles them
With a fixed number of buckets and an unbounded number of possible keys, two different keys landing in the same bucket — a collision — isn't a bug, it's pigeonhole-principle guaranteed to happen eventually. The visualizer (and this diagram) uses separate chaining: each bucket holds a small list, and a collision just means appending to that list instead of overwriting anything.
8 buckets, 6 real keys, computed with the exact hash function above — bucket 2 and bucket 5 each hold a genuine two-way collision; the rest sit at zero or one entry.
Looking up a key that collided means walking that bucket's short list comparing keys — still fast as long as chains stay short, which is exactly what keeping the bucket count proportional to the entry count is for.
The other family: open addressing
Separate chaining isn't the only answer. Open addressing keeps every entry directly in the bucket array itself — no chains, no extra allocations — and resolves a collision by probing for the next open slot according to a fixed rule:
- Linear probing — try
bucket + 1, then+2, and so on. Simple and cache-friendly (the next slot to check is already likely in the same cache line), but prone to clustering — occupied slots clump together, which makes the next collision in that area even more likely. - Quadratic probing — try
bucket + 1²,+2²,+3². Spreads probes out faster, reducing clustering at the cost of a slightly less cache-friendly access pattern. - Double hashing — use a second, independent hash function to decide the probe step size itself, so different keys colliding on the same bucket don't even follow the same probe sequence. Best collision behavior of the three, at the cost of computing two hash functions per operation instead of one.
Every open-addressing variant shares one hard requirement chaining doesn't have: the table can never be allowed to fill completely, since an insert needs at least one open slot to probe into — chaining, by contrast, can technically keep accepting entries into ever-longer chains even past 100% full, just slower.
Load factor and resizing
Load factor is entries ÷ buckets — the single number that predicts average chain length, and therefore average lookup cost. A real hash table doesn't let this number grow unbounded: Java's HashMap, for instance, documents a default load factor threshold of 0.75 — once entries ÷ buckets crosses that, the table allocates a larger backing array (typically double the size) and rehashes every existing entry into it, since hash mod numBuckets gives a different answer once numBuckets changes. That rehash is an O(n) operation, but — same reasoning as Array.prototype.push in Big O Notation Explained with Real Examples — it happens rarely enough, relative to how many cheap inserts occur between resizes, that the amortized cost per insert stays O(1). Hash Table Visualizer exposes the same lever manually: drag its bucket-count slider down while keeping the same keys, and watch the "Load factor" and "Longest chain" stats climb together in real time.
Why "average O(1)" has a worst case of O(n)
Every guarantee above assumes the hash function spreads keys roughly evenly across buckets. Nothing stops every key from landing in the same bucket — a pathological input, or a badly-designed hash function, degrades a hash table into exactly one thing:
Longest chain: 2. Looking up any key touches at most 2 entries.
Longest chain: 6 — every lookup now scans the whole chain, one entry at a time.
A single bucket holding every entry is a linked list — see Array vs Linked List for exactly what that costs: O(n) to find anything, no better than never having hashed at all. This isn't just theoretical — a hash-flooding attack deliberately submits keys engineered to collide under a known, predictable hash function, turning an API endpoint that inserts user-supplied keys into a hash table into an accidental O(n²) denial-of-service surface. It's exactly why production language runtimes (V8, CPython, and others) randomize their hash seed per process — the same key produces a different hash on every run, so an attacker can't precompute a colliding set in advance.
What a hash table needs from its hash function — and what it doesn't
A good hash table hash function needs to be fast (computed on every single operation) and produce a uniform spread across buckets (avoiding clusters that create long chains). It does not need to be a cryptographic hash function — those solve a completely different problem: collision resistance against a deliberate adversary and one-way irreversibility, both of which cost far more compute than a hash table can afford to spend on every get() call. Running SHA-256 on every hash table lookup would work, but it's solving for a threat model a hash table doesn't have — the hash-seed randomization above is the actual, proportionate defense against a hostile key set.
Complexity cheat sheet
| Operation | Average case | Worst case |
|---|---|---|
| Insert | O(1) | O(n) |
| Lookup | O(1) | O(n) |
| Delete | O(1) | O(n) |
| Resize (amortized per insert) | O(1) | — |
Try it yourself
Hash Table Visualizer runs every example in this post live — insert or look up a key and watch it hashed character by character, folded to a bucket index, and either slotted in or chained onto a collision, with the bucket-count slider to explore load factor directly. Binary Search Tree Visualizer and Heap Visualizer cover the ordered alternatives — a hash table gives up all ordering for its average O(1), where a BST keeps full sorted order at O(log n), and a heap keeps only the single best value accessible at O(1).
FAQ
Is a hash table the same thing as a hash function?
No — the hash function is one ingredient. A hash table is the whole structure: the bucket array, the hash function that maps keys into it, and the collision-resolution strategy (chaining or open addressing) that handles the inevitable overlaps.
Do JavaScript objects and Python dicts preserve insertion order? Doesn't that contradict how hash tables work?
They do preserve order today, but it's a guarantee layered on top of the hash table, not a natural property of one. Modern JavaScript engines track insertion order separately and iterate string keys in that order (with integer-like keys sorted first — a specified, deliberate exception); CPython's dict has kept insertion order since 3.7 via a compact internal layout that's explicitly not just "a bucket array, iterated in bucket order." A hash table with no extra bookkeeping — the kind this post describes — has no inherent order at all, since which bucket a key lands in depends on its hash, not when it was inserted.
Why does Java's HashMap use 0.75 specifically?
It's a documented, deliberate space/time trade-off: a lower threshold resizes (and rehashes) more often, wasting more memory on mostly-empty buckets to keep chains shorter; a higher threshold packs the table tighter at the cost of longer average chains. 0.75 is Java's chosen middle ground — a different implementation is free to choose differently, and several do.
Is anything I enter into Hash Table Visualizer sent anywhere?
No — every hash and lookup runs entirely in your browser. Nothing is ever sent to a server.