Two-way chaining for non-uniform distributions

Abstract

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].

Keywords:

• two-way chaining
• worst-case search time
• non-uniform distributions
• multiple choice allocation process
• witness tree

2000 AMS Subject Classification :

• 68Q25
• 68P10
• 68P20
• 68W20
• 68W40

Acknowledgements

The author would like to thank Luc Devroye for suggesting this problem and for his invaluable advice. The author also wishes to acknowledge the support provided by KFUPM.