An exponential open hashing function based on dynamical systems theory
Bradley Jay Smith · 1997
this paper an efficient open addressing hash function called exponential hashing is developed using concepts from dynamical systems theory and number theory. A comparison of exponential hashing versus a widely-used double hash function is performed using an analysis based on Lyapunov exponents and entropy. Proofs of optimal table parameter choices are provided for a number of hash functions. We also demonstrate experimentally that exponential hashing nearly matches the performance of an 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: E.1 [Data Structures]: tables; E.2 [Data Storage Representation ]: hash-table representations; H.3.3 [Information Storage and Retrieval]: Information Storage and Retrieval General Terms: Algorithms Additional Key Words and Phrases: Chaos, dynamic dictionary ADT, dynamical systems theory, exponential hashing, lyapunov exponent, number theory 1. INTRODUCTION