Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I've seen this question in a past exam paper, and I know that the answer given is (b), but I'm not sure why.
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
(a) h(i) = i2 mod 10
(b) h(i) = i3 mod 10
(c) h(i) = (11 i2) mod 10
(d) h(i) = (12 i) mod 10
I understand the number of buckets relating to the modulus, but not how the factor or power of i affects the uniformity of the distribution.
What are the quadratic residues in $\mathbb{Z}_{10}$? What about the cubic residues? What are the orders of $[11]$ and $[12]$ in the group $(\mathbb{Z}_{10}, +)$?
A brief solution follows.
For the sake of clarity, we rename the four functions $a, b, c, d$. Let's analyze their range. Because of the closure properties of the modulo operation, we may do so in the ring $(\mathbb{Z}_{10}, +, \cdot)$. We will prove that $a, c, d$ have a range that is a strict subset of $\mathbb{Z}_{10}$, and can not therefore be uniform, while $b$ is a permutation of $\mathbb{Z}_{10}$.
Since we are working over a finite ring, we could compute each of the functions on each element of $\mathbb{Z}_{10}$ and prove our claim by exhaustion. Even though that's probably what the exercise wanted you to do, and what you should fall back on if you don't understand what follows, a true gentlemen never does that. Let's work out a more elegant way.
To begin with, we observe that $a(i) = i^2$ cannot be injective, and therefore, by piegonhole, not even surjective modulo any $m > 2$ as $[1] \neq [-1]$ but $[1]^2 = [1] = [-1]^2$. This also rules out $c$, since $[11] = [1]$ in $\mathbb{Z}_{10}$.
$d$ has to go as well; this stems from the more general fact, which I leave for you to prove, that if $\gcd(k, m) \neq 1$ then $f(i) = ki$ cannot be injective modulo $m$. (Hint: use the Bezout identity).
Now all is left is to prove that $b(i) = i^3$ is a permutation of $\mathbb{Z}_{10}$. First of all, we observe that the ring $\mathbb{Z}_{10}$ is isomorphic to the direct sum of $\mathbb{Z}_5$ and $\mathbb{Z}_2$. Since $b$ is clearly a permutation of $\mathbb{Z}_2$, if we prove that it's also a permutation of $\mathbb{Z}_5$ we are done. But $5$ is prime, so $i^3 \equiv i^{-1}$, which proves our claim.
Think of the hash function as a box with input and output values. Here, the number of possible output values is fixed to 10 (because of the mod10). Hence, uniformity depends on the input and the function. Our input is uniform in this case(whole numbers).
But the functions seem to mess up this uniformity(or variability). We'll choose the one which preserves uniformity.
Observe that the unit digit of the input solely decides the output: thanks to the mod10.
Comparing options:
A. i squared --> Unit digits 2, 3, 7, 8 lost upon squaring.
B. i cubed --> No loss
C. 11 * i squared --> Same as A. Multiplying by 11 doesn't help.
D. 12 * i --> Odd digits lost.
The answer is B, because it allows for more variety, and is therefore more uniform(for the given input range). Intuitively, a loss of variation results in the probability distribution becoming skewed, which is the reason for collisions.
PS: It is important to understand that there may exist hash function(s) that are better than these 4 options. But that's not being asked: we have to choose from the given options. Morever, as the question is from the Indian GATE exam, this is the practical approach: you only have around 2.5 minutes to solve a problem, on average.
