Chapter 11.4

1. line probing
h(10, 0) = 10
|---+---+---+---+---+---+---+---+---+---+----|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---+---+---+---+---+---+---+---+---+---+----|
|   |   |   |   |   |   |   |   |   |   | 10 |
|---+---+---+---+---+---+---+---+---+---+----|

h(22, 0) = 0
|----+---+---+---+---+---+---+---+---+---+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|----+---+---+---+---+---+---+---+---+---+----|
| 22 |   |   |   |   |   |   |   |   |   | 10 |
|----+---+---+---+---+---+---+---+---+---+----|

h(31, 0) = 9
|----+---+---+---+---+---+---+---+---+----+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |  9 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|
| 22 |   |   |   |   |   |   |   |   | 31 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|

h(4, 0) = 4
|----+---+---+---+---+---+---+---+---+----+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |  9 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|
| 22 |   |   |   | 4 |   |   |   |   | 31 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|

h(15, 0) = 4
h(15, 1) = 5
|----+---+---+---+---+----+---+---+---+----+----|
|  0 | 1 | 2 | 3 | 4 |  5 | 6 | 7 | 8 |  9 | 10 |
|----+---+---+---+---+----+---+---+---+----+----|
| 22 |   |   |   | 4 | 15 |   |   |   | 31 | 10 |
|----+---+---+---+---+----+---+---+---+----+----|

h(28, 0) = 6
|----+---+---+---+---+----+----+---+---+----+----|
|  0 | 1 | 2 | 3 | 4 |  5 |  6 | 7 | 8 |  9 | 10 |
|----+---+---+---+---+----+----+---+---+----+----|
| 22 |   |   |   | 4 | 15 | 28 |   |   | 31 | 10 |
|----+---+---+---+---+----+----+---+---+----+----|

h(17, 0) = 6
h(17, 1) = 7
|----+---+---+---+---+----+----+----+---+----+----|
|  0 | 1 | 2 | 3 | 4 |  5 |  6 |  7 | 8 |  9 | 10 |
|----+---+---+---+---+----+----+----+---+----+----|
| 22 |   |   |   | 4 | 15 | 28 | 17 |   | 31 | 10 |
|----+---+---+---+---+----+----+----+---+----+----|

h(88, 0) = 0
h(88, 1) = 1
|----+----+---+---+---+----+----+----+---+----+----|
|  0 |  1 | 2 | 3 | 4 |  5 |  6 |  7 | 8 |  9 | 10 |
|----+----+---+---+---+----+----+----+---+----+----|
| 22 | 88 |   |   | 4 | 15 | 28 | 17 |   | 31 | 10 |
|----+----+---+---+---+----+----+----+---+----+----|

h(59, 0) = 4
h(59, 1) = 5
h(59, 2) = 6
h(59, 3) = 7
h(59, 4) = 8
|----+----+---+---+---+----+----+----+----+----+----|
|  0 |  1 | 2 | 3 | 4 |  5 |  6 |  7 |  8 |  9 | 10 |
|----+----+---+---+---+----+----+----+----+----+----|
| 22 | 88 |   |   | 4 | 15 | 28 | 17 | 59 | 31 | 10 |
|----+----+---+---+---+----+----+----+----+----+----|

2. quadratic probing
h(10, 0) = 10
|---+---+---+---+---+---+---+---+---+---+----|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---+---+---+---+---+---+---+---+---+---+----|
|   |   |   |   |   |   |   |   |   |   | 10 |
|---+---+---+---+---+---+---+---+---+---+----|

h(22, 0) = 0
|----+---+---+---+---+---+---+---+---+---+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|----+---+---+---+---+---+---+---+---+---+----|
| 22 |   |   |   |   |   |   |   |   |   | 10 |
|----+---+---+---+---+---+---+---+---+---+----|

h(31, 0) = 9
|----+---+---+---+---+---+---+---+---+----+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |  9 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|
| 22 |   |   |   |   |   |   |   |   | 31 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|

h(4, 0) = 4
|----+---+---+---+---+---+---+---+---+----+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |  9 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|
| 22 |   |   |   | 4 |   |   |   |   | 31 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|

h(15, 0) = 4
h(15, 1) = 8
|----+---+---+---+---+---+---+---+----+----+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |  8 |  9 | 10 |
|----+---+---+---+---+---+---+---+----+----+----|
| 22 |   |   |   | 4 |   |   |   | 15 | 31 | 10 |
|----+---+---+---+---+---+---+---+----+----+----|

h(28, 0) = 6
|----+---+---+---+---+---+----+---+----+----+----|
|  0 | 1 | 2 | 3 | 4 | 5 |  6 | 7 |  8 |  9 | 10 |
|----+---+---+---+---+---+----+---+----+----+----|
| 22 |   |   |   | 4 |   | 28 |   | 15 | 31 | 10 |
|----+---+---+---+---+---+----+---+----+----+----|

h(17, 0) = 6
h(17, 1) = 10
h(17, 2) = 9
h(17, 3) = 3
|----+---+---+----+---+---+----+---+----+----+----|
|  0 | 1 | 2 |  3 | 4 | 5 |  6 | 7 |  8 |  9 | 10 |
|----+---+---+----+---+---+----+---+----+----+----|
| 22 |   |   | 17 | 4 |   | 28 |   | 15 | 31 | 10 |
|----+---+---+----+---+---+----+---+----+----+----|

h(88, 0) = 0
h(88, 1) = 4
h(88, 2) = 3
h(88, 3) = 8
h(88, 4) = 8
h(88, 5) = 3
h(88, 6) = 4
h(88, 7) = 0
h(88, 8) = 2
|----+---+----+----+---+---+----+---+----+----+----|
|  0 | 1 |  2 |  3 | 4 | 5 |  6 | 7 |  8 |  9 | 10 |
|----+---+----+----+---+---+----+---+----+----+----|
| 22 |   | 88 | 17 | 4 |   | 28 |   | 15 | 31 | 10 |
|----+---+----+----+---+---+----+---+----+----+----|


h(59, 0) = 4
h(59, 1) = 8
h(59, 2) = 7
|----+---+----+----+---+---+----+----+----+----+----|
|  0 | 1 |  2 |  3 | 4 | 5 |  6 |  7 |  8 |  9 | 10 |
|----+---+----+----+---+---+----+----+----+----+----|
| 22 |   | 88 | 17 | 4 |   | 28 | 59 | 15 | 31 | 10 |
|----+---+----+----+---+---+----+----+----+----+----|


3. double hashing
h(10, 0) = 10
|---+---+---+---+---+---+---+---+---+---+----|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---+---+---+---+---+---+---+---+---+---+----|
|   |   |   |   |   |   |   |   |   |   | 10 |
|---+---+---+---+---+---+---+---+---+---+----|

h(22, 0) = 0
|----+---+---+---+---+---+---+---+---+---+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|----+---+---+---+---+---+---+---+---+---+----|
| 22 |   |   |   |   |   |   |   |   |   | 10 |
|----+---+---+---+---+---+---+---+---+---+----|

h(31, 0) = 9
|----+---+---+---+---+---+---+---+---+----+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |  9 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|
| 22 |   |   |   |   |   |   |   |   | 31 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|

h(4, 0) = 4
|----+---+---+---+---+---+---+---+---+----+----|
|  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |  9 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|
| 22 |   |   |   | 4 |   |   |   |   | 31 | 10 |
|----+---+---+---+---+---+---+---+---+----+----|

h(15, 0) = 4
h(15, 1) = 10
h(15, 2) = 5
|----+---+---+---+---+----+---+---+---+----+----|
|  0 | 1 | 2 | 3 | 4 |  5 | 6 | 7 | 8 |  9 | 10 |
|----+---+---+---+---+----+---+---+---+----+----|
| 22 |   |   |   | 4 | 15 |   |   |   | 31 | 10 |
|----+---+---+---+---+----+---+---+---+----+----|

h(28, 0) = 6
h(28, 1) = 4
h(28, 2) = 2
|----+---+----+---+---+----+---+---+---+----+----|
|  0 | 1 |  2 | 3 | 4 |  5 | 6 | 7 | 8 |  9 | 10 |
|----+---+----+---+---+----+---+---+---+----+----|
| 22 |   | 28 |   | 4 | 15 |   |   |   | 31 | 10 |
|----+---+----+---+---+----+---+---+---+----+----|

h(17, 0) = 6
h(17, 1) = 3
|----+---+----+----+---+----+---+---+---+----+----|
|  0 | 1 |  2 |  3 | 4 |  5 | 6 | 7 | 8 |  9 | 10 |
|----+---+----+----+---+----+---+---+---+----+----|
| 22 |   | 28 | 17 | 4 | 15 |   |   |   | 31 | 10 |
|----+---+----+----+---+----+---+---+---+----+----|

h(88, 0) = 0
h(88, 1) = 9
h(88, 2) = 7
|----+---+----+----+---+----+---+----+---+----+----|
|  0 | 1 |  2 |  3 | 4 |  5 | 6 |  7 | 8 |  9 | 10 |
|----+---+----+----+---+----+---+----+---+----+----|
| 22 |   | 28 | 17 | 4 | 15 |   | 88 |   | 31 | 10 |
|----+---+----+----+---+----+---+----+---+----+----|

h(59, 0) = 4
h(59, 1) = 3
h(59, 2) = 2
h(59, 3) = 1
|----+----+----+----+---+----+---+----+---+----+----|
|  0 |  1 |  2 |  3 | 4 |  5 | 6 |  7 | 8 |  9 | 10 |
|----+----+----+----+---+----+---+----+---+----+----|
| 22 | 59 | 28 | 17 | 4 | 15 |   | 88 |   | 31 | 10 |
|----+----+----+----+---+----+---+----+---+----+----|

HASH-DELETE(T, k)
    i = HASH-SEARCH(k)
    if i != NIL
        T[i] = DELETED

HASH-INSERT(T, k)
    i = 0
    repeat
        j = h(k, i)
        if T[j] == NIL or T[j] == DELETED
            T[j] = k
            return j
        else i = i + 1
    until i == m
    error "hash table overflow"

When the load factor is \(3 / 4\), the upper bound on the expected number of probes in an unsuccessful search is \(4\), the upper bound on the expected number of probes in a successful search is \(\frac{4\ln4}{3}\approx 1.848\).

When the load factor is \(7 / 8\), the upper bound on the expected number of probes in an unsuccessful search is \(8\), the upper bound on the expected number of probes in a successful search is \(\frac{8\ln8}{7}\approx 2.377\).

From theorem 31.24, we know that the equation \(ih_2(k)\equiv 0\pmod{m}\) has exactly \(d\) distinct solutions, modulo m, given by \(i_k = k(m/d)\) for \(k=0,1,\dots,d-1\), thus the first unsuccessful search appears when \(i=m/d\), which means \(1/d\)th of the hash table was examined before returning to slot \(h_1(k)\). Thus, when \(d=1\), the search may examine the entire table.

To 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, we need to solve the equation below.

\begin{align*} \frac{1}{1-\alpha}=\frac{2}{\alpha}\ln\frac{1}{1-\alpha} \end{align*}

To solve the equation, we need to use the Lambert W function, which is the inverse function of \(f(w) = w\mathrm{e}^w\).

\begin{align*} &\frac{1}{1-\alpha}=\frac{2}{\alpha}\ln\frac{1}{1-\alpha}\\ \implies&\mathrm{e}^{\frac{\alpha}{2(1-\alpha)}}=\frac{1}{1-\alpha}\\ \implies&-\frac{1}{2}\mathrm{e}^{-\frac{1}{2}}=\frac{1}{2(\alpha-1)} \mathrm{e}^{\frac{1}{2(\alpha-1)}}\\ \implies&\frac{1}{2(\alpha-1)}=W(-\frac{1}{2}\mathrm{e}^{-\frac{1}{2}}) \end{align*}

Since \(-\frac{1}{\mathrm{e}}< -\frac{1}{2}\mathrm{e}^{-\frac{1}{2}}< 0\), we could use two branches \(W_0\) and \(W_{-1}\) when dealing with real numbers only, after calculation, we found the result \(\alpha \approx 0.7153\).