TY - JOUR
T1 - Spatial complexity of oblivious κ-probe hash functions
AU - Schmidt, Jeanette P.
AU - Siegel, Alan
PY - 1990
Y1 - 1990
N2 - 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,...,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 κ-probe hash functions require a program size of Ω((n/k2)e-k+ log log m) bits, on average. A probabilistic construction of a family of oblivious κ-probe hash functions that can be specified in O(ne-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.
AB - 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,...,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 κ-probe hash functions require a program size of Ω((n/k2)e-k+ log log m) bits, on average. A probabilistic construction of a family of oblivious κ-probe hash functions that can be specified in O(ne-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.
UR - http://www.scopus.com/inward/record.url?scp=0025507834&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025507834&partnerID=8YFLogxK
U2 - 10.1137/0219054
DO - 10.1137/0219054
M3 - Article
AN - SCOPUS:0025507834
SN - 0097-5397
VL - 19
SP - 775
EP - 786
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 5
ER -