A
hashing algorithm by which a
hash table can grow
dynamically by constantly generating new
hash functions from a family of
functions. 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.