Minimean Optimal Key Arrangements in Hash Tables
Report ID: TR-145-88Author: Yao, Andrew
Date: 1988-03-00
Pages: 19
Download Formats: |PDF|
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.