Skip to content

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}$.

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.

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} $$