In recent years a number of dynamic hashing schemes have been invented which allow for th extensibility of hash tables together with a guarantee of adequate efficiency. This paper presents a nonrandom extendible hasing scheme and a summary of the results of a performance analysis comparison between this technique and perfect randomization.

Two techniques of nonrandom hashing are suggested; one involves the use of packed decimal numbers; the other involves unpacked decimals. Both are described and analyzed within the framework of implementing access paths, as in database and file management systems.

The performance analysis is carried out by means of a simulation series. The results show that packed decimal keys can be used without randomization in extendible hashing with no significant degradation in either storage utilization or in directory size. As far as storage utilization is concerned, unpacked decimal key can also be used without randomization, but they show substantial growth in directory size.

An analysis of the efficiency of the packed decimal technique is presented in some detail. The representation chosen for each decimal key involves the use of a packed sequence of the EBCDIC codes for each digit. The analysis is somewhat dependent upon the technique chosen for splitting full buckets. The method used invovles an examination (moving left to right) of the individual bits in the EBCDIC representation of the key. While this results in some degradation in the performance of the method, the overall effect is not significant. Unfortunately, there is little explanation given for this choice of a splitting technique, which leaves the reader to wonder whether still better methods are available.