dynamic hashing

(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

Implementation

Charles B. Falconer's hashlib (C) including several example applications. Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.

More information

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.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 25 July 2006.
HTML page formatted Mon Sep 11 09:46:02 2006.

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. 25 July 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/dynamicHashing.html