On optimal arrangements of keys with double hashing

Abstract

Given a set of n keys, the keys are arranged in a hash table of size n such that the worst-case retrieval time is minimized. It is shown that, when double hashing is used, one can, with probability 1 - o(1), arrange the keys to achieve a worst-case retrieval time O(log n). This gives a solution to an open problem in Rivest (J. Assoc. Comput. Mach. 25 (1978), 200-209). © 1985.