Extendible hashing visualizer

Type or paste the keys from your exercise, separated by commas or spaces, and choose the conventions your course uses: which bits of the hash index the directory, how many keys a bucket holds, and how wide the hash is. "Run all" inserts every key; "Start step by step" lets you go one key at a time with Next and Back. The answer table under the drawing lists each operation, what it caused and every bucket afterwards, and "Copy answer" puts it on the clipboard as plain text.

• Decimal keys are hashed by taking the key modulo 2^width, the usual convention in exercises, so 13 with an 8-bit hash is 00001101. To use the hash values from your exercise directly, switch to "Hash bits" and type bit strings such as 0110.
• Prefix a key with x to delete it, for example "x13". The merge rule decides whether buckets combine again.
• "Copy link" gives an address that reopens this exact exercise, for a bookmark or to send to someone.

Extendible hashing is a way of storing a hash index on disk that grows smoothly as keys are added. Keys live in fixed-size buckets, usually one disk page each. A directory of 2^d pointers sits in front of them, and a key's bucket is found by taking d bits of its hash, the global depth, and following that directory entry. A lookup therefore costs one directory access and one bucket access, however large the table gets.

Buckets do not each need all d bits. A bucket's local depth l is the number of bits its keys are known to share, and 2^{d − l} directory entries point to it. Static hashing has to rehash every key when the table outgrows its buckets. Extendible hashing never does: when one bucket overflows, only that bucket is split.

To insert a key, find its bucket through the directory. If the bucket has room, the key goes in. If it is full:

1. If the bucket's local depth is less than the global depth, several directory entries point to it. Split it: create a new bucket, raise both local depths by one, move the keys whose next bit is 1 to the new bucket, and repoint half of the directory entries to it.
2. If the local depth equals the global depth, only one entry points to it, so there is nothing to divide. First double the directory, with each new entry copying the pointer of the entry it was made from, then split as above.
3. Try the insert again; if every key landed on the same side, the bucket may still be full and the process repeats.

Inserting the page's default keys, 13, 4, 30, 21, 7, 18, 25, 2, 11, 9, 28, 16, into buckets of two with the last bits of an 8-bit hash takes 6 splits, 3 of which double the directory, and ends with global depth 3 and 7 buckets:

The directory can be indexed by the last (low-order) bits of the hash or the first (high-order) bits, and textbooks differ. Ramakrishnan and Gehrke's Database Management Systems uses the last bits; Wikipedia's worked example and many lecture notes use the first bits. With the last bits, doubling the directory is a copy of the whole directory placed after itself; with the first bits, each entry is duplicated in place. The two give different buckets for the same keys, so check which one your course uses. The same twelve keys, buckets of two, 8-bit hash:

Deleting a key removes it from its bucket. Merging is optional, and textbooks again differ. A bucket can merge with its split image, the bucket it was split from or that was split from it, when both have the same local depth: either only when one of them becomes empty, or whenever their keys fit in one bucket. The merged bucket's local depth drops by one, and when no bucket has a local depth equal to the global depth, the directory halves.

Many systems skip merging altogether, since a table that shrank once will often grow again and merging costs writes; the "Keep buckets" setting does that.

A bucket that splits leaves two buckets about half full, so for random keys the average fill settles near ln 2, about 69%. The directory grows faster than the buckets, because a doubling is triggered by the single deepest bucket. Inserting 20,000 random 30-bit keys, averaged over eight runs:

Extendible hashing is a standard topic in database courses next to B+ trees, as the other main way to build an index on disk. A hash index answers equality lookups in about two page reads but cannot answer range queries, which is why databases default to B+ trees. File systems use it for large directories: Wikipedia lists ZFS, GPFS, the Global File System and SpadFS among file systems that do.

Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger and H. Raymond Strong described extendible hashing in "Extendible Hashing: A Fast Access Method for Dynamic Files" in ACM Transactions on Database Systems in 1979, presenting it as an alternative to balanced trees that guarantees at most two page faults per lookup. Witold Litwin's linear hashing followed in 1980, removing the directory at the cost of overflow pages.