(data structure)
Definition:
A dynamic hashing table that grows a few slots at a time. It uses a hash function, h, with a range of [0,1). For a key, k, an intermediate value, x= S-h(k)
+h(k), is computed to find the final slot,
dx
, where d>1 is called the growth factor. To increase the number of slots, increase S to S' and rehash any keys from
dS
to
dS'
-1.
Generalization (I am a kind of ...)
dynamic hashing.
See also linear hashing.
Note:
Choosing d=2 and S=log2N, the number of slots, every expansion retires one slot and creates two new slots. Since slots in use go from dS
to
dS+1
-1, they are usually remapped to physical storage.
Author: PEB
G. N. N. Martin, Spiral storage: Incrementally augmentable hash addressed storage, Theory of Computation Rep. 27, Univ. of Warwick, England, 1979.
Per-Åke Larson, Dynamic Hash Tables, CACM 31(4):446-457, April 1988.
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:08 2006.
Cite this as:
Paul E. Black, "spiral storage", 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/spiralStorage.html