Two-way chaining for non-uniform distributions
Ebrahim Malalla · International Journal of Computer Mathematics · 2008
Two-way chaining is a novel hashing scheme with separate chaining that achieves O(log log n) expected maximum search time, when Θ(n) data points are hashed via two independent uniform hash functions into a table of size n. In this note, we consider the two-way chaining scheme in the fixed density model, where the hashing values behave according to two fixed but possibly different densities on [0, 1].