Linear hash

Linear Hashing is a dynamic hash table algorithm invented by Witold Litwin (1980) [ 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] , 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 ofthe collision chain. The cost of hash table expansion is spread out across eachhash table insertion operation, as opposed to be incurred all at once. [ 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] Thereforelinear 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 thatis 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 greaterthan or equal to the 'split' variable. Otherwise, address(level+1,key) is used.

A linear hashing table expansion operation would consist of rehashing theentries at slot location indicated by the 'split' variable to the target slot locationof address(level+1,key). The 'split' variable is incremented by 1 at the end ofthe 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 choiceis to control the expansion with a programmer defined load factor.

The hash table array for linear hashing is usually implemented with a dynamic arrayalgorithm.

Adoption in language systems

Griswold and Townsend [ Citation | title=The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon | first1=William G. | last1=Griswold | first2=Gregg M. | last2=Townsend | journal=Software - Practice and Experience | volume=23 | issue=4 | date=April 1993 | pages=pp. 351-367 | url=http://citeseer.ist.psu.edu/griswold93design.html ] 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.

References

External links

* [http://www.concentric.net/~Ttwang/tech/sorthash.htm Sorted Linear Hash Table]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Hash function — A hash function is any well defined procedure or mathematical function for turning some kind of data into a relatively small integer, that may serve as an index into an array. The values returned by a hash function are called hash values, hash… …   Wikipedia

  • Linear probing — is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location. [cite book |last=Dale |first=Nell |title=C++ Plus Data Structures |year=2003… …   Wikipedia

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • Linear search — In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular value. It operates by checking every element of a list one at a time in sequence until a… …   Wikipedia

  • Hash collision — In computer science, a hash collision or hash clash is a situation that occurs when two distinct inputs into a hash function produce identical outputs.All hash functions have potential collisions, though with a well designed hash function,… …   Wikipedia

  • The Hash Function Hamsi — Содержание 1 Краткое описание 2 История 3 The Hash Funtion Hamsi 3.1 Общая структу …   Википедия

  • Rolling hash — A rolling hash is a hash function where the input is hashed in a window that moves through the input.A few hash functions allow a rolling hash to be computed very quickly the new hash value is rapidly calculated given only the old hash value, the …   Wikipedia

  • Perfekte Hash-Funktion — Eine Perfekte Hash Funktion ist eine Hash Funktion , welche unterschiedliche Elemente aus einer endlichen und festen Schlüsselmenge S auf unterschiedliche Elemente aus einer Bildmenge T abbildet (keine Kollisionen, Injektivität). Aus der… …   Deutsch Wikipedia

  • Distributed Hash Table — Eine verteilte Hashtabelle (VHT) [engl.: distributed hash table (DHT)] ist eine Datenstruktur, die versucht, das allgemeine Problem in P2P Systemen – das Finden des Speicherorts einer gesuchten Datei – mit möglichst geringem Aufwand effizient zu… …   Deutsch Wikipedia

  • Differential-linear attack — Introduced by Martin Hellman and Susan K. Langford in 1994, the differential linear attack is a mix of both linear cryptanalysis and differential cryptanalysis. The attack utilises a differential characteristic over part of the cipher with a… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.