Linear hashing with partial expansions

Abstract

A new method for organising dynamic files is presented and its performance is analysed. The scheme is a generalization of W. Litwin's linear (virtual) hashing. The amount of storage space allocated to the file grows and shrinks in a simple fashion according to the number of records actually stored in the file. The storage utilisation is controlled and constantly kept equal to a threshold selected by the user. Because no index or other form of access table is used, retrieval of a record requires only one access in most cases. The analysis reveals that an average search length in the range 1.1 - 1.2 accesses can easily be achieved, even for storage utilisations as high as 85-90 per cent.