Linear hashing visualizer

Type or paste the keys from your exercise and set the number of initial buckets N, how many keys fit on a page, and when to split. "Run all" inserts every key; "Start step by step" goes one key at a time. Each row of the drawing is a bucket: its primary page, then any overflow pages, with the split pointer marked. The answer table lists every step and the buckets after it, and "Copy answer" puts it on the clipboard as text.

• The hash function is the key modulo the current table size, as in textbook exercises.
• "A page overflows" is the classic rule: an insert that needs an overflow page triggers one split. The load-factor rules split whenever the table gets fuller than the threshold.

Linear hashing is a hash index that grows smoothly as keys are added, one bucket per split, without ever rehashing the whole table and without the directory that extendible hashing needs. Its state is just the number of initial buckets N, the level L, which counts how many times the table has doubled, and the split pointer, which says which bucket will be split next.

The trick is that it does not split the bucket that overflows. It splits buckets in order, 0, 1, 2 and so on, and lets an overflowing bucket keep its extra keys in overflow pages until its turn comes. Since every bucket is split once per round, every overflow chain is eventually broken up.

Linear hashing uses a family of hash functions, each doubling the range of the last: h_L(k) = k mod (N·2^L). To find a key's bucket, compute h_L(k). If the result is below the split pointer, that bucket has already been split this round and its keys were redistributed with the next function, so use h_L+1(k) instead. Buckets from the split pointer onward, up to N·2^L − 1, have not been split yet; buckets beyond that are the new halves created this round.

A split takes the bucket at the split pointer, s, creates bucket s + N·2^L at the end of the table, and rehashes the keys of s, including its overflow pages, with h_L+1: each stays in s or moves to the new bucket. The split pointer then advances. When it reaches N·2^L, every original bucket of the round has been split and the table has doubled, so L increases and the pointer returns to 0.

The default keys, 12, 27, 5, 40, 33, 18, 9, 64, 21, 50, 7, 36, with two initial buckets, two keys per page and splitting on overflow, cause 4 splits and end at level 1 with the split pointer at 2 and 6 buckets:

Litwin's original rule splits once each time an insert overflows a page, which is also the rule in Ramakrishnan and Gehrke's textbook; with it the space use is not controlled directly. The alternative splits whenever the load factor, keys divided by primary slots, rises above a threshold, which lets the designer trade space for lookup cost. Inserting 20,000 random keys into a table with four initial buckets and four keys per page, averaged over five runs:

Both grow one bucket at a time. Extendible hashing splits exactly the bucket that overflows and keeps a directory to find it, so a lookup is one directory access and one bucket, but the directory can double suddenly and grows badly with skewed keys. Linear hashing has no directory to store or double, and its growth is perfectly regular, but buckets that overflow before their turn need overflow pages, and skewed keys can make those chains long. Under random keys the two fill their buckets about equally: 69.2% for extendible hashing in the same experiment.

Witold Litwin presented linear hashing in "Linear Hashing: A New Tool for File and Table Addressing" at the Very Large Data Bases conference in 1980, a year after extendible hashing was published. Its regular, directory-free growth made it popular for hash files and for in-memory tables that must grow without long pauses; Berkeley DB's hash access method is based on it.