Linear hashing: Difference between revisions

Revision as of 21:16, 13 March 2009

Revision as of 20:57, 6 April 2009

Line 1:

'''Linear hashing''' is a dynamic [[hash table]] algorithm invented by Witold Litwin (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 | url=http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF|format=PDF}}</ref>, and later popularized by [[Paul Larson]]. 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 | Volumevolume=31 | Number=4 | doi=10.1145/42404.42410 | url=http://doi.acm.org/10.1145/42404.42410}}</ref> Therefore

linear hashing is well suited for interactive applications.