11-3 Quadratic probing

Suppose that we are given a key \(k\) to search for in a hash table with positions \(0, 1, \ldots, m - 1\), and suppose that we have a hash function \(h\) mapping the key space into the set \(\\{0, 1, \ldots, m - 1\\}\). The search scheme is as follows:

1. Compute the value \(j = h(k)\), and set \(i = 0\).
2. Probe in position \(j\) for the desired key \(k\). If you find it, or if this position is empty, terminate the search.
3. Set \(i = i + 1\). If \(i\) now equals \(m\), the table is full, so terminate the search. Otherwise, set \(j = (i + j) \mod m\), and return to step 2.

Assume that \(m\) is a power of \(2\).

a. Show that this scheme is an instance of the general "quadratic probing" scheme by exhibiting the appropriate constants \(c_1\) and \(c_2\) for equation \(\text{(11.5)}\).

b. Prove that this algorithm examines every table position in the worst case.

(Removed)

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