Minkowski–Hlawka theorem

2013-12-11T21:06:31Z

173.228.57.67: /* See aolso */

'''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=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 being incurred all at once.<ref>{{Citation | first1=Per-Åke | last1=Larson | title=Dynamic Hash Tables | journal=Communications of the ACM | pages=446–457 | date=April 1988 | volume=31 | number=4 | doi=10.1145/42404.42410}}</ref> Linear hashing is therefore well suited for interactive applications.

==Algorithm Details==

First the initial hash table is set up with some arbitrary initial number of buckets. The following values need to be kept track of:

* <math>N</math>: The initial number of buckets.
* <math>L</math>: The current level which is an integer that indicates on a logarithmic scale approximately how much the table has grown. This is initially <math>0</math>.
* <math>S</math>: The step pointer which points to a bucket. It initially points to the first bucket in the table.

Bucket collisions can be handled in a variety of ways but it is typical to have space for two items in each bucket and to add more buckets whenever a bucket overflows. Addresses are calculated in the following way:

* Apply a [[hash function]] to the key and call the result <math>H</math>.
* If <math>H \bmod N \times 2^L</math> is an address that comes before <math>S</math>, the address is <math>H \bmod N \times 2^{L+1}</math>.
* If <math>H \bmod N \times 2^L</math> is <math>S</math> or an address that comes after <math>S</math>, the address is <math>H \bmod N \times 2^L</math>.

To add a bucket:

* Allocate a new bucket at the end of the table.
* If <math>S</math> points to the <math>N \times 2^L</math>th bucket in the table, reset <math>S</math> and increment <math>L</math>.
* Otherwise increment <math>S</math>.

The effect of all of this is that the table is split into three sections; the section before <math>S</math>, the section from <math>S</math> to <math>N \times 2^L</math>, and the section after <math>N \times 2^L</math>. The first and last sections are stored using <math>H \bmod N \times 2^{L+1}</math> and the middle section is stored using <math>H \bmod N \times 2^L</math>. Each time <math>S</math> reaches <math>N \times 2^L</math> the table has doubled in size.

==Adoption in language systems==
Griswold and Townsend <ref>{{Citation | title=The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon | first1=William G. | last1=Griswold | author1-link = Bill Griswold | first2=Gregg M. | last2=Townsend | journal=Software - Practice and Experience | volume=23 | issue=4 | date=April 1993 | pages=351–367 | url=http://citeseer.ist.psu.edu/griswold93design.html}}</ref> discussed the adoption of linear hashing in the [[Icon language]]. They discussed the implementation alternatives of [[dynamic array]] algorithm used in linear hashing, and presented performance comparisons using a list of Icon benchmark applications.

==Adoption in database systems==
Linear hashing is used in the BDB Berkeley database system, which in turn is used by many software systems such as OpenLDAP, using a C implementation derived from the CACM article and first published on the Usenet in 1988 by Esmond Pitt.

==References==
{{Reflist}}

==External links==
*[http://www.concentric.net/~Ttwang/tech/sorthash.htm Sorted Linear Hash Table, C++ implementation of a Linear Hashtable]
*[http://tommyds.sourceforge.net/ TommyDS, C implementation of a Linear Hashtable]
*[http://hackthology.com/an-in-memory-go-implementation-of-linear-hashing.html An in Memory Go Implementation with Explanation]
* {{DADS|linear hashing|linearHashing}}
*[https://github.com/KevinStern/index-cpp/blob/master/src/linear_hashing_table.h A C++ Implementation of Linear Hashtable which Supports Both Filesystem and In-Memory Storage]

==See also==
* [[Extendible hashing]]
* [[Consistent hashing]]

[[Category:Search algorithms]]
[[Category:Hashing]]

formulasearchengine - User contributions [en]

Minkowski–Hlawka theorem