GATE CS 2015 Set 2 Q33 — Graphs

Since the hash functions compute values modulo $10$, the hash value $h(i)$ depends only on the last digit of $i$ (i.e., $i \pmod{10}$). For $i$ ranging from $0$ to $2020$, the last digits $d \in \{0, 1, 2, \dots, 9\}$ appear almost equally often. Thus, the most uniform distribution is achieved by the function that maps these $10$ digits to the $10$ buckets as uniquely as possible.

Let's evaluate the outputs for each option for $d \in \{0, 1, \dots, 9\}$:

• Option A: $h(i) = i^2 \pmod{10}$
  The outputs are $\{0, 1, 4, 9, 6, 5, 6, 9, 4, 1\}$. Only buckets $\{0, 1, 4, 5, 6, 9\}$ are used, leaving others empty.
• Option B: $h(i) = i^3 \pmod{10}$
  The outputs for $d = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ are:
  $0^3 \equiv 0$, $1^3 \equiv 1$, $2^3 \equiv 8$, $3^3 \equiv 7$, $4^3 \equiv 4$, $5^3 \equiv 5$, $6^3 \equiv 6$, $7^3 \equiv 3$, $8^3 \equiv 2$, $9^3 \equiv 9 \pmod{10}$.
  This produces a perfect permutation of $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Every bucket receives an equal number of keys, resulting in a perfectly uniform distribution.
• Option C: $h(i) = (11 \ast i^2) \pmod{10} \equiv i^2 \pmod{10}$. Same as Option A.
• Option D: $h(i) = (12 \ast i^2) \pmod{10} \equiv 2i^2 \pmod{10}$.
  The outputs are restricted to $\{0, 2, 8\}$, which is highly non-uniform.

Therefore, Option B distributes the keys most uniformly.