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.