The Exponential Hash Function

Bradley J. Smith, Gregory L. Heileman, Chaouki Abdallah

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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. Categories and Subject Descriptors: R.1 [Data Structures]: tables; E.2 [Data Storage Representation]: hash-table representations; H.3.3 [Information Storage and Retrieval]: Information Storage and Retrieval.

Original languageEnglish (US)
Pages (from-to)3
Number of pages1
JournalACM Journal of Experimental Algorithmics
StatePublished - Jan 1 1997
Externally publishedYes


  • Algorithms
  • Chaos
  • Lyapunov exponent
  • dynamic dictionary ADT
  • dynamical systems theory
  • exponential hashing
  • number theory

ASJC Scopus subject areas

  • Theoretical Computer Science


Dive into the research topics of 'The Exponential Hash Function'. Together they form a unique fingerprint.

Cite this