An Alternative Analysis of Linear Dynamic Hashing Algorithm

概要

論文の詳細を見る
The linear hashing is a well-known dynamic hashing algorithm designed for internal main memory as well as external secondary memory. 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 of the linear dynamic hashing algorithm for internal main memory in consideration of the frequency of access on each key. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. Furthermore, the evaluate formula derived from the proposed analysis can exactly evaluate the average search cost in conformity with any probability distribution of the frequency of access. The proposed analysis is compared to the traditional one provided that the frequency of access on each key is uniform, and the differences are discussed.
社団法人電子情報通信学会の論文
2003-05-01