On the program size of perfect and universal hash functions
- 1 November 1982
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 170-175
- https://doi.org/10.1109/sfcs.1982.80
Abstract
We address the question of program size of of perfect and universal hash functions. We prove matching upper and lower bounds (up to constant factors) on program size. Furthermore, we show that minimum or nearly minimum size programs can be found efficiently. In addition, these (near) minimum size programs have time complexity at most O(log* N) where N is the size of the universe in the case of perfect hashing, and time complexity 0(1) in the case of universal hashing. Thus for universal hashing programs of minimal size and minimal time complexity have been found.Keywords
This publication has 3 references indexed in Scilit:
- Reciprocal hashingCommunications of the ACM, 1981
- New classes and applications of hash functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979