Non-oblivious hashing

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

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

Abstract

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
Pages367-376
Number of pages10
ISBN (Print)0897912640, 9780897912648
DOIs
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

Other

Other20th Annual ACM Symposium on Theory of Computing, STOC 1988
CountryUnited States
CityChicago, IL
Period5/2/885/4/88

ASJC Scopus subject areas

  • Software

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

Cite this