Extendible Hashing and Why the Directory Doubles

A hash table that must grow has one hard problem: growing means rehashing, and rehashing the whole table is a pause proportional to the table size. Chained tables solve it by rehashing into a doubled table and paying the whole cost at once; open addressing solves it by allocating a new array and moving every element. Extendible hashing takes a third route. It keeps a small directory of pointers in memory, splits one bucket at a time when that bucket overflows, and doubles the directory only when the split requires it. The file grows by one page per split; the directory grows by a factor of two occasionally; and no lookup touches more than one bucket.

Hashing to a bit string, then reading a suffix

The structure’s central idea is to treat the hash value as a bit string and use a fixed-length slice of it as an address. A global depth d means the directory has 2^d entries, and an entry is indexed by the low d bits of the hash. Each directory entry points to a bucket, and each bucket carries a local depth d' ≤ d recording how many of those bits its contents actually distinguish.

When d' = d, the bucket is “full-depth”: the directory has exactly one entry for it. When d' < d, the bucket is shared — 2^(d − d') directory entries, spaced 2^d' apart, point to the same bucket. That sharing is the mechanism that lets the directory be larger than the number of buckets, and it is why a split can occur without growing the directory at all.

global depth d = 3, so 8 directory slots

slot   low 3 bits   local depth   bucket
  0        000           1          A   <-- shared with slots 2, 4 and 6
  1        001           3          B
  2        010           1          A
  3        011           2          C   <-- shared with slot 7
  4        100           1          A
  5        101           3          D
  6        110           1          A
  7        111           2          C

Bucket A has local depth 1, so its four directory entries agree on the low bit and are spaced two apart. Bucket C has local depth 2 and two entries spaced four apart. Buckets B and D are full-depth and hold one entry each.

Fagin’s original presentation indexes by the high-order bits, and the choice is arbitrary: any fixed slice of a well-mixed hash works. The low-order form has one practical advantage. Doubling the directory becomes a plain concatenation — the new directory is the old one followed by a copy of itself — because the new address bit is the most significant of the address bits and the old addresses are unchanged. With high-order addressing the same operation is an interleave, which is one more thing to get wrong.

Lookup takes the hash, masks it to d bits, indexes the directory, and then reads the bucket and compares the full key. The last comparison is mandatory: a bucket holds keys whose hashes agree on the address bits, not keys that are equal.

The split that does not grow the directory

Insertion overflows a bucket. If its local depth is less than the global depth, the bucket is shared, and the split is local: allocate a new bucket, raise both buckets’ local depths to d' + 1, redistribute the entries by the newly significant bit, and redirect the directory entries whose address has that bit set.

MASK = (1 << 64) - 1

def hash64(x):
    """splitmix64 finaliser: spreads key bits across all 64 positions."""
    x = (x + 0x9E3779B97F4A7C15) & MASK
    x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK
    x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK
    return x ^ (x >> 31)

class Bucket:
    def __init__(self, depth):
        self.depth = depth
        self.items = []

def split_shared(table, bucket):
    """Split a bucket whose local depth is below the global depth."""
    bucket.depth += 1
    new = Bucket(bucket.depth)
    bit = 1 << (bucket.depth - 1)          # newly significant address bit
    keep, move = [], []
    for item in bucket.items:
        (move if hash64(item[0]) & bit else keep).append(item)
    bucket.items, new.items = keep, move

    # Every slot whose address has the new bit set moves to the new bucket.
    for i, target in enumerate(table.directory):
        if target is bucket and i & bit:
            table.directory[i] = new

The number of directory entries that change is half of those pointing at the old bucket, and the number of buckets increases by exactly one. The bucket’s shrunken contents keep their existing directory entries; only the entries carrying the newly significant bit are redirected. The directory does not move. This is the step that makes the structure attractive: growth is proportional to the data, not to the address space.

One detail in the initialisation matters and is easy to miss: the first bucket starts with local depth 0, not 1. A bucket created with depth 1 claims to distinguish its keys by one address bit while the directory may still hold only two slots pointing at it, and the first split then produces two buckets that both contain keys with the same low bit. The invariant to check after any insertion is that every key in a bucket agrees with that bucket’s depth-d' suffix, and that every directory slot pointing at a bucket agrees with the slot index in those same bits.

The split that does grow it

If the overflowing bucket has d' = d, its address is unique and there is no spare directory entry to hand to the new bucket. The only way to address two buckets with the same d-bit address is to add a bit. So the directory doubles: d becomes d + 1, the entry at index i of the old directory becomes the entry at both i and i + 2^d of the new one, and then the split proceeds as before. Every bucket’s local depth is unchanged by the doubling — sharing patterns are preserved — except for the bucket being split.

The doubling is O(2^d) in directory entries, not in data. For a directory of a million entries and 8-byte pointers, that is an 8 MiB copy; the buckets themselves are untouched. Because the directory is normally small enough to stay in memory, the cost is a memory copy rather than a disk operation, and it happens only when a full-depth bucket splits.

The doubling also explains the structure’s failure mode under adversarial keys. If the hash function is poor and many keys agree on the low address bits, the global depth rises while the buckets stay nearly empty. A directory of 2^d entries for n keys with d much greater than log₂ n means the directory dominates memory, and each doubling is a copy that buys almost nothing. The pathological case is a hash whose low bits are constant — every key lands in one bucket, which splits repeatedly, and the directory grows without bound while the other buckets stay empty.

What the indirection costs

Every lookup pays two dependent memory accesses instead of one: the directory entry, then the bucket. In an in-memory table that is one extra cache miss on the directory, which is usually resident because it is small; in an on-disk structure it is an extra page read if the directory is not cached, which is why implementations keep the directory pinned and the buckets on disk.

The second cost is the partial bucket fill. A bucket splits when it overflows, and both halves are then about half full. If splits happen only on overflow, the average occupancy settles somewhere between half and full, with the exact value depending on the key distribution and the split policy. The waste is comparable to a chained hash table’s load factor, and the failure mode is the same: long runs of inserts into one bucket, repeated splits, and a directory that grows faster than the data. A bucket that splits at capacity with a small number of records settles near half full while it is small, and the average across a large file tends toward ln 2 ≈ 0.69 of capacity — the same occupancy that a B-tree reaches under random insertion — because that is where the split frequency and the refill rate balance. The exact value depends on the capacity, because smaller buckets split more readily and waste less per bucket.

Two policies mitigate it. The first is to allow a small overflow area per bucket — a few extra slots in the page, or a chain of overflow pages — so that a bucket absorbs a burst without splitting. The second is to split on a different criterion, such as splitting a bucket that is more than a threshold full when its sibling is empty, which balances occupancy across the file rather than reacting per bucket.

The comparison with linear hashing

Linear hashing was published a year later and addresses the same problem with a different mechanism. It keeps no directory at all. Instead it maintains a pointer that advances through the buckets in order, splitting one bucket per insertion once the load factor crosses a threshold, and it stops splitting when the load factor falls back below it. The address of a key is computed by a hash modulo twice the current number of buckets, with a correction: when the resulting bucket number has not yet been split, the key is redirected to its pre-split bucket at number minus the original count.

The comparison is instructive because it isolates what the directory buys.

Property	Extendible	Linear
Address computation	Masked hash bits, one indirection	Arithmetic, no indirection
Growth unit	One bucket per split	One bucket per split, in file order
Overflow handling	Split the overflowing bucket	Split the next bucket in sequence, regardless
Directory	2^d pointers, doubling	None
Worst-case probe	2 accesses	1 access, plus overflow chain

Linear hashing’s weakness is that the bucket that splits is not the bucket that overflowed, so an unlucky key distribution produces long overflow chains even though the file is growing. Extendible hashing’s weakness is the directory: memory proportional to the address space, and a doubling copy that is invisible in the amortised analysis but real in a latency-sensitive path.

The choice between them turns on whether the directory fits in memory and whether the hash function can be trusted. When both hold, extendible hashing’s single-bucket split is the cleaner mechanism, because the bucket that grows is the bucket that splits. When the directory would be large relative to the data, linear hashing’s lack of indirection wins.

Related structures and where the idea recurs

The prefix-of-hash addressing scheme is the same idea as a hash trie, and the same idea as a sharded directory: the top bits of a hash select a shard, and each shard is an independent structure. A concurrent hash map can use exactly this decomposition — the directory is an array of bucket pointers, and a resize doubles it while readers continue on the old array until they observe the new one.

The structure also shares a failure mode with the load-factor arithmetic of open-addressed tables: performance degrades not when the table is full but when the probe sequences or the buckets become crowded, and the crowding is a function of the hash quality, not the count. Both structures depend on the hash distributing keys uniformly over the bits that are actually used as addresses; a hash that is uniform over 64 bits but biased in its top 8 is fine for extendible hashing with d ≤ 8 and catastrophic for d > 8.

Finally, the split-on-overflow rule assumes that the bucket contents can be redistributed by inspecting one more bit. That requires the hash bits to be independent of each other, which is a property of a good hash but not of a truncation of a bad one. If the address bits are taken directly from the key — as in key mod 2^d — then the bits are the key’s own binary digits, and keys that are multiples of large powers of two all collapse into the same slot. A multiplicative hash or a bit-mixing finaliser is what makes the address-bit scheme behave as designed.