Uniform-Hashing Assumption

So, clearly hashing with a bad hash function is not terribly useful.

So, let's assume we have a good one.

• For chaining: $\Pr(h(k) = j) = 1/m$ (the probability that a key ends up in slot j is 1/m for all slots).
• For open addressing: $\Pr(h'(k,i) = j) = 1/m$ (the probability that a key ends up in slot j on the ith probe is 1/m for all slots).