Collections of Functions for Perfect Hashing
Authors:
- Francine BermanFBFrancine Berman
- Mary Ellen BockMBMary Ellen Bock
- Eric DittertEDEric Dittert
- Michael J. O’donnellMOMichael J. O’donnell
- Darrell PlankDPDarrell Plank
- 1 May 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (2) , 604-618
Abstract
Hashing techniques for accessing a table without searching it are usually designed to perform efficiently on the average over all possible contents of the table. If the table contents are known in advance, we might be able to choose a hashing function with guaranteed efficient (worst-case) performance. Such a technique has been called “perfect hashing” by Sprugnoli and others. In this paper, we address the question of whether perfect hashing is feasible in principle as a general technique, or whether it must rely on special qualities of the table contents. We approach the question by counting the number of functions which must be searched to be sure of finding a perfect hashing function. We present upper and lower bounds on the size of this search space, with attention to the tradeoff between the size of the search space and the size of the hash table.Keywords
This publication has 10 references indexed in Scilit:
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- On the program size of perfect and universal hash functions1982
- Geometric Problems with Application to HashingSIAM Journal on Computing, 1982
- Reciprocal hashingCommunications of the ACM, 1981
- Should Tables Be Sorted?Journal of the ACM, 1981
- Minimal perfect hash functions made simpleCommunications of the ACM, 1980
- Storing a sparse tableCommunications of the ACM, 1979
- Perfect hashing functionsCommunications of the ACM, 1977
- Universal classes of hash functions (Extended Abstract)1977
- Further Results on the Construction of Mutually Orthogonal Latin Squares and the Falsity of Euler's ConjectureCanadian Journal of Mathematics, 1960