A New Analysis of Hashing Algorithm for External Searching

概要

論文の詳細を見る
Two mathematical analyses are proposed to evaluate exactly the number of accesses of the separate chaining method for external searching on secondary storage devices in consideration of the frequency of access on each key. The first one is compared to the traditional one based on the Knuth's model, and the second one is a new analysis based on the AHU (Aho, Hopcroft and Ullman) model. The evaluation formulae derived from the proposed analyses can exactly evaluate the average and variance of the search cost in conformity with any probability distribution of the frequency of access on a key, and then under the assumption that the frequency of access is uniform these formulae can be represented concisely and approximately by a function of the load factor and the bucket size.
一般社団法人情報処理学会の論文
1996-12-15