Linear hashing

In order to access a record with key ${\displaystyle c}$, a family of hash functions, called collectively a dynamic hash function is applied to the key ${\displaystyle c}$. At any time, at most two hash functions ${\displaystyle h_{i}}$ and ${\displaystyle h_{i+1}}$ are used. A typical example uses the division modulo x operation. If the original number of buckets is ${\displaystyle N}$, then the family of hash functions is [10]

${\displaystyle h_{i}(c)\mapsto c{\pmod {N\cdot 2^{i}}}}$

As the file grows through insertions, it expands gracefully through the splitting of one bucket into two buckets. The sequence of buckets to split is predetermined. This is the fundamental difference to schemes like Fagin's extendible hashing. [11] For the two new buckets, the hash function ${\displaystyle h_{i}}$ is replaced with ${\displaystyle h_{i+1}}$. The number of the bucket to be split is part of the file state and called the split pointer ${\displaystyle s}$.[10]

A split can be performed whenever a bucket overflows. This is an uncontrolled split. Alternatively, the file can monitor the load factor and performs a split whenever the load factor exceeds a threshold. This was controlled splitting.[10]

Addressing is based on the file state, consisting of the split pointer ${\displaystyle s}$ and the level ${\displaystyle l}$. If the level is ${\displaystyle l}$, then the hash functions used are ${\displaystyle h_{l}}$ and ${\displaystyle h_{l+1}}$.

The LH algorithm for hashing key ${\displaystyle c}$ is[10]

${\displaystyle a:=h_{l}(c)}$

if ${\displaystyle a<s:a:=h_{l+1}(c)}$

When a bucket is split, split pointer and possibly the level are updated according to[10]

${\displaystyle s:=s+1}$

if ${\displaystyle s\geq N\times 2^{l}}$: ${\displaystyle l+=1,s=0}$

If under controlled splitting the load factor sinks below a threshold, a merge operation is triggered. The merge operation undoes the last split, also resetting the file state. [10]

The file state consists of split pointer ${\displaystyle s}$ and level ${\displaystyle l}$. If the original file started with ${\displaystyle N=1}$ buckets, then the number of buckets ${\displaystyle n}$ and the file state are related via [12]

${\displaystyle n=2^{l}+s}$

The main contribution of LH* is to allow a client of an LH* file to find the bucket where the record resides even if the client does not know the file state. Clients in fact store their version of the file state, which is initially just the knowledge of the first bucket, namely Bucket 0. Based on their file state, a client calculates the address of a key and sends a request to that bucket. At the bucket, the request is checked and if the record is not at the bucket, it is forwarded. In a reasonably stable system, that is, if there is only one split or merge going on while the request is processed, it can be shown that there are at most two forwards. After a forward, the final bucket sends an Image Adjustment Message to the client whose state is now closer to the state of the distributed file.[10] While forwards are reasonably rare for active clients, their number can be even further reduced by additional information exchange between servers and clients [12]