Proofs: Linear hashing

Expected and amortized cost of linear hashing full

This proof shows: time.search, time.insert, time.delete, space.

We use the names of the page and of the correctness proof: $M = N 2^L$, $B = M + p$, and the invariant (I1) to (I4). Time is counted on the word RAM, with $O(1)$ for one evaluation of $h$, for one comparison of keys, and for one step over a pair of a list. Appending a list to the array of buckets and removing the last one cost $O(1)$ amortized, as in a dynamic array.

Assumption (A). Let $R$ be a multiple of every $2M$ that occurs, for example $R = N 2^w$ for a large $w$. The values $h(k)$ of all keys that occur are independent and uniform on $\{0, \ldots, R - 1\}$, and the sequence of operations is fixed in advance, so it does not depend on these values. Under (A), $h(k) \bmod M$ and $h(k) \bmod 2M$ are uniform for every $M$ that occurs, because $M$ and $2M$ divide $R$.

Lemma 1 (a fixed bucket). In a state with (I1), for each key $k$ and each bucket $j$, $\Pr[\mathrm{addr}(k) = j] \le 1/M < 2/B$.

Proof. If $p \le j < M$, the event is $h(k) \bmod M = j$, with probability $1/M$. If $j < p$ or $j \ge M$, the event is $h(k) \bmod 2M = j$, with probability $1/(2M)$. Each other $j$ has probability 0 by Lemma 1 of the correctness proof. Finally $B = M + p < 2M$ gives $1/M < 2/B$. $\square$

The state at any time, that is, $n$, $L$, $p$ and the set of stored keys, depends only on the sequence of operations, because the decisions of lines L10 and D4 use only $n$ and $B$. The hash values decide only which list holds which key. This is what lets Lemma 1 apply at each step.

Search. Let the query be $k$. Condition on $h(k)$; this fixes the bucket $j = \mathrm{addr}(k)$. Each stored key $k' \ne k$ is in bucket $j$ with probability at most $1/M$, independently of $h(k)$, by (A) and Lemma 1. So the expected number of pairs with a key other than $k$ in the list is at most $n / M < 2n / B \le 2 \alpha_{\max}$ by (I4). The scan of lines L4 to L6 steps over these pairs and over at most one pair with key $k$. So SEARCH takes $O(1 + \alpha_{\max})$ expected time, whether $k$ is present or not.

The number of splits per insertion. Before INSERT, (I4) gives $n \le \alpha_{\max} B$. After line L9 there are at most $n + 1$ pairs. Let $s = \lceil 1 / \alpha_{\max} \rceil$. After $s$ splits, $\alpha_{\max} (B + s) \ge \alpha_{\max} B + 1 \ge n + 1$, so the loop of line L10 stops after at most $s$ splits.

The cost of one split. A split runs when the table holds some number $n'$ of pairs with $n' \le \alpha_{\max} B_0 + 1$, where $B_0 \le B$ is the size before the insertion and $B$ the current size. It scans the list $p$, an unsplit bucket. By Lemma 1, its expected length is at most $n' / M < 2 n' / B \le 2 \alpha_{\max} + 2 / B \le 2 \alpha_{\max} + 2$. With the $O(1)$ amortized cost of line L11, a split costs $O(1 + \alpha_{\max})$ expected amortized time.

The cost of one merge. A merge runs when $n < \alpha_{\min} B$. It moves the pairs of the last list, a split bucket, whose expected length is at most $n / (2M) < n / B < \alpha_{\min}$ by Lemma 1. So a merge costs $O(1 + \alpha_{\min}) = O(1 + \alpha_{\max})$ expected amortized time.

Insert and delete. Lines L7 to L9 and D1 to D3 scan one list, with the bound of the search: $O(1 + \alpha_{\max})$ expected time. Start from NEW, with $B = N$. Each split adds one bucket and each merge removes one, and $B \ge N$ at all times, so over any sequence the number of merges is at most the number of splits. The number of splits is at most $s$ times the number of insertions. So a sequence of $m$ operations does at most $2 s m$ splits and merges, with expected total cost $O(s m (1 + \alpha_{\max}))$, and $O(m (1 + \alpha_{\max}))$ for the scans. Since $s \le 1 + 1/\alpha_{\max}$, the expected amortized cost of each operation is

which is $O(1)$ when $\alpha_{\max}$ is a positive constant.

Worst case. Without (A), all keys may share one list. Then one scan costs $O(n)$, and one split or merge costs $O(n)$. The loop of line L10 does at most $s$ splits. The loop of line D4 does at most $B - N$ merges, which move at most $n$ pairs in total, so it costs $O(n + B)$.

Space. The structure holds $B$ lists and $n$ pairs, so it uses $\Theta(B + n)$ words. If $\alpha_{\min} > 0$, then $B \le \max(N, n / \alpha_{\min} + 1)$ after each operation. This holds after NEW, where $B = N$. A search and a replacement of a value change neither $n$ nor $B$. An insertion without a split makes $n$ larger and keeps $B$. An insertion with splits ends with a split that ran because $n > \alpha_{\max} (B - 1)$ for the final $B$, so $B < n / \alpha_{\max} + 1 \le n / \alpha_{\min} + 1$. A deletion ends the loop of line D4 either with $B = N$ or with $n \ge \alpha_{\min} B$. So the space is $O(N + n / \alpha_{\min})$ words. $\blacksquare$

Linear hashing keeps its invariant and answers each operation correctly full

This proof shows: correctness, termination.

We use the names of the page: $N \ge 1$, $\alpha_{\max} > 0$, $0 \le \alpha_{\min} \le \alpha_{\max} / 2$, the level $L$, the pointer $p$, the number of pairs $n$, the array of $B$ lists, and $M = N 2^L$. For a pair $(L, p)$ we write

This is the value of ADDRESS (lines L1 to L3). We call $(L, p)$ extended valid if $L \ge 0$, $0 \le p \le M$ and $B = M + p$. It is valid if also $p < M$; this is (I1).

Lemma 1 (the address is a bucket). If $(L, p)$ is extended valid, then $0 \le \mathrm{addr}_{L,p}(k) < B$ for every key $k$. Moreover $\mathrm{addr}_{L,p}(k) = j$ implies $h(k) \bmod M = j \bmod M$.

Proof. Let $r = h(k) \bmod M$. If $r \ge p$, the address is $r$ with $p \le r < M \le B$. If $r < p$, the address $a = h(k) \bmod 2M$ satisfies $a \bmod M = r$, because $M$ divides $2M$; so $a = r$ or $a = r + M$, and both are less than $p + M = B$. In both cases $a \bmod M = r$. $\square$

Lemma 2 (end of a round). If $p = M$, then $(L, M)$ and $(L + 1, 0)$ give the same $B$ and the same address for every key.

Proof. $B = M + M = 2M = 2M + 0$. Under $(L, M)$ every $r = h(k) \bmod M$ is less than $p = M$, so the address is $h(k) \bmod 2M$. Under $(L + 1, 0)$ the small table has size $2M$ and every value is at least $p = 0$, so the address is again $h(k) \bmod 2M$. $\square$

Lemma 3 (SPLIT). Assume (I1), (I2) and (I3) before SPLIT. Then after SPLIT, (I1), (I2) and (I3) hold, $n$ is the same, and $B$ is one larger.

Proof. Let $L, p, M, B = M + p$ be the values before. Line L11 adds the list with index $B = p + M$. Consider a pair $(k, v)$ in the old list $\mathit{bucket}[p]$. By (I2), $\mathrm{addr}_{L,p}(k) = p$, so by Lemma 1, $h(k) \bmod M = p$. Then $h(k) \bmod 2M$ is $p$ or $p + M$, and line L14 puts the pair in that list, which exists after line L11. Lines L12 to L14 move only the pairs of $\mathit{bucket}[p]$ and keep each of them, so (I3) holds and $n$ does not change.

Line L15 sets $p' = p + 1 \le M$, and $(L, p')$ is extended valid with $B + 1 = M + p'$. We show that each pair is in the list $\mathrm{addr}_{L,p'}(k)$. Let $r = h(k) \bmod M$.

• If $r = p$, the pair came from the old $\mathit{bucket}[p]$, because by (I2) and Lemma 1 every pair with $r = p$ was in the list $p$ (its old address was $r = p$, since $r \ge p$). Now $r < p'$, so its new address is $h(k) \bmod 2M$, which is the list of line L14.
• If $r > p$, then $r \ge p'$, and both the old and the new address are $r$. The pair did not move.
• If $r < p$, then $r < p'$, and both addresses are $h(k) \bmod 2M$. The pair did not move.

If $p' < M$, line L16 does nothing and $(L, p')$ is valid. If $p' = M$, line L16 sets $(L + 1, 0)$, which is valid because $0 < 2M$, and by Lemma 2 neither $B$ nor any address changes. So (I1) and (I2) hold. $\square$

Lemma 4 (MERGE). Assume (I1), (I2), (I3) and $B > N$ before MERGE. Then after MERGE, (I1), (I2) and (I3) hold, $n$ is the same, and $B$ is one smaller.

Proof. First, line M1. If $p = 0$, then $B = M = N 2^L > N$, so $L \ge 1$. Line M1 sets $L' = L - 1$ and $p' = N 2^{L'} = M / 2$. The pair $(L', p')$ is extended valid with $p' = N 2^{L'}$, and by Lemma 2 applied to it, it has the same $B$ and the same addresses as $(L, 0)$. So after line M1 we have an extended valid state with $1 \le p \le M$, for its own $M$, in which (I2) and (I3) hold. If $p \ge 1$ at the start, the same is true without a change.

Now let $q = p - 1$, so $0 \le q < M$, and the last list has index $B - 1 = M + q$. By Lemma 1, each pair in the list $M + q$ and each pair in the list $q$ has $h(k) \bmod M = q$. Line M2 sets the pointer to $q$. Let $r = h(k) \bmod M$ for a pair $(k, v)$.

• If $r = q$, the pair was in the list $q$ or in the list $M + q$, since its old address was $h(k) \bmod 2M$, which is one of these two. Its new address is $r = q$, because now $r \ge q$. Line M3 moves the pairs of the list $M + q$ to the list $q$, so the pair is in the list $q$.
• If $r > q$, then $r \ge p$ (the old pointer), and both the old and the new address are $r$.
• If $r < q$, both the old and the new address are $h(k) \bmod 2M$.

After line M3 the list $M + q$ is empty, and line M4 removes it. Now $B = M + q$ with $0 \le q < M$, so (I1) holds, and (I2) holds by the three cases. Line M3 moves pairs without loss or copy, so (I3) holds and $n$ does not change. $\square$

Theorem. NEW makes a state that satisfies (I1) to (I4). If (I1) to (I4) hold before an operation, then SEARCH, INSERT and DELETE terminate, return the value that the abstract type asks for, and leave a state that satisfies (I1) to (I4) and represents the new map.

Proof.

NEW. $L = 0$, $p = 0 < N = M$, and $B = N$, so (I1) holds. There are no pairs and $n = 0$, so (I2), (I3) and (I4) hold.

SEARCH$(k)$. By (I2), a pair with key $k$ can only be in the list $\mathrm{addr}(k)$, which exists by Lemma 1, and by (I3) there is at most one such pair. Lines L4 to L6 scan this list, which is finite, and return its value or NIL. The state does not change.

INSERT$(k, v)$. If $k$ is present, its pair is in the list $a$ of line L7 by (I2), and line L8 replaces its value. The keys, $n$ and $B$ do not change, so (I1) to (I4) hold, and the map now sends $k$ to $v$. Otherwise line L9 appends $(k, v)$ to the list $\mathrm{addr}(k)$, so (I2) holds for the new pair, (I3) holds with $n + 1$, and (I1) is unchanged. By Lemma 3, each SPLIT of line L10 keeps (I1) to (I3) and $n$, and makes $B$ one larger. So the loop ends after at most $\lceil n / \alpha_{\max} \rceil$ steps, which is a finite number, and at the end $n \le \alpha_{\max} B$, which is (I4).

DELETE$(k)$. By (I2) and (I3), lines D1 and D2 find the pair of $k$ exactly when $k$ is present; if it is absent, nothing changes and the result is false. Otherwise line D3 removes the pair and sets $n$ to $n - 1$; (I1) to (I3) hold, and (I4) holds because $n$ decreased. Each step of the loop of line D4 runs with $B > N$, so Lemma 4 applies: (I1) to (I3) stay true and $B$ drops by 1. The loop ends after at most $B - N$ steps. For (I4): a step runs only when $n < \alpha_{\min} B$, with $B \ge 2$ because $B > N \ge 1$. Then after the step

where the last inequality is $B \le 2(B - 1)$, true for $B \ge 2$. So (I4) holds for the new size $B - 1$. The result is true, and the map no longer has $k$.

In each case the set of pairs is exactly the new map, by (I3) and the description of each step. $\blacksquare$