### Nonoblivious hashingNonoblivious hashing

Access Restriction
Subscribed

 Author Fiat, Amos ♦ Naor, Moni ♦ Schmidt, Jeanette P. ♦ Siegel, Alan Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1992 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword O(1) probe search ♦ Dictionary problem ♦ Model of computation ♦ Oblivious and nonoblivious search ♦ Perfect hashing ♦ Upper and lower bounds 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:(1) An $\textit{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 $\textit{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 $\textit{O}(1);$ these schemes also permit properties, such as nearest neighbor and rank, to be determined in logarithmic time. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1992-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 39 Issue Number 4 Page Count 19 Starting Page 764 Ending Page 782

#### Open content in new tab

Source: ACM Digital Library