Thumbnail
Access Restriction
Subscribed

Author Ackerman, A. Frank
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Hashing ♦ Quadratic search
Abstract It has previously been claimed [1 and 2] that the quadratic hash table search method of Maurer cannot usefully be applied to tables of size 2n. This is not so; the method can in fact be applied to tables of size pn for any prime p. It is shown below that rather simple conditions on the coefficients suffice to guarantee that all table locations will be examined once and only once. Specifically, if the equation is k + bi2 + ai mod pn (*) where k is the initial hash address and 0 ≤ i < pn, then, if p divides b but not a, the range of values is all the least positive residues of pn. To prove that all values are covered, we consider some fixed value, say k + bi20 + ai0 mod pn and ask, what conditions must be true if the congruence equation k + bi2 + ai ≡ k + bi02 + ai0 mod pn is to have solutions i, 0 ≤ i < pn, other than i0?
Description Affiliation: Bell Telephone Labs, New Brunswick, NJ (Ackerman, A. Frank)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 17
Issue Number 3


Open content in new tab

   Open content in new tab
Source: ACM Digital Library