Linear Hashing: Split the Buckets in Turn, No Directory

The idea: split the buckets in a fixed order

Linear hashing is a hash file on disk that grows one bucket at a time and needs no directory. The buckets sit in a plain array 0, 1, 2, …, and a key's hash is the bucket's place in that array. When the file must grow, it does not split the bucket that is full. It splits the bucket that the split pointer next points to, and then moves the pointer one bucket on.

The page starts with N = 2 buckets and pages of 2 keys. A real page holds hundreds of keys; 2 makes splits happen quickly. Pick a key and press Insert or Find, or run a demo.

Two hash functions and the split pointer

In round L the file uses two hash functions: hL(k) = k mod (N·2L) and hL+1(k) = k mod (N·2L+1). Buckets 0 … next−1 have already split this round, so their keys are spread by h_L+1. To find a key's bucket:

a = h_L(k)
if a < next:          # bucket a has split this round
    a = h_L+1(k)       # so the key is in a or in a + N·2^L

The address costs two cheap computations and no disk read (Demo 4: h₀(6) = 0 is below next = 1, so h₁(6) = 2 gives bucket 2).

An overflow splits bucket next

A full bucket is never refused. The key goes into an overflow page chained to the bucket. That insert is also the signal to grow: bucket next splits. A new bucket next + N·2^L is added at the end of the array, every key of bucket next is rehashed with h_L+1, and about half of them move. Then next goes up by one.

So the bucket that splits is often not the bucket that overflowed (Demo 2). Its overflow page stays until the pointer gets there. In Demo 3 the next insert, 7, also lands in an overflow page; now next = 1, so bucket 1 splits, its keys spread over buckets 1 and 3, and the overflow page is freed.

Rounds: the file doubles, one bucket at a time

When next reaches N·2^L, every bucket of the round has split once and the file has doubled. The round ends: L goes up by one and next goes back to 0. The old h_L+1 becomes the new base hash. Growth is smooth: each split rewrites one bucket and adds one at the end, and no key outside that bucket is touched.

Skew is the weak spot. In Demo 5 the keys 1, 17, 33, 49 and 65 all leave the remainder 1 mod 16. When the pointer reaches bucket 1 it splits with k mod 4, but all five keys give 1, so nothing moves. The chain grows to two overflow pages, and a find of 65 would read three pages. The next split of bucket 1, with k mod 8, will not help either. Real systems use a good hash function so that this is rare.

The cost of a find

A find reads the primary page and then, if needed, each overflow page in turn. With a good hash and a sensible load the chains are short, so a lookup costs about one disk read, the same as extendible hashing, but there is no directory to keep in memory. The page splits on every overflow (Litwin's uncontrolled split); many systems instead split when the load factor n / (capacity · buckets) passes a threshold such as 75%, which keeps the file fuller.

Linear hashing and extendible hashing

	Extendible hashing	Linear hashing
Extra structure	directory of 2g pointers	none: L and next
Which bucket splits	the full one	bucket next, in order 0, 1, 2, …
Full bucket meanwhile	never: it splits at once	an overflow page until the pointer arrives
Growth step	one bucket; sometimes the directory doubles	always one bucket at the end
Lookup	directory entry + 1 bucket	1 bucket + its overflow pages
Skewed keys	directory grows large	long overflow chains

Linear hashing was published by Witold Litwin in 1980. It is used in Berkeley DB's hash access method and PostgreSQL's hash index (which splits buckets in order and keeps overflow pages), and the same in-turn splitting lets in-memory hash tables grow without one long rehash.

See also Extendible Hashing for the directory-based alternative, Closed Hash Tables, using buckets and Open Hash Tables for fixed-size tables, B+ Tree for the disk index that also answers range queries, and PostgreSQL index types for a hash index in a real database.

What the page leaves out

Delete, and merging the last bucket back into its partner when the file shrinks (next moves backwards); a load-factor trigger instead of splitting on every overflow; a real hash function on strings; pages with hundreds of keys; how the bucket array is laid out on disk when it grows (real systems allocate it in chunks); and locking during a split.

References

Litwin (1980): Linear Hashing, a New Tool for File and Table Addressing

Wikipedia: Linear hashing

PostgreSQL documentation: Hash index implementation