File organization using composite perfect hashing
- 1 June 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 14 (2) , 231-263
- https://doi.org/10.1145/63500.63521
Abstract
Perfect hashing refers to hashing with no overflows. We propose and analyze a composite perfect hashing scheme for large external files. The scheme guarantees retrieval of any record in a single disk access. Insertions and deletions are simple, and the file size may vary considerably without adversely affecting the performance. A simple variant of the scheme supports efficient range searches in addition to being a completely dynamic file organization scheme. These advantages are achieved at the cost of a small amount of additional internal storage and increased cost of insertions.Keywords
This publication has 24 references indexed in Scilit:
- An Interactive System for Finding Perfect Hash FunctionsIEEE Software, 1985
- Practical Perfect HashingThe Computer Journal, 1985
- The TWA reservation systemCommunications of the ACM, 1984
- Minimal and almost minimal perfect hash function search with application to natural language lexicon designComputers & Mathematics with Applications, 1983
- Storing a sparse table with O(1) worst case access timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Minimal perfect hash functions made simpleCommunications of the ACM, 1980
- Extendible hashing—a fast access method for dynamic filesACM Transactions on Database Systems, 1979
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- Combinatorial Chance.Economica, 1962
- Combinatorial extreme value distributionsMathematika, 1959