17.4 Dynamic tables

17.4-1

Suppose that we wish to implement a dynamic, open-address hash table. Why might we consider the table to be full when its load factor reaches some value $\alpha$ that is strictly less than $1$? Describe briefly how to make insertion into a dynamic, open-address hash table run in such a way that the expected value of the amortized cost per insertion is $O(1)$. Why is the expected value of the actual cost per insertion not necessarily $O(1)$ for all insertions?

By theorems 11.6-11.8, the expected cost of performing insertions and searches in an open address hash table approaches infinity as the load factor approaches one, for any load factor fixed away from $1$, the expected time is bounded by a constant though. The expected value of the actual cost my not be $O(1)$ for every insertion because the actual cost may include copying out the current values from the current table into a larger table because it became too full. This would take time that is linear in the number of elements stored.

17.4-2

Show that if $\alpha_{i - 1} \ge 1 / 2$ and the $i$th operation on a dynamic table is $\text{TABLE-DELETE}$, then the amortized cost of the operation with respect to the potential function $\text{(17.6)}$ is bounded above by a constant.

If $\alpha_{i - 1} \ge 1 / 2$, $\text{TABLE-DELETE}$ cannot contract, so $c_i = 1$ and $size_i = size_{i - 1}$.

  • Case 1: if $\alpha_{i - 1} \ge 1 / 2$,

    $$ \begin{aligned} \hat c_i & = c_i + \Phi_i - \Phi_{i - 1} \\ & = 1 + (2 \cdot num_i - size_i) - (2 \cdot num_{i - 1} - size_{i - 1}) \\ & = 1 + (2 \cdot (num_{i - 1} - 1) - size_{i - 1}) - (2 \cdot num_{i - 1} - size_{i - 1}) \\ & = -1. \end{aligned} $$

  • Case 2: if $\alpha_i < 1 / 2$,

    $$ \begin{aligned} \hat c_i & = c_i + \Phi_i - \Phi_{i - 1} \\ & = 1 + (size_i / 2 - num_i) - (2 \cdot num_{i - 1} - size_{i - 1}) \\ & = 1 + (size_{i - 1} / 2 - (num_{i - 1} - 1)) - (2 \cdot num_{i - 1} - size_{i - 1}) \\ & = 2 + \frac{3}{2} size_{i - 1} - 3 \cdot num_{i - 1} \\ & = 2 + \frac{3}{2} size_{i - 1} - 3\alpha_{i - 1} size_{i - 1} \\ & \le 2 + \frac{3}{2} size_{i - 1} - \frac{3}{2} size_{i - 1} \\ & = 2. \end{aligned} $$

17.4-3

Suppose that instead of contracting a table by halving its size when its load factor drops below $1 / 4$, we contract it by multiplying its size by $2 / 3$ when its load factor drops below $1 / 3$. Using the potential function

$$\Phi(T) = | 2 \cdot T.num - T.size |,$$

show that the amortized cost of a $\text{TABLE-DELETE}$ that uses this strategy is bounded above by a constant.

If $1 / 3 < \alpha_i \le 1 / 2$,

$$ \begin{aligned} \hat c_i & = c_i + \Phi_i - \Phi_{i - 1} \\ & = 1 + (size_i - 2 \cdot num_i) - (size_i - 2 \cdot (num_i + 1)) \\ & = 3. \end{aligned} $$

If the $i$th operation does trigger a contraction,

$$ \begin{aligned} \frac{1}{3} size_{i - 1} & = num_i + 1 \\ size_{i - 1} & = 3 (num_i + 1) \\ size_{i} & = \frac{2}{3} size_{i - 1} = 2 (num_i + 1). \end{aligned} $$

$$ \begin{aligned} \hat c_i & = c_i + \Phi_i - \Phi_{i - 1} \\ & = (num_i + 1) + [2 \cdot (num_i + 1) - 2 \cdot num_i] - [3 \cdot (num_i + 1) - 2 \cdot (num_i + 1)] \\ & = 2. \end{aligned} $$