Spiral hashing

Spiral hashing, also known as Spiral Storage is an extensible hashing algorithm.[1][2][3][4][5] As in all hashing schemes, spiral hashing stores records in a varying number of buckets, using a record key for addressing. In an expanding Linear hashing file, buckets are split in a predefined order. This results in adding a new bucket at the end of the file. While this allows gradual reorganization of the file, the expected number of records in the newly created bucket and the bucket from what it splits falls to half the previous number. Several attempts were made to alleviate this sudden drop in space utilization. Martin's spiral storage uses a different approach. The file consists of a number of continuously numbered buckets. The lower-numbered (left) buckets have a higher expected number of records. When the file expands, the left-most bucket is replaced by two buckets on the right. Some variants of this idea exist.[6] [7][8]

Spiral hashing requires a uniform hash function of the keys of the records into the unit interval  [ 0 , 1 ] {\displaystyle [0,1]} . If the hash file starts at bucket  S {\displaystyle S} , the key  k {\displaystyle k} is mapped into a real number  x = S + h ( k ) ∈ [ S , S + 1 ] {\displaystyle x=S+h(k)\in [S,S+1]} . The final address is then computed as  ⌊ d x ⌋ {\displaystyle \lfloor d^{x}\rfloor } where  d {\displaystyle d} is the "extension factor". When  S {\displaystyle S} is incremented, approximately  d {\displaystyle d} new buckets are created on the right. Larson [9] conducted experiments that showed that Linear hashing still had superior performance over Spiral Hashing.

## See also

[edit]

* Extendible hashing
* Linear hashing

## References

[edit]

1. ^ Martin, G.N. (1979), "Spiral Storage", Tech. Rep. 27, Univ. Of Warwick, Coventry, UK
2. ^ Mullin, James K. (1981), "Tightly controlled linear hashing without separate overflow storage", BIT Numerical Mathematics, 21 (4): 390–400, doi:10.1007/BF01932837, S2CID 43311559
3. ^ Mullin, James K. (1985), "Spiral storage: Efficient dynamic hashing with constant performance", The Computer Journal, 28 (3): 330–334, doi:10.1093/comjnl/28.3.330
4. ^ Chu, J-H.; Knott, G.D. (1994), "An analysis of spiral hashing", The Computer Journal, 37 (8): 715-719, doi:10.1093/comjnl/37.8.715
5. ^ Enbody, Richard; Du, HC (June 1988), "Dynamic hashing schemes", ACM Computing Surveys, 20 (2): 85–113, doi:10.1145/46157.330532, S2CID 1437123
6. ^ Mullin, James K. (1984), "Unified Dynamic Hashing", Proceedings 10th International Conference on Very Large Databases (VLDB)
7. ^ Kawagoe, K. (1985), "Modified Dynamic Hashing", Proceedings SIGMOD international conference on management of data
8. ^ Chang, Ye-In; Lee, Chien-I; ChangLiaw, Wann-Bay (1999), "Linear spiral hashing for expansible files", IEEE Transactions on Knowledge and Data Engineering, 11 (6)
9. ^ Larson, Per-Åke (April 1988), "Dynamic Hash Tables", Communications of the ACM, 31 (4): 446–457, doi:10.1145/42404.42410, S2CID 207548097