Records in LH or LH* consists of a key and a content, the latter basically all the other attributes of the record.
Hash functions The hash function h_i(c) returns the 0-based index of the bucket that contains the record with key c. When a bucket which uses the hash function h_i is split into two new buckets, the hash function h_i is replaced with h_{i+1} for both of those new buckets. At any time, at most two hash functions h_l and h_{l+1} are used; such that l corresponds to the current
level. The family of hash functions h_i(c) is also referred to as the dynamic
hash function. Typically, the value of i in h_i corresponds to the number of rightmost binary digits of the key c that are used to segregate the buckets. This dynamic hash function can be expressed arithmetically as h_i(c) \mapsto (c \bmod 2^i) . Note that when the total number of buckets is equal to one, i=0. Complete the calculations below to determine the correct hashing function for the given hashing key c. 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. == Other properties ==