Storage Utilization in a Memory Hierarchy When Storage Assignment Is Performed by a Hashing Algorithm The utilization of storage is studied in a two-level memory hierarchy. The first storage level, which is the fast store, is divided into a number of storage areas. When an entry is to be filed in the hierarchy, a hashing algorithm will attempt to place the entry into one of these areas. If this particular area is full, then the entry will be placed into the slower second-level store, even though other areas in the first-level store may have space available. Given the N entries have been filed in the entire hierarchy, an expression is derived for the expected number of entries filed in the first-level storehis expression gives a measure of how effectively the first-level store is being used. By means of examples, storage utilization is then studied as a function of the hashing algorithm, the number of storage areas into which the first-level store is divided and the total size of the first-level store. CACM March, 1971 Williams, J. G. hashing algorithms, memory allocation, memory hierarchy, memory utilization, storage allocation, storage hierarchy, storage utilization 3.74 4.3 CA710304 JB February 3, 1978 4:37 PM 2208 5 2208 2208 5 2208 2208 5 2208