(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 Wed Feb 4 11:02:23 2009.
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.itl.nist.gov/div897/sqg/dads/HTML/spiralStorage.html