An Alternative Analysis of Spiral Hashing Algorithm

Ayad SOUFIANE  Tsuyoshi ITOKAWA  Ryozo NAKAMURA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.5   pp.988-993
Publication Date: 2002/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
discrete analysis dynamic hashing algorithm,  

Full Text: PDF(226.7KB)>>
Buy this Article




Summary: 
Spiral hashing is a well known dynamic hashing algorithm. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost in consideration of the frequency of access on each key for this spiral hashing algorithm. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. The evaluate formulae derived from the proposed analysis can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access.