Non-oblivious hashing

Amos Fiat, Moni Naor, Jeanette P. Schmidt, Alan Siegel

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Non-oblivious hashing, where the information gathered by performing "unsuccessful" probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables: a. An 0(1) worst case scheme that requires only logarithmic additional memory (improving on the [FKS84] linear space upper bound). b. An almost sure 0(1) probabilistic worst case scheme, without any additional memory (improving on previous logarithmic time upper bounds). c. Enhancements to hashing: Solving (a) and (b) in the multikey record environment, search can be performed under any key in time 0(1); finding the nearest neighbor, the rank, etc. in logarithmic time. Our non-oblivious upper bounds are much better than the appropriate oblivious lower bounds.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)0897912640, 9780897912648
StatePublished - 1988
Event20th Annual ACM Symposium on Theory of Computing, STOC 1988 - Chicago, IL, United States
Duration: May 2 1988May 4 1988

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other20th Annual ACM Symposium on Theory of Computing, STOC 1988
Country/TerritoryUnited States
CityChicago, IL

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Non-oblivious hashing'. Together they form a unique fingerprint.

Cite this