1
$\begingroup$

The following question appears in Introduction to Algorithms (CLRS):

Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h_1(k) + ih_2(k)) \bmod{m} $. Show that the probe sequence $\langle h(k, 0), h(k, 1), \dots , h(k, m - 1) \rangle$ is a permutation of the slot sequence $(0, 1, \dots , m-1)$ if and only if $h_2(k) $ is relatively prime to $m$. (Hint: See Greatest Common Divisor (GCD)).

Double hash function uses two hash functions, given that $h(k, i) = (h_i(k) + ih_2(k)) \bmod{m} $, such that integer $i$ is $i=0, \dots, m-1$ when we probe in case of collision, so we start first with $i=0$, if there is a collision, then $i=1$ and so on until we find an empty slot. The key $k$ is an integer.

Attempt: Relatively prime and co-prime is same thing. So if $h_2(k) $ is relatively prime to $m$, then $\gcd(h_2(k), m) = 1$. So, if $h_2(k)$ and $h_2(k)$ and $m$ are always co-prime to each other, we can see we always get a number between $h_2(k) \bmod{m}$ that is in slots $(0, \dots, m-1)$. If $h_2(k)$ is not relatively prime to $m$, then for the probe sequence $\langle h(k, 0), h(k, 1), \dots , h(k, m - 1)\rangle$, we might get two elements in the probe sequence that are identical to each other. This is how I approached it, so I am not sure how that will prove that $\langle h(k, 0), h(k, 1), \cdots , h(k, m - 1) \rangle$ is a permutation of $(0, 1, \dots , m-1)$ anyway.

$\endgroup$
6
  • 1
    $\begingroup$ let's consider only h2(k) * i part, and have a = h2(k). i is 0 ... m-1. a * i is m different values, we want to prove that a * i takes each of these values exactly once. Let's assume that it is not the case. Then there are i_1 and i_2 such that a * i_1 = a * i_2 = b mod m, b is arbitrary value. But we know that if gcd(a, m) = 1 then linear congruence can have only one solution. So a * i takes m different values -> thus all values between 0 and m - 1. If i understand correctly adding h1 will just rotate these values. $\endgroup$
    – Effie
    Sep 8 at 0:15
  • 1
    $\begingroup$ see here about linear congruence: math.niu.edu/~richard/Math420/lin_cong.pdf $\endgroup$
    – Effie
    Sep 8 at 0:16
  • $\begingroup$ @effenok. Thank you very much. $\endgroup$
    – Avra
    Sep 8 at 0:21
  • 1
    $\begingroup$ does it work? then i will post it as answer. $\endgroup$
    – Effie
    Sep 8 at 0:21
  • 2
    $\begingroup$ i think stackoverflow generally prefers having accepted answers to questions. but if @robjohn has a better answer, he should post it. $\endgroup$
    – Effie
    Sep 8 at 0:26
1
$\begingroup$

Let's write your question more succinctly:

Let $m \geq 1$ and $a,b$ be integers. The set $S = \{ a+ib \bmod{m} : 0 \leq i \leq m-1 \}$ consists of the integers $0,\ldots,m-1$ iff $b$ is relatively prime to $m$.

Note that $S$ consists of the integers $0,\ldots,m-1$ iff the values $a+ib \bmod{m}$ are all distinct.

Suppose first that $b$ is not relatively prime to $m$. This means that we can find $c > 1$ that divides both $b$ and $m$. It follows that $a \bmod{m} = a + (m/c)b \bmod{m}$, since $(m/c)b$ is a multiple of $m$. Since $1 \leq m/c \leq m-1$, this shows that $S$ contains fewer than $m$ distinct values.

Now suppose that $b$ is relatively prime to $m$. Assume, by way of contradiction, that not all values in $S$ are distinct, say $a+ib \bmod{m} = a+jb \bmod{m}$ for some $i < j$. Then $(j-i)b \bmod{m} = 0$, where $1 \leq j-i \leq m-1$. This means that $(j-i)b$ is a multiple of $m$. Since $b$ is relatively prime to $m$, this implies that $j-i$ is a multiple of $m$, which is impossible since $1 \leq j-i \leq m-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.