## 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,...,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/k^{2})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.

Original language | English (US) |
---|---|

Pages (from-to) | 775-786 |

Number of pages | 12 |

Journal | SIAM Journal on Computing |

Volume | 19 |

Issue number | 5 |

DOIs | |

State | Published - 1990 |

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics