11-1 Longest-probe bound for hashing

Suppose that we use an open-addressed hash table of size \(m\) to store \(n \le m / 2\) items.

a. Assuming uniform hashing, show that for \(i = 1, 2, \ldots, n\), the probability is at most \(2^{-k}\) that the \(i\)th insertion requires strictly more than \(k\) probes.

b. Show that for \(i = 1, 2, \ldots, n\), the probability is \(O(1 / n^2)\) that the \(i\)th insertion requires more than \(2\lg n\) probes.

Let the random variable \(X_i\) denote the number of probes required by the \(i\)th insertion. You have shown in part (b) that \(\Pr\\{X_i > 2\lg n\\} = O(1 / n^2)\). Let the random variable \(X = \max_{1 \le i \le n} X_i\) denote the maximum number of probes required by any of the \(n\) insertions.

c. Show that \(\Pr\\{X > 2\lg n\\} = O(1 / n)\).

d. Show that the expected length \(\text E[X]\) of the longest probe sequence is \(O(\lg n)\).

(Removed)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用