在开放寻址散列法中，散列表是一个数组 A 且每个桶均无拉链。数组中每个位置 要么包含一个散列项要么是空的。对每个待散列对象 x，散列函数 h 定义了数组 中的探测位置序列 h(x,0), h(x,1),….。Insert(x)如下操作：按照 h 定义的探测位置 序列 h(x,0), h(x,1),….在数组中寻找空位置 k，并将 x 存入 A[k]。Find(x)如下操作： 依次探查 h 定义的探测位置序列 h(x,0), h(x,1),….中的每个位置；如果 A[h(x,i)]=x, 则返回 h(x,i)，否则，返回-1 表明 x 未出现在散列表中。 假设用具有 2n 个存储位置的数组作为开放寻址散列表存储 n 个数据项，并 且 h(x,i)服从 0,1,…,2n-1 上的均匀分布，h(x,1), h(x,2)…相互独立。用 X（i 1in） 表示第 i 次执行 Insert 操作时探查的位置个数，X=maxiXi 表示 n 次插入操作中各 次操作的最大探查次数。 (1) 证明：Insert(x)需要探查 a 个存储位置的概率至多为 2 -a； (2) 证明：Pr[ Xi>2logn]  1/n 2 ; (3) 证明：Pr[ X>2logn]  1/n; (4) 证明：E[X] = O(logn)。

1. 对于第一部分，我们可以使用筒抽原理。在一个 2n 大小的数组中，对于每一个探测位置序列中的第 i 个位置，每个位置有 2 种可能：要么是空闲的，要么是已占用的。因此，探查 a 个存储位置都是已占用的概率为 (1/2)^a。显然，这个概率不会超过 (1/2)^a，即插入一个元素需要探查 a 个位置的概率至多为 2^(-a)。

2. 对于第二部分，我们需要考虑第 i 次 Insert 操作探查超过 2logn 个位置的概率。一个探查序列最长为 2n，因此，第 i 次探查超过 2logn 个位置的概率为 (2n - 2logn)/2n。令 A 表示探查次数超过 2logn 的事件，则我们有：

Pr[Xi>2logn] = Pr[A] ≤ (2n - 2logn)/2n = 1 - logn/n ≤ 1/n^2

因此，Pr[Xi>2logn]≤1/n^2。

3. 对于第三部分，我们需要考虑整个插入数据的过程，而不仅仅是第 i 次插入。插入 n 个不同的元素后，用 X(i) 表示第 i 次插入的探查次数，X=maxiXi。我们可以使用 Union Bound 技术：

Pr[X>2logn] = Pr[X1>2logn 或 X2>2logn 或 ... 或 Xn>2logn] ≤ nPr[Xi>2logn] ≤ 1/n

因为 Pr[Xi>2logn] ≤ 1/n^2，因此，Pr[X>2logn] ≤ 1/n。

4. 对于第四部分，我们可以使用期望值的定义来证明 E[X] = O(logn)。我们有：

E[X] = E[maxiXi] ≤ logn + E[∑(i=1)^n Xi - max Xi]

第一个不等式使用了最大值小于等于和的和小于等于最大值加和的性质。我们可以先证明 E[∑(i=1)^n Xi - max Xi] = O(logn)。我们可以将这个式子重新写成：

E[∑(i=1)^n Xi - max Xi] = E[∑(i=1)^(n-1) Xi - max Xi] + E[Xn- max(Xi)]

其中，第一个式子可以使用归纳法证明。对于第二个式子，我们需要考虑在插入第 n 个元素时，新元素的探查次数至多为 2logn，因此 E[Xn-max(Xi)] ≤ E[max(Xi)] ≤ logn。因此，我们得到 E[X] = O(logn)。