Suppose that we insert n keys into a hash table of size m using open addressing and uniform hashing. Let p(n, m) be the probability that no collisions occur. Show that p(n, m) ≤ e^(-n(n-1)/2m). (Hint: See equation (3.11).) Argue that when n exceeds sqrt(m), the probability of avoiding collisions goes rapidly to zero.
下面采用数学归纳法证明p(n,m) ≤ e^((-n(n-1))/2m)，1≤n≤m：
1).当n=1时，因为只有一个关键字不会有冲突，所以p(1,m)=1 ≤ e^((-1(1-1))/2m) = 1成立;
2).假设n=k时，p(k,m) ≤ e^((-k(k-1))/2m),k < m-1成立。
因为第k+1个关键字的探查序列等可能为0,1,…,m-1的所有排列中的任何一种，所以第k+1个关键字的探查序列的第一个探查位置h(k+1,0)等可能为0,1,…,m-1中的任何一个。故在前k个关键字无冲突的条件下，第k+1个关键字的探查序列的第一个探查位置，h(k+1,0)不与前面的k个关键字中的任何一个关键字冲突，那么这k+1个关键字也没有冲突。
所以：
p(k+1,m) = p(k,m)*(m-k)/m
≤ e^((-k(k-1))/2m)*(1-k.m)
≤ e^((-k(k-1))/2m) * e^(-k/m)
= e^((-(k+1)k)/2m)即p(k+1,m) = e^((-(k+1)k)/2m)。
3)综上，p(n,m) ≤ e^((-n(n-1))/2m)，对于1≤n≤m成立。
Follow @louis1992 on github to help finish this task.