An Alternative Analysis of Dynamic Hashing Algorithms

概要

論文の詳細を見る
Linear and spiral hashing are well-known dynamic hashing methods. Traditional analyses of these two search algorithms have been proposed under the assumption that all keys are uniformly accessed; however, in general the search cost is defined as the product of the number of probes and the frequency of access to a key. Therefore, in this paper, we present a discrete analysis of the average search cost in consideration of the frequency of access to each key for these two dynamic hashing methods. In the proposed discrete analyses, the number of probes itself is regarded as a random variable and its probability distribution is derived. The evaluate formulae derived from the proposed analyses can exactly evaluate the average search cost in conformity with any probability distribution of the frequency of access.
一般社団法人情報処理学会の論文
2003-04-15