General Purpose Scatter Storage Subsystem and a Comparison of Hashing Methods

摘要

Scatter storage techniques, sometimes referred to as hashing techniques, were developed to provide a means whereby external labels, or keys, may be mapped to some unique internal number, the latter generally being used as a storage location where information related to the key may be stored. The use of scatter storage techniques are required whenever the possible number of unique keys exceeds the number of available storage locations. Scatter storage techniques were originally developed for computer language compilers as a means of mapping program variable names to the computers internal storage locations. Due to the large number of possible variable names allowed by most compilers, it would be impractical to require any computer to provide a unique storage location for every possible variable name. A general purpose hashing subsystem designed to be easily implemented into existing application programs is presented. Also presented are various popular hashing algorithms as well as empirical test data characterizing the performance of each algorithm.