(data structure)
Definition: A hash table that grows to handle more items. The associated hash function must change as the table grows. Some schemes may shrink the table to save space when items are deleted.
Generalization (I am a kind of ...)
hash table.
Specialization (... is a kind of me.)
extendible hashing, linear hashing, spiral storage.
Aggregate child (... is a part of or used in me.)
load factor.
See also expandable hashing, virtual hashing.
Note: See also Consistent hashing in Wikipedia. Consistent hashing allows mapping into arbitrary sets of buckets.
Author: PEB
R. J. Enbody and H. C. Du, Dynamic Hashing Schemes, ACM Computing Surveys, 20(2):85-113, June 1998.
Note: Figure 5b has errors: boxes should be labeled (top to bottom) A, D, B, and C.
Per-Åke Larson, Dynamic hashing, BIT 18(2):184-201, 1978.
Per-Åke Larson, Dynamic Hash Tables, CACM 31(4):446-457, April 1988.
Martin Dietzfelbinger, Anna Karlin, Kurt Melhorn, Friedhelm Meyer Auf Der Heide, Hans Rohnert, and Robert E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM J. Comput., 23(4):738-761, August 1994.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 10 June 2010.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "dynamic hashing", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 10 June 2010. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/dynamicHashing.html