Hash functions

The hash function ${\displaystyle h_{i}(c)}$ returns the 0-based index of the bucket that contains the record with key ${\displaystyle c}$. When a bucket which uses the hash function ${\displaystyle h_{i}}$ is split into two new buckets, the hash function ${\displaystyle h_{i}}$ is replaced with ${\displaystyle h_{i+1}}$ for both of those new buckets. At any time, at most two hash functions ${\displaystyle h_{l}}$ and ${\displaystyle h_{l+1}}$ are used; such that ${\displaystyle l}$ corresponds to the current level. The family of hash functions ${\displaystyle h_{i}(c)}$ is also referred to as the dynamic hash function.

Typically, the value of ${\displaystyle i}$ in ${\displaystyle h_{i}}$ corresponds to the number of rightmost binary digits of the key ${\displaystyle c}$ that are used to segregate the buckets. This dynamic hash function can be expressed arithmetically as ${\textstyle h_{i}(c)\mapsto (c{\bmod {2}}^{i})}$. Note that when the total number of buckets is equal to one, ${\displaystyle i=0}$.

Complete the calculations below to determine the correct hashing function for the given hashing key ${\displaystyle c}$.^[10]

# l represents the current level
# s represents the split pointer index
a = h_l(c)
if (a < s): a = h_{l+1}(c)

Split control

Linear hashing algorithms may use only controlled splits or both controlled and uncontrolled splits.

Controlled splitting occurs if a split is performed whenever the load factor, which is monitored by the file, exceeds a predetermined threshold.^[10] If the hash index uses controlled splitting, the buckets are allowed to overflow by using linked overflow blocks. When the load factor surpasses a set threshold, the split pointer's designated bucket is split. Instead of using the load factor, this threshold can also be expressed as an occupancy percentage, in which case, the maximum number of records in the hash index equals (occupancy percentage)*(max records per non-overflowed bucket)*(number of buckets).^[12]

An uncontrolled split occurs when a split is performed whenever a bucket overflows, in which case that bucket would be split into two separate buckets.

File contraction occurs in some LH algorithm implementations if a controlled split causes the load factor to sink below a threshold. In this case, a merge operation would be triggered which would undo the last split, and reset the file state.^[10]

Split pointer

The index of the next bucket to be split is part of the file state and called the split pointer ${\displaystyle s}$. The split pointer corresponds to the first bucket that uses the hash function ${\displaystyle h_{l}}$ instead of ${\displaystyle h_{l+1}}$.^[10]

For example, if numerical records are inserted into the hash index according to their farthest right binary digits, the bucket corresponding with the appended bucket will be split. Thus, if we have the buckets labelled as 000, 001, 10, 11, 100, 101, we would split the bucket 10 because we are appending and creating the next sequential bucket 110. This would give us the buckets 000, 001, 010, 11, 100, 101, 110.^[12]

When a bucket is split, split pointer and possibly the level are updated according to the following, such that the level is 0 when the linear hashing index only has 1 bucket.^[10]

# l represents the current level
# s represents the split pointer index
s = s + 1
if (s >= 2^l): 
    l = l + 1
    s = 0

LH*

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 ^[13]

File state calculation

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 ^[13]

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