11. Hash Tables

Exercises

11.1-1

Available in the latest revision of the IM.

11.1-2

Available in the latest revision of the IM.

In java, the class BitSet implements a vector of bits that grows as needed. In C++, the class template bitset represents a fixed-size sequence of bits.

11.1-3

Available in the latest revision of the IM.

If any element with an equal key suffices to serve as a return value from Search, then there is no need to keep them all. Hence, we can avoid the usage of doubly linked lists, as in the IM, by working with $(x,count)$ ordered pairs, where $x$ is an object or pointer to an object. So, each slot is either nil (None in Python) or an ordered pair. Insertions increase, while deletions decrease these counters.

★ 11.1-4 🌟

Describes a scheme for implementing a direct-address dictionary on a huge array without incurring initialization penalty (setting arrays elements to NIL at creation).

Available in the latest revision of the IM.

Setting T[k]=nil on deletion is redundant, since T[k] becomes garbage (breaks the validating cycle).

11.2-1

Available in the latest revision of the IM.

11.2-2

We start with an empty table $T[0:8]$. Elements which appear to the left in the table have been added later.

Slot	Content
0	$\empty$
1	10, 19, 28
2	20
3	12
4	$\empty$
5	5
6	33, 15
7	$\empty$
8	17

11.2-3

Available in the latest revision of the IM.

11.2-4

Available in the latest revision of the IM.

11.2-5

Available in the latest revision of the IM.

11.2-6

Available in the latest revision of the IM.

11.3-1

Available in the latest revision of the IM.

11.3-2

Available in the latest revision of the IM.

The solution in the IM doesn't take into account the fact that the key is encoded as a radix-128 number. As it is implemented there, any permutation of characters of a string would produce the same hash value. So, the correct way is to apply Horner's rule. Let's assume that the key $k$ is represented as a sequence of characters $\langle s_1, s_2, \dots, s_r \rangle$ in big-endian format.

// Snippet of pseudocode to calculate h(k).
h = 0
for i = 1 to r:
    // Multiplying by 128 is shifting left by 7 positions.
    h = ((h << 7) + s[i]) mod m

11.3-3

Available in the latest revision of the IM.

The solution in the IM is incomplete, since it doesn't answer the last question from this exercise. A cryptographic hash function must ensure that any permutation of characters generate a different hash value. Otherwise, someone could rearrange a document without breaking a message digest used in a digital signature. Imagine an adversary being able to rearrange the bank account number and/or amount of a digitally signed transaction.

11.3-4

61 → 700 62 → 318 63 → 936 64 → 554 65 → 172

★ 11.3-5

Available in the latest revision of the IM.

★ 11.3-6

The size of our family of hash functions is $|\Z_p|=p$, as we have $p$ choices to select $b$. We need to calculate the probability of a collision $h_b(k_1)=h_b(k_2)$ for distinct keys $k_1$ and $k_2$. This probability is over the picks of $h_b$. Observe that

$$0 \le h_b(k_1),h_b(k_2)<p \implies -p < h_b(k_1)-h_b(k_2)<p,$$

which gives

$$h_b(k_1)-h_b(k_2)=0\space(\!\!\!\!\!\!\mod p) \implies h_b(k_1)=h_b(k_2).$$

We have the following equalities all taken modulo $p$

$$h_b(k_1)-h_b(k_2)=\sum_{j=0}^{d-1} k_{1j}b^j-\sum_{j=0}^{d-1} k_{2j}b^j=\sum_{j=0}^{d-1} (k_{1j}-k_{2j})b^j.$$

Following the hint from the book, according to Exercise 31.4-4, the above non-zero polynomial (due to $k_1 \neq k_2$) can have at most $d-1$ distinct zeros modulo $p$. In other words, at most $d-1$ choices of $b$ can lead to a collision. Therefore, our family of hash functions is $\epsilon$-universal for $\epsilon = (d-1)/p$.

11.4-1

Use VisuAlgo and select linear probing in the top menu bar. Choose the option in the left sidebar to create an empty hash table with $m=11$ slots and $n=0$ elements and press Go. Afterward, select the command to insert elements 10,22,31,4,15,28,17,88,59 and press Go.

For double hashing, the above website uses a different auxiliary hash function $h_2$, so we cannot use it. The hash table is filled as follows:

0	1	2	3	4	5	6	7	8	9	10
										10
22										10
22									31	10
22				4					31	10
22				4	15				31	10
22				4	15	28			31	10
22			17	4	15	28			31	10
22			17	4	15	28	88		31	10
22		59	17	4	15	28	88		31	10

11.4-2

Hash-Delete(T, k)
    i = Hash-Search(T, k)
    if i ≠ NIL
        T[i] = DELETED

The Hash-Insert procedure from the book requires a slight change in 4 line as follows:

if T[q] == NIL or T[q] == DELETED

The Hash-Search doesn't need any change.

11.4-3

Available in the latest revision of the IM.

11.4-4

Instead of doing integral approximation (see page 300), we simply use the definition of the $m$th harmonic humber.

$$\frac{1}{\alpha}\sum_{k=m-n+1}^m \frac{1}{k}=\sum_{k=1}^m \frac{1}{k}=H_m.$$

★ 11.4-5

According to Theorem 31.20, $|\langle h_2(k)\rangle|=m/d$. Since the sequence generates $m/d$ distinct offsets before repeating, the search examines exactly $m/d$ slots. Because the total table size is $m$, examining $m/d$ slots is exactly examining $(1/d)$th of the hash table.

★ 11.4-6

Enter solve 1/(1-x)=2/x ln(1/(1-x)) in WolframAlpha to get $\alpha \approx 0.71533$ by clicking on the Approximate form button inside the Result pane.

★ 11.5-1

$f_a^{(0)}(k)$ is an identity function, which is injective. If we prove that $f_a=f_a^{(1)}(k)$ is injective (base case), then $f_a^{(r)}(k)=f_a \circ f_a^{(r-1)}(k)$ for $r>1$ is also injective by induction on $r$. Note that the composition of two bijections is again a bijection (see Exercise B.3-4).

We know that the $swap$ function only rearranges the bits of an input independently of it's value, therefore $x=y \iff swap(x)=swap(y)$.

Suppose, for the sake of contradiction, that there are two distinct inputs $x$ and $y$ such that $f_a(x) =f_a(y)$. WLOG assume that $x>y$, otherwise, exchange them. Thus,

$$\begin{align*} &2x^2+ax = 2y^2+ay\space(\!\!\!\!\!\!\mod 2^{\omega}) \\ &\implies 2^{\omega} | (2x^2+ax) - (2y^2+ay) \\ &\implies 2^{\omega} | 2(x-y)(x+y)+a(x-y) \\ &\implies 2^{\omega} | (x-y)(2(x+y)+a) && \text{(contradiction!)}. \end{align*}$$

We have reached a contradiction, since $a$ is odd and $2^{\omega} ∤ (x-y)$. Recall that both $x$ and $y$ are $\omega$-bit words, hence $x-y < 2^{\omega}$. Consequently, $f_a$ is injective.

★ 11.5-2

A random oracle is equivalent to an independent uniform hash function family. Let us take 5 distinct keys $k_1,k_2,k_3,k_4,k_5$. Each will be independently and uniformly mapped by a random oracle to a slot in the range $[0,m)$. There are $m^5$ possible mappings, each with an equal probability of occurrence $1/m^5$. Thus, a random oracle is 5-independent according to the definition from the book on page 288.

Since a random oracle guarantees independence for any number of distinct inputs, it inherently satisfies 5-independence. 5-independence is a weaker condition than full independence; a fully independent function trivially satisfies $k$-independence for all $k$.

★ 11.5-3

At least $r=3$ rounds are required to trigger an avalanche effect potentially affecting any bit of the output to flip. In the illustration below, light red colored cells could be affected by flips in previous rounds. After 3 rounds, all cells are marked red, hence may be impacted by flipping a single bit of the input value $k$. Observe that flipping the most-significant bit of $k$ only impacts the most-significant bit of $g_a(k)$ in the first round. Any other bit of $k$ can only make the situation better. Hence, we consider a flip in bit position $\omega-1$ as the worst-case scenario. Note that round 0 is an identity function, so it is essentially the key itself. Each round consists of two parts: the upper is $g_a(k)$ and the lower is $f_a(k)$ of the corresponding round.

Problems

11-1 Longest-probe bound for hashing

Available in the latest revision of the IM.

11-2 Searching a static set

Available in the latest revision of the IM.

11-3 Slot-size bound for chaining

Available in the latest revision of the IM.

11-4 Hashing and authentication

a.

Arbitrarily pick two distinct keys $x,y \in U$. If $\mathcal{H}$ is 2-independent, then we can have $m^2$ different pairs $(h(x),h(y))$ of hash values with equal probability of occurrence $1/m^2$. Collisions are denoted by pairs $(i,i)$ for $i=0,1,\dots,m-1$. Therefore, the probability of a collision for two distinct keys is $m/m^2=1/m$. Consequently, $\mathcal{H}$ is universal.

b.

First, we show that is $\mathcal{H}$ universal. Arbitrarily pick two distinct keys $x,y \in U$. They must differ in at least one component. WLOG let it happen at index $0 \le i < n$. For a collision to occur, with a randomly picked hash function $h_a \in \mathcal{H}$, we must have $h_a(x)=h_a(y)$. Using the definition of $h_a$ we get

$$\begin{align*} &\sum_{j=0}^{n-1} a_jx_j = \sum_{j=0}^{n-1} a_jy_j \space(\!\!\!\!\!\!\mod p) \\ &\implies \sum_{j=0}^{n-1} a_j(x_j-y_j)=0 \space(\!\!\!\!\!\!\mod p) \\ &\implies a_i(x_i-y_i)=-\sum_{\substack{0\le j<n\\i \neq j}} a_j(x_j-y_j) \space(\!\!\!\!\!\!\mod p). \end{align*}$$

Observe that $-(p-1) \le x_i-y_i \le p-1$ and $x_i-y_i \neq 0$ implies that $x_i-y_i$ has a multiplicative inverse modulo $p$. Therefore,

$$a_i=-(x_i-y_i)^{-1}\sum_{\substack{0\le j<n\\i \neq j}} a_j(x_j-y_j) \pmod p \quad (1).$$

Notice that $a_i$ is fully determined based on the choice of $x$, $y$ and other components of $a$. Thus, the probability of a collision is $1/p$, since for a randomly selected $n$-tuple $a$, there are $p$ possible values at index $i$ and only one leads to a collision. Furthermore, if $h_a(x)=h_a(y)$ then all coefficients $a_k$, associated with corresponding non-zero terms $x_k-y_k$, simultaneously satisfy (1) (set $i=k)$. This shows that $\mathcal{H}$ is universal.

Following the hint from the book, it is easy to see that $x_0=\langle0,0,\dots,0\rangle$ always hashes to zero. Therefore, the condition to have $p^2$ unique pairs of hash values, with equal probability of occurrence, for any two distinct keys is not satisfied. Consequently, $\mathcal{H}$ is not 2-independent.

c.

Following the hint from the book, arbitrarily pick two distinct keys $x,y \in U$. They must differ in at least one component. WLOG let it happen at index $0 \le i < n$. Let's define the fixed sums of the other terms:

1. $c_x = \sum_{j \neq i} a_j x_j \pmod p$

2. $c_y = \sum_{j \neq i} a_j y_j \pmod p$

Now, we can set up the system of congruences for a collision:

1. $a_i x_i + b + c_x = u \pmod p$

2. $a_i y_i + b + c_y = v \pmod p$

To prove 2-independence, we just need to show that this system has exactly one unique solution for the pair $(a_i, b)$ for any given $u$ and $v$. We have

$$\begin{align*} a_i(x_i - y_i) + (c_x - c_y) &= u - v \pmod p \\ a_i(x_i - y_i) &= u - v - c_x + c_y \pmod p. \end{align*}$$

We can solve this using the analogous reasoning as in part (b)

$$\begin{align*} a_i &= (u - v - c_x + c_y)(x_i - y_i)^{-1} \pmod p \\ b &= u - a_i x_i - c_x \pmod p. \end{align*}$$

Therefore, the probability of mapping to any specific pair of outputs is exactly $1/p^2$, which strictly satisfies the definition of 2-independence.

d.

Since $\mathcal{H}$ is 2-independent, by part (a), it is also universal. The adversary may fool Bob, assuming that $m \neq m'$, if they can guess a tag $t'$ such that $h(m')=t'$, where $h$ denotes the shared hash function between Alice and Bob. We must decipher the probability that Alice and Bob had selected a random hash function that evaluates to this forged $t'$ for $m'$. Among those that produce $t$ for $m$ only $(1/p)$th generate $t'$ for $m'$. Therefore, the probability that the adversary succeeds in fooling Bob into accepting the forged message is at most $1/p$ no matter what.