跳转至

11.4 Open addressing

11.4-1

Consider inserting the keys \(10, 22, 31, 4, 15, 28, 17, 88, 59\) into a hash table of length \(m = 11\) using open addressing with the auxiliary hash function \(h'(k) = k\). Illustrate the result of inserting these keys using linear probing, using quadratic probing with \(c_1 = 1\) and \(c_2 = 3\), and using double hashing with \(h_1(k) = k\) and \(h_2(k) = 1 + (k \mod (m - 1))\).

We use \(T_t\) to represent each time stamp \(t\) starting with \(i = 0\), and if encountering a collision, then we iterate \(i\) from \(i = 1\) to \(i = m - 1 = 10\) until there is no collision.

  • Linear probing:

    \[ \begin{array}{r|ccccccccc} h(k, i) = (k + i) \mod 11 & T_0 & T_1 & T_2 & T_3 & T_4 & T_5 & T_6 & T_7 & T_8 \\\\ \hline 0 \mod 11 & & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 \\\\ 1 \mod 11 & & & & & & & & 88 & 88 \\\\ 2 \mod 11 & & & & & & & & & \\\\ 3 \mod 11 & & & & & & & & & \\\\ 4 \mod 11 & & & & 4 & 4 & 4 & 4 & 4 & 4 \\\\ 5 \mod 11 & & & & & 15 & 15 & 15 & 15 & 15 \\\\ 6 \mod 11 & & & & & & 28 & 28 & 28 & 28 \\\\ 7 \mod 11 & & & & & & & 17 & 17 & 17 \\\\ 8 \mod 11 & & & & & & & & & 59 \\\\ 9 \mod 11 & & & 31 & 31 & 31 & 31 & 31 & 31 & 31 \\\\ 10 \mod 11 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \end{array} \]

  • Quadradic probing, it will look identical until there is a collision on inserting the fifth element:

    \[ \begin{array}{r|ccccccccc} h(k, i) = (k + i + 3i^2) \mod 11 & T_0 & T_1 & T_2 & T_3 & T_4 & T_5 & T_6 & T_7 & T_8 \\\\ \hline 0 \mod 11 & & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 \\\\ 1 \mod 11 & & & & & & & & & \\\\ 2 \mod 11 & & & & & & & & 88 & 88 \\\\ 3 \mod 11 & & & & & & & 17 & 17 & 17 \\\\ 4 \mod 11 & & & & 4 & 4 & 4 & 4 & 4 & 4 \\\\ 5 \mod 11 & & & & & & & & & \\\\ 6 \mod 11 & & & & & & 28 & 28 & 28 & 28 \\\\ 7 \mod 11 & & & & & & & & & 59 \\\\ 8 \mod 11 & & & & & 15 & 15 & 15 & 15 & 15 \\\\ 9 \mod 11 & & & 31 & 31 & 31 & 31 & 31 & 31 & 31 \\\\ 10 \mod 11 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \end{array} \]

Note that there is no way to insert the element \(59\) now, because the offsets coming from \(c_1 = 1\) and \(c_2 = 3\) can only be even, and an odd offset would be required to insert \(59\) because \(59 \mod 11 = 4\) and all the empty positions are at odd indices.

  • Double hashing:

    \[ \begin{array}{r|ccccccccc} h(k, i) = (k + i(1 + k \mod 10)) \mod 11 & T_0 & T_1 & T_2 & T_3 & T_4 & T_5 & T_6 & T_7 & T_8 \\\\ \hline 0 \mod 11 & & 22 & 22 & 22 & 22 & 22 & 22 & 22 & 22 \\\\ 1 \mod 11 & & & & & & & & & \\\\ 2 \mod 11 & & & & & & & & & 59 \\\\ 3 \mod 11 & & & & & & & 17 & 17 & 17 \\\\ 4 \mod 11 & & & & 4 & 4 & 4 & 4 & 4 & 4 \\\\ 5 \mod 11 & & & & & 15 & 15 & 15 & 15 & 15 \\\\ 6 \mod 11 & & & & & & 28 & 28 & 28 & 28 \\\\ 7 \mod 11 & & & & & & & & 88 & 88 \\\\ 8 \mod 11 & & & & & & & & & \\\\ 9 \mod 11 & & & 31 & 31 & 31 & 31 & 31 & 31 & 31 \\\\ 10 \mod 11 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \end{array} \]

11.4-2

Write pseudocode for \(\text{HASH-DELETE}\) as outlined in the text, and modify \(\text{HASH-INSERT}\) to handle the special value \(\text{DELETED}\).

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
HASH-DELETE(T, k)
    i = 0
    repeat
        j = h(k, i)
        if T[j] == k
            T[j] = DELETE
            return j
        else i = i + 1
    until T[j] == NIL or i == m
    error "element not exist"

By implementing \(\text{HASH-DELETE}\) in this way, the \(\text{HASH-INSERT}\) need to be modified to treat \(\text{NIL}\) slots as empty ones.

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
HASH-INSERT(T, k)
    i = 0
    repeat
        j = h(k, i)
        if T[j] == NIL or T[j] == DELETE
            T[j] = k
            return j
        else i = i + 1
    until i == m
    error "hash table overflow"

11.4-3

Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is \(3 / 4\) and when it is \(7 / 8\).

  • \(\alpha = 3 / 4\),

    • unsuccessful: \(\frac{1}{1 - \frac{3}{4}} = 4\) probes,
    • successful: \(\frac{1}{\frac{3}{4}} \ln\frac{1}{1-\frac{3}{4}} \approx 1.848\) probes.

  • \(\alpha = 7 / 8\),

    • unsuccessful: \(\frac{1}{1 - \frac{7}{8}} = 8\) probes,
    • successful: \(\frac{1}{\frac{7}{8}} \ln\frac{1}{1 - \frac{7}{8}} \approx 2.377\) probes.

11.4-4 \(\star\)

Suppose that we use double hashing to resolve collisions—that is, we use the hash function \(h(k, i) = (h_1(k) + ih_2(k)) \mod m\). Show that if \(m\) and \(h_2(k)\) have greatest common divisor \(d \ge 1\) for some key \(k\), then an unsuccessful search for key \(k\) examines \((1/d)\)th of the hash table before returning to slot \(h_1(k)\). Thus, when \(d = 1\), so that \(m\) and \(h_2(k)\) are relatively prime, the search may examine the entire hash table. (\(\textit{Hint:}\) See Chapter 31.)

Suppose \(d = \gcd(m, h_2(k))\), the \(\text{LCM}\) \(l = m \cdot h_2(k) / d\).

Since \(d | h_2(k)\), then \(m \cdot h_2(k) / d \mod m = 0 \cdot (h_2(k) / d \mod m) = 0\), therefore \((l + ih_2(k)) \mod m = ih_2(k) \mod m\), which means \(ih_2(k) \mod m\) has a period of \(m / d\).

11.4-5 \(\star\)

Consider an open-address hash table with a load factor \(\alpha\). Find the nonzero value \(\alpha\) for which the expected number of probes in an unsuccessful search equals twice the expected number of probes in a successful search. Use the upper bounds given by Theorems 11.6 and 11.8 for these expected numbers of probes.

\[ \begin{aligned} \frac{1}{1 - \alpha} & = 2 \cdot \frac{1}{\alpha} \ln\frac{1}{1 - \alpha} \\\\ \alpha & = 0.71533. \end{aligned} \]
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用