Unified Dynamic Hashing
James K. Mullin · 1984
This paper attempts to unify a variety of dynamic hashing methods. Spiral storage, linear hashing and- to a certain extent, linear hashing with partial expansions can be seen as particular cases of a more general technique. The approach is closest to spiral storage in concept. A new instantiation of the general method is offered which permits an adjustment to the dynamic growth rate during expansion. In addition, “optimai” performance results if a sufficiently accurate estimate of the file size is possible. Introduct ion Since 1979, a number of dynamic hashing methods have been discovered. Dynamic hashing methods are hash based, direct access storage methods which maintain good performance while the storage space is kept proportional to storage demand. Thus large underestimates of the space required do not result in poor performance or the need for a complete reorganization. We assume a conventional environment where records are mapped into physical device buckets. Each bucket has space for a number of records. The operations of fetch, insert and delete are performed on records-- each with a unique identifying key.