NIST

spiral storage

(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=ceiling( S-h(k)) +h(k), is computed to find the final slot, floor( dx), where d>1 is called the growth factor. To increase the number of slots, increase S to S' and rehash any keys from floor( dS) to floor( 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 floor( dS) to floor( dS+1)-1, they are usually remapped to physical storage.

Author: PEB

More information

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.


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

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

Entry modified 25 July 2006.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "spiral storage", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 25 July 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/spiralStorage.html