Two-way chaining for non-uniform distributions

Two-way chaining is a novel hashing scheme with separate chaining that achieves O(log log n) expected maximum search time, when Theta (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].