Definition: A hash table in which the hash function is the last few bits of the key and the table refers to buckets. Table entries with the same final bits may use the same bucket. If a bucket overflows, it splits, and if only one entry referred to it, the table doubles in size. If a bucket is emptied by deletion, entries using it are changed to refer to an adjoining bucket, and the table may be halved.
Generalization (I am a kind of ...)
Note: The table may be seen as a flattened complete binary tree where the buckets are (possibly) shared leaf nodes.
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, and H. Raymond Strong, Extendible Hashing - A Fast Access Method for Dynamic Files, ACM Transactions on Database Systems, 4(3):315-344, 1979.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 2 May 2005.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "extendible hashing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 2 May 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/extendibleHashing.html