A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table
Wei‐Pang Yang, Mingzhe Du · Very Large Data Bases · 1984
This paper presents a new dynamic file organization scheme based on hashing. The hash functions used here, being defined by extended hash indicator tables (EHITs), are both dynamic and perfect. The allocated storage space can be enlarged and shrunk without reorganizing the data file. Simulation results show'that the storage utilization is approximately equal to 70% in an experiment where the number of rehash functions s=7, the size of a segment r=lO, and the size of the key set n varies from 1 to 1000. Since the hash functions are perfect, the retrieval operation needs only one disk access.