Portal de Periódicos da CAPES

Linear hashing with overflow-handling by linear probing

1985; Association for Computing Machinery; Volume: 10; Issue: 1 Linguagem: Inglês

10.1145/3148.3324

1557-4644

Per-Åke Larson,

Caching and Content Delivery

Linear hashing is a file structure for dynamic files. In this paper, a new, simple method for handling overflow records in connection with linear hashing is proposed. The method is based on linear probing and does not rely on chaining. No dedicated overflow area is required. The expansion sequence of liner hashing is modified to improve the performance, which requires changes in the address computation. A new address computation algorithm and an expansion algorithm are given. The performance of the method is studied by simulation. The algorithms for the basic file operations are very simple, and the overall performance is competitive with that of other variants of linear hashing.