An exponential open hashing function based on dynamical systems theory

Pre-PrintIn 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.The University of New Mexic