Methods and apparatus for information storage and retrieval utilizing a method of hashing and different collision avoidance schemes depending upon clustering in the hash table

Abstract

An apparatus for performing storage and retrieval in an information storage system is disclosed which uses the hashing technique. In order to provide efficient and graceful operation under varying loading conditions, the system shifts between collision avoidance by linear probing with open addressing when the load is below a threshold, and collision avoidance by external chaining when the load is above a threshold. Insertion, deletion and retrieval operations are arranged to switch dynamically between the two collision avoidance stratagems as the local loading factor on the system, as measured by the number of records hashed to the same address, crosses preselected thresholds.

What is claimed is: 
     
       1. An information storage and retrieval system for data records using a portion of each said data record for generating a hashed storage address in said system, said system comprising storage means for storing a collision count for each set of said data records having identical hashed storage addresses,   first means responsive to said storage means for locally resolving collisions by open addressing when said collision count in said storage means is below a preselected threshold, and   second means responsive to said storage means for locally resolving collisions by external chaining when said collision count in said storage means is equal to or greater than said preselected threshold.   
     
     
       2. The information storage and retrieval system according to claim 1 further comprising means for storing one of said data records at said hashed storage address when said collision count is below said preselected threshold.   
     
     
       3. The information storage and retrieval system according to claim 1 further comprising means for storing a pointer to one of said data records at said at said hashed storage address when said collision count is equal to or greater than said preselected threshold.