Minimean Optimal Key Arrangements in Hash Tables

Abstract:

For an open-address hash function h and a set A of n keys, let Ch(A) be the expected retrieval cost when the keys are arranged to minimize the expected retrieval cost in a full table. It is shown that, asymptotically for large n, when h satisfies a certain doubly dispersive property, as is the case for
uniform hashing or double hashing, Ch(A) = O(1) with probability 1 - o(1) for a random A.