Analysis of open addressing We make the assumption of uniform hashing Each key is equally likely to have any one of the m! permutations as its probe sequence Theorem. Given an open-addressed hash table with load factor a=n/m<1. the expected number of probes in an unsuccessful search is at most 1/(1-a) o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.21© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.21 Analysis of open addressing We make the assumption of uniform hashing: • Each key is equally likely to have any one of the m! permutations as its probe sequence. Theorem. Given an open-addressed hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1–α)