Linear hash
From Wikipedia, the free encyclopedia
Linear Hashing is a dynamic hash table algorithm discovered by Witold Litwin in 1980. Linear hashing allows for the expansion of the hash table one slot at a time. The frequent single slot expansion can very effectively control the length of the collision chain. The cost of hash table expansion is spread out across each hash table insertion operation, as opposed to be incurred all at once. Therefore linear hashing is well suited for interactive applications.
[edit] Algorithm Details
As usual, a hash function controls the address calculation of linear hashing. In linear hashing, the address calculation is always bounded by a size that is a power of two.
- address(level,key) = hash(key) mod (2level)
The 'split' variable controls the read operation, and the expansion operation.
A read operation would use address(level,key) if address(level,key) is greater than or equal to the 'split' variable. Otherwise, address(level+1,key) is used.
A linear hashing table expansion operation would consist of rehashing the entries at slot location indicated by the 'split' variable to the target slot location of address(level+1,key). The 'split' variable is incremented by 1 at the end of the expansion operation. If the 'split' variable reaches 2level, then the 'level' variable is incremented by 1, and the 'split' variable is reset to 0.
There is some flexibility in choosing how often the expansion operations are performed. One obvious choice is one expansion operation per insertion request. Another choice is to control the expansion with a programmer defined load factor.
The hash table array for linear hashing is usually implemented with a dynamic array algorithm.
[edit] References
W. Litwin, Linear hashing: A new tool for file and table addressing, Proc. 6th Conference on Very Large Databases, pages 212–223, 1980.
Per-Åke Larson, Dynamic Hash Tables, Communications of the ACM, pages 446–457, April 1988, Volume 31, Number 4.