Every structure on this site so far finds things by comparing: binary search halves a range, a binary search tree walks left or right, a linked list walks node by node. A hash table skips comparing almost entirely. It turns a key into a number — the hash — and uses that number as a direct index into an array of buckets. Look up the same key later, get the same number, land on the same bucket. No searching required to find the right neighborhood; only within it.
That "which bucket" step is O(1), but two different keys can hash to the
same bucket — a collision — and with a fixed number of buckets, collisions
are certain to happen eventually, not a rare edge case. The demo below uses separate
chaining: each bucket holds a small list of every key that landed there, so a
collision just means comparing against the handful of keys sharing that bucket instead of
searching the whole table.
Put a key/value pair, get a key back out, or delete one. The log line shows the hash computed and which bucket it lands in — watch what happens when two different keys land on the same one. Keep putting new keys and watch the stats line above the table: once entries divided by buckets crosses 0.75, the table doubles its bucket count and rehashes everything that's in it — put just one more distinct key on top of the sample below (6 entries in 8 buckets already sits right at the threshold) to see it happen.
% numBuckets. O(k) for a key of
length k, effectively O(1) for the short keys most programs use.O(1) average — the chain being scanned is short as long as the table
isn't badly overloaded.O(1) average, same caveat.O(1) average.class HashTable {
#buckets;
#size = 0;
constructor(numBuckets = 8) {
this.#buckets = Array.from({ length: numBuckets }, () => []);
}
#hash(key, numBuckets = this.#buckets.length) {
let h = 0;
const s = String(key);
for (let i = 0; i < s.length; i++) {
h = (h * 31 + s.charCodeAt(i)) >>> 0; // >>>0 keeps it a positive 32-bit int
}
return h % numBuckets;
}
#resize() {
const bigger = Array.from({ length: this.#buckets.length * 2 }, () => []);
for (const bucket of this.#buckets) {
for (const [key, value] of bucket) {
bigger[this.#hash(key, bigger.length)].push([key, value]);
}
}
this.#buckets = bigger;
}
put(key, value) {
const bucket = this.#buckets[this.#hash(key)];
const existing = bucket.find(entry => entry[0] === key);
if (existing) { existing[1] = value; return; }
bucket.push([key, value]);
this.#size++;
if (this.#size / this.#buckets.length > 0.75) this.#resize();
}
get(key) {
const bucket = this.#buckets[this.#hash(key)];
const entry = bucket.find(entry => entry[0] === key);
return entry ? entry[1] : undefined;
}
has(key) {
const bucket = this.#buckets[this.#hash(key)];
return bucket.some(entry => entry[0] === key);
}
delete(key) {
const bucket = this.#buckets[this.#hash(key)];
const i = bucket.findIndex(entry => entry[0] === key);
if (i === -1) return false;
bucket.splice(i, 1);
this.#size--;
return true;
}
}
The multiply-by-31 in #hash is the standard trick for folding a string into a
number: it's the same scheme Java's String.hashCode() uses, chosen because 31 is
odd and prime, which spreads similar strings across different buckets better than an even or
composite multiplier would. #resize doubles the bucket count and reinserts every
key, since a key's bucket depends on numBuckets — the old bucket assignments don't
carry over, every entry has to be rehashed against the new count. Verified against a
plain-object reference model over 50,000 randomized interleaved put/get/delete/has trials
(small key spaces to force frequent collisions and repeated resizes), checking every
get/has result after every operation and that the load factor never
exceeds 0.75 after a put returns, plus edge cases (delete on an empty table,
delete a key twice, put the same key twice with different values, a deliberately-collided pair
of keys, enough sequential inserts to force several resizes in a row) — see
/tmp/ht_test.js, scratch, not committed.
Resizing isn't free — it's just infrequent. Doubling the bucket count and
rehashing every entry is an O(n) pass, not O(1). The demo above still
calls put "O(1) average" and that's true amortized over many calls — most
puts just append to a bucket, and the occasional expensive rehash gets averaged out over all
the cheap ones between it and the last one — but the one put that crosses the 0.75
threshold is genuinely slower than its neighbors, a real (if brief) pause a latency-sensitive
system would feel. Measured directly against the exact hash/resize logic shown in the reference
implementation above (instrumented with a work counter, nothing about the algorithm changed):
100,000 sequential puts trigger 15 resizes, and the costliest one — put #98,305,
growing the table from 131,072 to 262,144 buckets — does 98,305 units of rehash
work by itself, where an ordinary put does 1. That one put is a 98,305x spike,
not a "genuinely slower" that stays vague. This is the same amortized-vs-per-call distinction
the queue page's array-backed
implementation runs into with its occasional compacting pass, just triggered by a growing
table instead of a growing dead prefix. Pick a size and run it yourself below:
A bad hash function defeats the whole point. If hash mapped
every key to bucket 0, the table above would still be correct — every
get would still return the right value — just no faster than a linked list,
since every operation would scan one giant chain. Collisions aren't a bug to eliminate
(they're mathematically guaranteed once there are more possible keys than buckets); a good
hash function just spreads them thin instead of piling them into a few buckets.
Mutating a key after it's inserted. The bucket a key lives in is decided once, at insert time, from whatever the key's value was then. In a language where keys can be mutable objects, changing the object after inserting it doesn't move it to the bucket matching its new hash — the entry just becomes unreachable by any key that would hash correctly now. This is why languages that let you use custom objects as hash keys generally expect them to be treated as immutable once inserted.
dict, JavaScript's
Map and plain {} object, Ruby's Hash — the built-in
key/value type in most languages is a hash table under the hood.O(1) instead of scanning a list."A hash table spends more memory than a tree holding the same entries" sounds like a flat
rule, but nothing on this site had ever actually counted it. The comparison below isn't against
the plain Binary Search Tree — that page
only guarantees O(log n) on average, not worst case, so it's not the tree
the Complexity section's own worst-case claim below means — it's against an
AVL tree, extended with one extra field per node so
it holds a key and a value the same way this page's own [key, value] chain
entries do (the real shipped AVL class is a set, one orderable value per node — adding a second
field for the associated payload is the only change). Counting real reference-sized slots, the
same convention Fenwick Tree's own memory
comparison against Segment Tree uses (array/field counts, not a full JS-engine byte audit): this
table's buckets array contributes one slot per bucket, each stored entry contributes one slot
inside its own bucket's array plus two more inside its [key, value] pair, so
n entries across B buckets cost B + 3n slots total. The
extended AVL node (key, value, left, right,
height) costs a fixed 5n.
Because B only ever doubles, it isn't a tight 1.33n — it ranges from
1.33n (load factor just at the 0.75 limit, right before the next resize) up to
2.67n (right after one, load factor freshly halved to 0.375). At
n = 98,304, B = 131,072 and the table costs 425,984
slots against the AVL tree's 491,520 — the table uses 13.33% fewer.
One more entry triggers a resize to B = 262,144: at n = 98,305 the table
costs 557,059 slots against the tree's 491,525 — now
13.33% more. Same two structures, same single extra entry, opposite verdict —
"generally spends more memory" was never true in one direction; it oscillates around rough parity
depending on how recently the table last resized, narrowest right after a resize and widest right
before the next one.
Time: put, get, and delete are all
O(1) amortized average — "average" because a reasonable hash function is
assumed to spread keys thinly across buckets, and "amortized" on top of that because keeping
the load factor bounded means resizing occasionally, and any single put that
triggers a resize actually costs O(n) (the "resizing isn't free" pitfall above
walks through that call specifically). Worst case is still O(n) if every key
collides into a single bucket regardless of resizing, since that one chain degrades to a
linear scan no matter how many total buckets exist. Compare to an
AVL tree, which
guarantees O(log n) worst case with no hash function required — the trade is a
probabilistic O(1) against a guaranteed O(log n).
Space: O(n) for n entries, plus the unused
capacity sitting in empty or underfull buckets — see Measuring
the memory claim above: that slack oscillates to within about 13% of a comparable tree's own
fixed per-node cost, rather than sitting one-directionally above it.
That O(n) space is the cost of storing every key so get has
something to hand back. If all that's ever needed is "have I seen this key?" with no value to
retrieve, a Bloom filter answers the same
question in a fixed number of bits chosen up front — no keys stored at all — at the cost of
occasionally answering yes when the true answer is no.
Growing this table always means the O(n) full rehash the Complexity section above
prices out — every key gets reinserted, whether or not its own bucket ever overflowed. Extendible hashing avoids that by growing a
small directory of bucket pointers instead of one big array, splitting only the bucket that
actually overflowed and leaving everything else untouched — the trade that matters once a rehash
means moving records on disk rather than just in memory.
Everything on this page hashes a key to a bucket within one table. A different
question — which server owns a key, when the servers themselves can come and
go — needs the buckets to be far more stable than a fixed array's % numBuckets
allows; see consistent hashing for how
that's done.
Chaining also isn't the only way to resolve a collision. Cuckoo hashing gives every key exactly two
candidate slots across two separate tables instead of an unbounded chain in one, trading this
page's average-case O(1) for a worst-case O(1) guarantee on
get — at the cost of a trickier insert that can occasionally evict its way into an
unresolvable cycle and force a full rehash. Robin
Hood hashing is a third option, splitting the difference: it keeps chaining's single table and
one hash function but adds a rule that bounds how unlucky any one key's probe length can get,
without chaining away this page's worst-case risk the way cuckoo hashing does. Hopscotch hashing is a fourth: like cuckoo
hashing it gives get a hard worst-case bound, but like Robin Hood hashing it keeps a
single table and one hash function, using a per-slot bitmap to bound every key's distance from home
instead of a second table to bound the number of candidate slots. See Choosing a Hash Table Collision
Strategy for the full four-way comparison.