# Why does double hashing create a permutation?

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)$$.

• So the actual question is not about double hashing but just something like $a + bn \mod m$?
– qwr
Aug 18 at 20:41
• @qwr: Well, the question is motivated by the double hashing concept and the requirement that we want to have a probe sequence which looks at all of the hash table slots . Aug 18 at 20:56

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.

• (I didn't read the motivation before answering the math question but now I see you added the coprime assumption, which is necessary, there.) Aug 18 at 15:29
• (+1), Thanks for your attention. You are right, I just forgot put the coprime condition in the question part. :) Aug 18 at 17:19
• For context, the result about coprime numbers is known as Bezout's Lemma, and can be generalized to rings
– qwr
Aug 18 at 20:36

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$$.

• Since it's a map between finite sets of the same cardinality it is not needed to show that it is a surjection once it's an injection.
– quid
Aug 18 at 23:00
• @quid: That's right. :) Aug 19 at 10:26