An Open Hash Method Using Predictors

IPSJ

Search this article

Description

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.

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.

Journal

Details 詳細情報について

Report a problem

Back to top