BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-85-1038
       ENTRY:: May 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Uniform hashing is optimal
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew C.
        DATE:: January 1985
       PAGES:: 10
    ABSTRACT:: It was conjectured by J. Ullman that uniform hashing is
               optimal in its expected retrieval cost among all open-address
               hashing schemes (JACM 19 (1972), 569-575). In this paper we
               show that, for any open-address hashing scheme, the expected
               cost of retrieving a record from a large table which is
               alpha-fraction full is at least 1/alpha log 1/1-alpha + o(1).
               This proves Ullman's conjecture to be true in the asymptotic
               sense.
       NOTES:: [Adminitrivia V1/Prg/19950501]
         END:: STAN//CS-TR-85-1038