Extendible hashing

Extendible hashing

Extendible hashing is a type of hash system which treats a hash as a bit string, and uses a trie for bucket lookup. [ Citation | title=Extendible Hashing - A Fast Access Method for Dynamic Files | journal=ACM Transactions on Database Systems | volume=4 | issue=3 | date=September, 1979 | first1=R. | last1=Fagin | first2=J. | last2=Nievergelt | first3=N. | last3=Pippenger | first4=H. R. | last4=Strong | pages=315–344 | doi=10.1145/320083.320092 | url=http://doi.acm.org/10.1145/320083.320092 ] Because of the hierarchal nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes.

References

See also

* Trie
* Hash table
* Stable hashing
* Consistent hashing

External links

*
* [http://www.isqa.unomaha.edu/haworth/isqa3300/fs009.htm Extendible Hashing] at University of Nebraska
* [http://www.csm.astate.edu/~rossa/datastruc/Extend.html Extendible Hashing notes] at Arkansas State University
* [http://www.inf.unibz.it/dis/teaching/DMS/lecturenotes/dms03.pdf Extendable Hashing] Lecture Slides at the Free University of Bolzano (Italy) (in english)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • 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

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • dbm — This article is about the family of database engines. For other uses, see dbm. dbm was the first of a family of simple database engines, originally written by Ken Thompson and released by AT T in 1979. The name is a three letter acronym for… …   Wikipedia

  • Berkeley DB — Original author(s) Margo Seltzer and Keith Bostic of Sleepycat Software Developer(s) Sleepycat Software, later Oracle Corporation Stable release 5.2.28 / June 10, 2011; 5 months ago …   Wikipedia

  • Trie — A trie for keys A , to , tea , ted , ten , i , in , and inn . In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search… …   Wikipedia

  • Radix tree — In computer science, a radix tree (also patricia trie or radix trie) is a space optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. Unlike… …   Wikipedia

  • SpadFS — Infobox filesystem name = SpadFS developer = Mikuláš Patočka full name = introduction date = introduction os = partition id = directory struct = file struct = bad blocks struct = max file size = max files no = max filename size = max volume size …   Wikipedia

Share the article and excerpts

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