Electrical & Computer Engineering Faculty Publications
Document Type
Article
Publication Date
4-12-2012
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.
Language (ISO)
English
Sponsorship
ACM
Keywords
chaos, dynamic dictionary, dynamical systems theory
Recommended Citation
Abdallah, Chaouki T.; Bradley J. Smith; and Gregory L. Heileman. "The exponential hash function." (2012). https://digitalrepository.unm.edu/ece_fsp/118
Comments
Pre-Print