Why does double hashing create a permutation?

Question

Question

Let $\mathbb{N} = \{0, 1, 2, \dots \}$, $\mathbb{N}^+ = \mathbb{N} - \{0\}$, $m \in \mathbb{N}^+$, $[m] := \{0, 1, \dots, m-1\}$ and define the function $f:[m]\to[m]$ as below

$$f(i) = (a + i \, b) \bmod m,$$

where $a, \, b \in \mathbb{N}$. I want to show that $\big( f(0), f(1), \dots, f(m-1) \big)$ is a permutation of $(0, 1, \dots, m-1)$ provided that $b$ and $m$ are relatively prime.

---

Motivation

In open address hash tables, hash functions are of the form

$$h:U \times \{0, 1, \dots, m-1\} \to \{0, 1, \dots, m-1\}, \tag{1}$$

where $U$ is the set of all possible keys. It is required that the sequence of probes defined as

$$p(k) := \big(h(k, 0), \, h(k, 1), \dots, \, h(k, m-1)\big) \tag{2}$$

generates a permutation of $(0,1,\dots,m-1)$ for every key $k \in U$, which guarantees that all of the hash table slots will be visited in a probe sequence. One way to get around this is by double hashing. In this method, the hash function is defined as below

$$h(k,i):=f(k) + i \, g(k) \bmod m, \tag{3}$$

where $f$ and $g$ are functions of the form

$$f:U \to \{0, 1, \dots, m-1\}, \qquad g:U \to \{0, 1, \dots, m-1\}.$$

In order to have the permutation property, we have the following theorem.

Theorem. If $g(k)$ and $m$ are relatively prime then $p(k)$ is a permutation of $(0,1,\dots,m-1)$.

Answer 1

If we want to show that $\big(f(0), f(1), \dots, f(m-1)\big)$ is a permutation of $(0,1,\dots,m-1)$, it suffices to show that $f: \{0, 1, \dots , m-1\} \to \{0, 1, \dots , m-1\}$ is a bijection. For $f$ to be an injection we must show

$$f(i) = f(j) \implies i=j.$$

So, let's start with the hypothesis that $f(i)=f(j)$ and use what we have.

\begin{align} (a + i \, b \bmod m) &= (a + \, j \, b \bmod m) \\ a + i \, b &\overset{m}{\equiv} a + j \, b \\ i \, b &\overset{m}{\equiv} j \, b \tag{1}\\ i &\overset{m}{\equiv} j \tag{2}\\ i &= j \tag{3}, \end{align}

where $(2)$ was concluded from $(1)$ because $b$ and $m$ are relatively prime that is $\gcd(b, m) = 1$, and $(3)$ was concluded from $(2)$ because $i, \, j \in \{0, 1, \dots, m-1 \}$. There are two ways to show that $f$ is a surjection.

A. The easy way is to note that $f$ is a map between two finite sets of the same cardinality, and since it is an injection, it also becomes a surjection.

B. The other way is to directly show that $f$ is a surjection, which requires that $$\forall k \in \{0, 1, \dots , m-1\}, \, \exists i \in \{0, 1, \dots, \,m-1\}, (a + i \, b) \bmod m = k.$$ Firstly, note that

\begin{align} a + i \, b &\overset{m}{\equiv} k \\ i \, b & \overset{m}{\equiv} k - a \\ i \, b & \overset{m}{\equiv} \bar k, \end{align}

where $\bar k := k - a$. Now, since $b$ and $m$ are relatively prime, by the Bezout's lemma there exists integers $x$ and $y$ such that $x \, b + y \, m = 1$. Consequently, we have

$$\bar k \overset{m}{\equiv} (x \, b + y \, m) \, \bar k \overset{m}{\equiv} (x \, \bar k) \, b \overset{m}{\equiv} (x \, \bar k \bmod m) \, b. $$

Finally, we set $i:= x \, (k - a) \bmod m$ for the given $k$.

Answer 2

This is not true in general, since you haven't put any restrictions on the divisibility properties of $a, b$, and $m$. For example, if $a= 3$ and $b = m$ then $f$ is not a permutation since it just maps everything to $3$.

However, it will be true if $b$ is assumed coprime to $m$. Let's see why.

First, the final step of adding $a$ and then modding by $m$ obviously gives a permutation, and so you only need to check that multiplying by $b$ gives a permutation.

Since $b$ and $m$ are coprime, there are integers $c$ and $d$ such that $cb + dm = 1$. That means that any arbitrary class $f$ modulo $m$ is the same as $(cb + dm)f = b\cdot(cf)$ mod $m$. So multiplication by $b$ is a permutation and multiplication by $c$ is the inverse of it.