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. 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.
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.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 a
balanced binary search 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 — a hash table generally spends more memory
than a tree holding the same entries, in exchange for its average-case speed.
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.