An Open Hash Method Using Predictors

概要

論文の詳細を見る
In the scatter storage technique, many methods of resolving collisions have been proposed. Those are classified into two main methods, i.e. the open hash method and the chaining method. A measure of efficiency for a table search is the average number E of probes necessary to retrieve a key in the table. The average number E of the open hash method is always greater than that of the chaining method. In this paper, it is shown that the predictor method, which uses a several bit field reserved in each cell and is applicable to the open hash method, significanyly reduces the average probe number E. The efficiency of the predictor method is estimated theoretically and verified experimentally. A comparison with the chaining method is also made with respect to the memory usage.
一般社団法人情報処理学会の論文