Thumbnail
Access Restriction
Subscribed

Author Smith, Bradley J. ♦ Heileman, Gregory L. ♦ Abdallah, Chaouki
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1997
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword ADT ♦ Lyapunov exponent ♦ Chaos ♦ Dynamic dictionary ♦ Dynamical systems theory ♦ Exponential hashing ♦ Number theory
Abstract In this paper an efficient open address hash function called exponential hashing is developed. The motivation for this hash function resulted from our ongoing efforts to apply dynamical systems theory to the study of hashing; however, the analysis conducted in this paper is primarily based on traditional number theory. Proofs of optimal table parameter choices are provided for a number of hash functions. We also demonstrate experimentally that exponential hashing essentially matches the performance of a widely-used optimal double hash function for uniform data distributions, and performs significantly better for nonuniform data distributions. We show that exponential hashing exhibits a higher integer Lyapunov exponent and entropy than double hashing for initial data probes, which offers one explanation for its improved performance on nonuniform data distributions.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1997-01-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 2


Open content in new tab

   Open content in new tab
Source: ACM Digital Library