For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Alternative Analysis of Spiral Hashing Algorithm
Ayad SOUFIANE Tsuyoshi ITOKAWA Ryozo NAKAMURA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
discrete analysis dynamic hashing algorithm,
Full Text: PDF(226.7KB)>>
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.