The Hash Table page's own growth strategy is a
full rehash: once the load factor gets too high, allocate a bigger array and reinsert every
existing key into it. That's O(1) amortized, but the word "amortized" is doing real
work — one unlucky insert pays for touching the entire table. Extendible hashing grows a different
way. Instead of one array of buckets, it keeps a small directory — an array of
pointers, not data — and a separate pool of buckets, each holding a small fixed
number of entries. Looking a key up means computing its hash, using the low bits of that hash as
a directory index, following the pointer, and scanning that one bucket. Growth happens only when
a specific bucket overflows, and only that bucket's own entries ever move — everything else in
the table, directory included in the common case, stays exactly where it was.
Two things can happen when a bucket overflows, and they're independent. The directory itself
might need to double — but doubling a directory just means copying pointers, no key ever moves
for that alone. And the overflowing bucket splits in two, with its entries
redistributed by one more bit of their hash than was significant before — but only that
bucket's entries move; every other bucket, and every directory pointer that wasn't pointing
at the split bucket, is untouched. A full rehash costs O(n) the moment it happens.
A split costs O(bucket capacity) — a constant, not the table size — no matter how
many keys are already stored elsewhere.
Add an item and watch it land in a bucket via the directory. Bucket capacity is 3 here, small
enough that a handful of items already trigger the interesting cases. Load the sample: nine words
go in, in order. The first three fill bucket 0 outright. The fourth (dog) forces the
first split — global depth 0 → 1, a second bucket appears, directory grows to 2 slots. The fifth
and sixth (lion, owl) each force one more split; watching the log
during owl shows the more interesting case, where the directory has to double
and split in the same step, because the overflowing bucket's own local depth had already
caught up to the global depth. By the end (cat), global depth is 3 (8 directory
slots) over 4 real buckets, and every one of the nine words is still exactly one directory hop
and one bucket scan away.
Query checks the directory index and bucket a key resolves to, whether or not it's actually
there. Delete removes a key from its bucket directly — this page doesn't implement merging
buckets back together on delete (see Pitfalls), so the directory never shrinks, matching
Hash Table's own page, whose delete
doesn't shrink the array back down either.
globalDepth bits of
it are what everything else keys off; the directory has exactly 2^globalDepth
slots for exactly that reason.hash(item) & ((1 << globalDepth) - 1),
the directory slot to follow. Every directory slot holds a pointer to a bucket, never a key
itself.owl does in the demo above.add, read-only.
Always exactly one directory lookup and one bucket scan, regardless of how many splits have
happened.const MAX_GLOBAL_DEPTH = 6; // demo safety cap, not a property of the algorithm itself — see Pitfalls
function hashKey(key) {
let h = 0;
const s = String(key);
for (let i = 0; i < s.length; i++) h = (h * 31 + s.charCodeAt(i)) >>> 0;
return h >>> 0;
}
class ExtendibleHashTable {
#capacity; #globalDepth; #buckets; #directory; #nextId;
constructor(capacity) {
this.#capacity = capacity;
this.#globalDepth = 0;
this.#buckets = [{ id: 0, localDepth: 0, entries: [] }];
this.#directory = [0];
this.#nextId = 1;
}
#mask(d) { return d === 0 ? 0 : (1 << d) - 1; }
#dirIndex(h) { return h & this.#mask(this.#globalDepth); }
#bucketOf(id) { return this.#buckets.find(b => b.id === id); }
add(key) {
const h = hashKey(key);
for (;;) {
const bucket = this.#bucketOf(this.#directory[this.#dirIndex(h)]);
if (bucket.entries.includes(key)) return { added: false, reason: 'duplicate' };
if (bucket.entries.length < this.#capacity) { bucket.entries.push(key); return { added: true }; }
if (!this.#split(bucket)) return { added: false, reason: 'cap' };
}
}
// Splits `bucket` in two by one more bit than it currently uses. Only doubles the
// directory (pointer copies, no key moves) when the bucket's own depth has caught up
// to the global depth — a bucket that's shallower than global depth can split without
// touching the directory at all.
#split(bucket) {
const oldDepth = bucket.localDepth;
if (oldDepth === this.#globalDepth) {
if (this.#globalDepth >= MAX_GLOBAL_DEPTH) return false;
this.#directory = this.#directory.concat(this.#directory);
this.#globalDepth++;
}
const bit = oldDepth;
const lowMask = this.#mask(oldDepth);
const pattern = this.#directory.findIndex(id => id === bucket.id) & lowMask;
const sibling = { id: this.#nextId++, localDepth: oldDepth + 1, entries: [] };
bucket.localDepth = oldDepth + 1;
for (let i = 0; i < this.#directory.length; i++) {
if (this.#directory[i] === bucket.id && (i & lowMask) === pattern && ((i >> bit) & 1) === 1) {
this.#directory[i] = sibling.id;
}
}
this.#buckets.push(sibling);
const entries = bucket.entries;
bucket.entries = [];
for (const key of entries) {
const target = ((hashKey(key) >> bit) & 1) === 1 ? sibling : bucket;
target.entries.push(key);
}
return true;
}
query(key) {
const h = hashKey(key);
const idx = this.#dirIndex(h);
const bucket = this.#bucketOf(this.#directory[idx]);
return { dirIndex: idx, bucketId: bucket.id, found: bucket.entries.includes(key) };
}
delete(key) {
const bucket = this.#bucketOf(this.query(key).bucketId);
const i = bucket.entries.indexOf(key);
if (i === -1) return false;
bucket.entries.splice(i, 1);
return true;
}
}Verified two ways before writing content. (1) A randomized stress harness: 2,000 trials, 60
random add/query/delete operations each against an independent JavaScript Set oracle
(120,000 operations total), checking every operation's result against the oracle and a
structural invariant after every single one — every directory index pointing at a given bucket
must agree on that bucket's own low localDepth bits, and the number of directory
slots pointing at a bucket must equal exactly 2^(globalDepth - localDepth). 0
mismatches, 0 invariant violations. (2) Self-tested the harness against a deliberately broken
variant first — one that forgets to increment bucket.localDepth after a split. The
invariant check caught it on its very first violation (a bucket claiming 1 directory pointer when
its stale local depth implied it should have 2), and left running, the same bug drove the table
into an unbounded loop of pointless splits that never resolved anything, eventually crashing
the checker process on an out-of-memory error — a strong signal the invariant check has real
teeth, not just a check that happens to never fire. See /tmp/exthash/*.js, scratch,
not committed. The live demo above runs this exact code, re-verified by driving it through a
fake-DOM harness — Node's vm module plus stand-in DOM elements, real
Add/Query/Delete button clicks, no direct access to internal state — for 500 more trials (20,000
operations) against the same Set oracle, 0 mismatches, then a separate direct check
that a key containing HTML (<img src=x onerror=alert(1)>) renders as inert text
in a bucket chip rather than executing, confirming the render path builds real DOM nodes with
textContent rather than interpolating user input into innerHTML.
Splitting only helps when the colliding keys' hashes eventually disagree somewhere —
if they never do, no amount of splitting fixes it. Every split distinguishes keys by one
more bit of their hash than before. If two or more keys hash to the exact same value,
every bit agrees, forever, and splitting can never separate them — the overflowing bucket just
keeps re-triggering a directory doubling that accomplishes nothing. This isn't hypothetical: the
strings '!~', '"_', '#@', and '$!' all hash to
the exact same value (1149) under this page's own hashKey — confirmed directly
against the shipped function, not asserted. Clear the demo table, add the first three (they fill
one bucket exactly, at capacity 3, no split needed yet), then add the fourth: watch the log show
six consecutive doublings — global depth 0 → 6, the directory growing from 1 slot to 64, one real
bucket becoming seven — for a single item that still never finds a home, because the demo's own
MAX_GLOBAL_DEPTH safety cap (6, chosen so the directory table stays renderable) stops
it there. A real implementation would hit the same wall eventually regardless of any cap, once
global depth reaches the hash's full bit width — at which point the only fixes are ones this page
doesn't build: overflow chaining within a bucket, or a second, independent hash function to fall
back on.
No merge on delete. This page's delete removes an entry from its
bucket and stops — it never checks whether a bucket and its sibling could now fit back into one,
and never halves the directory even if every remaining bucket's local depth ends up below the
global depth. That's a real, standard extension (undo a split when the two halves' combined
entries fit the capacity again, then shrink the directory once nothing still needs the extra bit)
that plenty of production implementations skip entirely, the same way Hash Table's own chaining table never shrinks its
bucket array back down after a run of deletes either — reclaiming space on delete is an
optimization on top of correctness, not a requirement for it.
A single add has no small worst-case bound. Most inserts cost one
directory lookup and one bucket write. But a bucket that overflows when its own local depth
already equals the global depth pays for a full directory doubling — an O(2^globalDepth)
copy — and, as the owl step in the demo shows, a single add can trigger that more than
once in a row if the freshly split sibling immediately overflows again. The cost is real but rare:
the doubling only happens when the whole table's addressing capacity needs to grow, not
on every split, so it amortizes the same way a dynamic array's occasional full-copy resize does
(see Dynamic Array) — just triggered by one
bucket's local overflow instead of a global load-factor check.
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, and H. Raymond Strong described this structure in 1979 (ACM Transactions on Database Systems) for exactly the situation this page's own comparison against a full rehash is built around, except at disk scale rather than in memory: moving a record on disk costs a seek, so a hash table that occasionally rewrites its entire contents is not just slow but the dominant cost of using it at all. The original paper's own guarantee is at most two disk accesses to find any key — one to read the (small, often memory-resident) directory, one to read the bucket it points to — a structural guarantee, not a tuned average. That page-oriented design is why the technique shows up today inside real filesystems' own directory-hashing implementations, including ZFS, GPFS, and the Global File System family, for the same reason B-Tree and B+ Tree get reached for over a plain binary search tree once storage is disk- or page-backed (see this site's own disk-backed storage guide section) — except extendible hashing answers single-key point lookups only, with no ordering at all, where B-Tree and B+ Tree also support range queries at the cost of a comparison-ordered, wider-node tree instead of a flat directory.
Time: query is O(1) — exactly one directory lookup
plus a scan of at most capacity entries in one bucket, regardless of how many splits
the table has been through. add is O(1) amortized: most inserts are a
single bucket write, and the occasional directory doubling (an O(2^globalDepth)
pointer copy) happens only when the table's addressing capacity itself needs to grow, the same
amortized argument a dynamic array's resize relies on. Space: O(n)
for the buckets themselves, plus O(2^globalDepth) for the directory — normally a
small fraction of the data, but Pitfalls above shows that fraction has no upper bound if the key
set is adversarial or simply unlucky enough to collide.
This site's guide, Choosing a Hash Table Collision Strategy, sets this entry aside from its three-way collision-resolution comparison — this page answers a different question (how a hash table grows without a full rehash), not which slot a colliding key ends up in.