A hashing algorithm
by which a hash table
can grow dynamically
by constantly generating new hash functions
from a family of function
s. At any given time, keys are being hashed by one of two different functions, until there is a split
, in which the older hash function is thrown out, and a new one is chosen from the function "family."
An example of a family of functions is the set
h[i](c) = c mod (2^i)N
...where "i" is the current "order" of the hash table. Every time there is a split, i is incremented.
Linear hashing solves two basic problems of hash tables: Static size, and expensive re-hasing. By constantly shuffling on the fly, it is a "load balanced" approach to creating a "growable" table. Furthermore, the order of the table increases logarithmically, so after the first few splits, they become very rare.