Counting number of keys hashed to each slots

Question

Suppose $K= \{ k^2:1\leq k\leq 100 \} $ as the set of keys that hashed by two hash functions $$ a)\;\; h(k)=k\mod 12 $$ $$b)\;\; h(k)=k\mod 11 $$ I want to show that $a$ is not a good choice because it hash even numbers to slots with even index. But I try to find out how many elements hashed to each index for $a$ and $b$ to show that $a$ increases our cost for a search operation. I find out in $a$, if $k=12t$ like $12,24,36,\dots$ hashed to index $0$ but is there a simple way to speed up my computations?

Answer 1

For b), $h(x)=0$ iff $x$ is a multiple of $11$, so for approximately $\frac1{11}$ of the keys. The rest splits approximately evenly among the five remainders 1, 4, 9, 5, 3 (whereas 2, 6, 7, 8, 10 are never congruent to squares), so $\approx \frac2{11}$ of the keys per class.

---

For a), we have a bit more work because 12 is not prime. But we can factor it as $4\cdot 3$ and investigate the parts separately (at least approximately) per the Chinese Remainder Theorem. Modulo $4$, a square is either $0$ for even or $1$ for odd numbers. Modulo $3$, a square is either $0$ (for the multiples of $3$) or $1$ (for all others). By combining these results, we see that approximately $\frac12\cdot \frac13=\frac16$ each are $0$ or $9$ modulo $12$, approximately $\frac12\cdot \frac23=\frac13$ each are $1$ or $4$ modulo $12$.

If you are unhappy with the word "approximately" occurring so often, note that the remainder of $x^2\bmod 12$ depends only on $x\bmod 6$, so the mentioned proportions hold exactly for every group of six consecutive keys. So if we had $K=\{\,k^2\mid 5\le k\le 100\,\}$, we'd have exactly 16 times 0, 16 times 9, 32 times 1, and 32 times 4. The additional keys $1$, $4$, $9$, $16$ modify the stats to: 16 times 0, 17 times 9, 33 times 1, and 34 times 4.