Nonoblivious Hashing

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

Research output: Contribution to journalArticle

Abstract

Nonoblivious hashing, where information gathered from unsuccessful probes is used to modify subsequent probe strategy, is introduced and used to obtain the following results for static lookup on full tables: 1992 An O(1)-time worst-case scheme that uses only logarithmic additional memory, (and no memory when the domain size is linear in the table size), which improves upon previously linear space requirements. (2) An almost sure O(1)-time probabilistic worst-case scheme, which uses no additional memory and which improves upon previously logarithmic time requirements. (3) Enhancements to hashing: (1) and (2) are solved for multikey recors, where search can be performed under any key in time O(1); these schemes also permit properties, such as nearest neighbor and rank, to be determined in logarithmic time.

Original languageEnglish (US)
Pages (from-to)764-782
Number of pages19
JournalJournal of the ACM (JACM)
Volume39
Issue number4
DOIs
StatePublished - Jan 10 1992

Keywords

  • O(1) probe search
  • dictionary problem
  • model of computation
  • oblivious and nonoblivious search
  • perfect hashing
  • upper and lower bounds

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Nonoblivious Hashing'. Together they form a unique fingerprint.

  • Cite this