Linear hashing: Difference between revisions

Revision as of 23:09, 31 December 2005

Revision as of 03:02, 1 January 2006

Line 1:

'''Linear Hashing''' is a dynamic [[hash table]] algorithm invented by Witold Litwin in

{{wikify}}

'''Linear Hashing''' is a dynamic hash table algorithm invented 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

Line 7 ⟶ 6:

linear hashing is well suited for interactive applications.

===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 (2 ** ^level)

The 'split' variable controls the read operation, and the expansion operation.

Line 23 ⟶ 22:

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 a power of 2^level, then the 'level'

variable is incremented by 1, and the 'split' variable is reset to 0.

Line 30 ⟶ 29:

is to control the expansion with a programmer defined load factor.

===References===

W. Litwin, ''Linear hashing: A new tool for file and table addressing'', Proc. 6th Conference on Very Large Databases, pages 212–223, [[1980]].