(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.
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 E. Black.
Entry modified 18 August 2008.
HTML page formatted Mon Aug 25 09:01:40 2008.
Cite this as:
Paul E. Black, "dynamic hashing", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 18 August 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/dynamicHashing.html
