The Spatial Complexity of Oblivious k-Probe Hash Functions
Authors:
- Jeanette P. SchmidtJSJeanette P. Schmidt
- Alan SiegelASAlan Siegel
- 1 October 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 19 (5) , 775-786
Abstract
The problem of constructing a dense static hash-based lookup table T for a set of n elements belonging to a universe $U = \{ 0, 1, 2,\cdots , m -1 \}$ is considered. Nearly tight bounds on the spatial complexity of oblivious $O(1)$-probe hash functions, which are defined to depend solely on their search key argument, are provided. This establishes a significant gap between oblivious and nonoblivious search. In particular, the results include the following: • A lower bound showing that oblivious k-probe hash functions require a program size of $\Omega(({n / k}^{2})e^{-k}+\log \log m)$ bits, on average. • A probabilistic construction of a family of oblivious k-probe hash functions that can be specified in $O(n e^{-k} +\log \log m)$ bits, which nearly matches the above lower bound. • A variation of an explicit $O(1)$ time 1-probe (perfect) hash function family that can be specified in $O(n+\log \log m)$ bits, which is tight to within a constant factor of the lower bound.
Keywords
This publication has 20 references indexed in Scilit:
- Collections of Functions for Perfect HashingSIAM Journal on Computing, 1986
- Two results on tablesInformation Processing Letters, 1986
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- On the Size of Separating Systems and Families of Perfect Hash FunctionsSIAM Journal on Algebraic Discrete Methods, 1984
- Data Structures and Algorithms 11984
- On the program size of perfect and universal hash functions1982
- Expected Length of the Longest Probe Sequence in Hash Code SearchingJournal of the ACM, 1981
- An improved program for constructing open hash tablesLecture Notes in Computer Science, 1980
- Efficient Ordering of Hash TablesSIAM Journal on Computing, 1979
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973