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 \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} \]

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