Extendible hashing
From Wikipedia, the free encyclopedia
Extendible hashing is a type of hash system which treats a hash as a bit string, and uses a trie for bucket lookup. [1] 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.
[edit] References
- ^ Fagin, R.; Nievergelt, J.; Pippenger, N. & Strong, H. R. (September, 1979), “Extendible Hashing - A Fast Access Method for Dynamic Files”, ACM Transactions on Database Systems 4 (3): 315-344, doi:10.1145/320083.320092, <http://doi.acm.org/10.1145/320083.320092>
[edit] See also
[edit] External links
- Paul E. Black, Extendible hashing at the NIST Dictionary of Algorithms and Data Structures.
- Extendible Hashing at University of Nebraska
- Extendible Hashing notes at Arkansas State University
- Extendable Hashing Lecture Slides at the Free University of Bolzano (Italy) (in english)
