Chaining Analysis

Expected number of steps to discover an item k is not in the hash table:

• We need to look at each item in the list T[h(k)].
• Under our uniform-hashing assumption, the h(k) slot looks like all the others.
• What's the expected number of keys in a slot?
• By linearity of expectation, the expected number of keys in a slot j is equal to $\sum_{i=1}^n \Pr(\mbox{key\ } i \mbox{\ goes\ in\ slot\ } j) = \sum_{i=1}^n 1/m = n/m = \alpha$.

So, running time is proportional to the load factor: $\Theta(1+\alpha)$.