Content deleted Content added
MegaHasher (talk | contribs) m reference |
|||
Line 1:
'''Linear Hashing''' is a dynamic [[hash table]] algorithm discovered by [[Witold Litwin]] in
1980. <ref> {{Citation | first1=Witold | last1=Litwin | title=Linear hashing: A new tool for file and table addressing | journal=Proc. 6th Conference on Very Large Databases | pages=pp. 212-223 | year=1980}}</ref> 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. <ref> {{Citation | first1=Per-Åke | last1=Larson | title=Dynamic Hash Tables | journal=Communications of the ACM | pages=pp. 446-457 | date=April 1988 | Volume=31 | Number=4}}</ref> Therefore
linear hashing is well suited for interactive applications.
Line 9:
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 (2<sup>level</sup>)
Line 32:
==References==
{{Reflist}}
==External links==
| |||