Which one of the following hash functions on integers will distribute keys…

Answer: h(i) = i^3 mod 10

Key idea: h(i) depends only on i mod 10. The integers 0 through 2020 contain 202 full cycles of residues 0–9 plus one extra value (2020 ≡ 0), so residue 0 appears 203 times and each other residue appears 202 times.

• For h(i) = i^3 mod 10 the cube residues form a permutation: 0→0, 1→1, 2→8, 3→7, 4→4, 5→5, 6→6, 7→3, 8→2, 9→9.

• Because this mapping is bijective on residues 0–9, each bucket receives exactly the number of inputs that had the corresponding base residue: bucket 0 gets 203 keys, and every other bucket gets 202 keys.

Quick elimination of other candidates:

• Squaring (i^2 mod 10) only produces residues {0,1,4,5,6,9}, so several buckets are never used and some receive about twice as many inputs (very unbalanced).

• (11 * i^2) mod 10 is congruent to i^2 mod 10 because 11 ≡ 1 (mod 10), so it has the same poor distribution as squaring.

• (12 * i) mod 10 is congruent to 2*i mod 10 (since 12 ≡ 2). This only yields even residues {0,2,4,6,8}, leaving odd buckets empty and overloading the even buckets.

Conclusion: i^3 mod 10 distributes the 2021 keys across the 10 buckets most uniformly (one bucket has 203 keys and the other nine have 202), so it is the best choice.