Expected Length of the Longest Probe Sequence in Hash Code Searching 论文

摘要

An investigation ts made of the expected value of the maximum number of accesses needed to locate any element m a hashing file under various colhston resoluuon schemes This differs from usual worst-case considerations winch, for hashmg, would be the largest sequence of accesses for the worst possible file Asymptotic expressxons of these expected values are found for full and partly full tables For the open addressing scheme with a clustering-free model these values are found to be 0.6315... x n for a full table and = -logan for a partly full table, where n ts the number of records, m is the size of the table, and a = n/m. For the open addressing scheme which reorders the insertions to minimize the worst case, the lower bounds In n + 1 077... and [-a-~in(l -a)] are found for full and partly full tables, respectively FmaUy, for the separate chaining (or direct chaining) method both expected values are found to be ~.F-t(n). These results show that for these schemes, the actual behawor of the worst case in hash tables is quite good on the average.