In my algo class, we discussed how uniform hashing algorithms aren't the best since it is possible to generate many keys that all hash to the same location.
Take this hashing algorithm for example: h(x,y) = (ax+by) mod p
a and b are fixed constants, and a,b,x,y are within [0,p-1]. p is a significantly large prime.
How would one go about generating pairs x,y so that each pair hashes to the same index?
It's actually pretty easy because the algebra of $\mathbb{Z}_p$ is unusually nice: it is a finite field, and lots is known about this structure.
Let $h_0$ be any congruence class mod $p$. We can create many pairs that hash to $h_0$. Take any $x'$, and solve $h(x',y)=h_0$ for $y$. This is usually doable because the algebra is nice: $$ ax'+by=h_0 \Rightarrow by = h_0-ax'. $$ As long as $b\neq 0$, we can invert it mod $p$ (and this is computationally easy) and get $$ y= b^{-1}(h_0-ax'). $$
The pair $(x', b^{-1}(h_0-ax'))$ now hashes to $h_0$. You can do this for $p$ different choices of $x'$, and you can also play the same game in the $y$-variable.
Example: $p=10067$ is a prime. Suppose we hash by $h(x,y)= 213x+400y$. Here $b=400$ and my modular calculator tells me that $b^{-1}=4958$. Let's create a pair that hashes to $h(1,1)=613$. I'll randomly take $x'=7322$ and solve for $y$ as above: $$ y=4958(613-213\cdot 7322) = 4131. $$ Hence $h(7322,4131)$ should equal $613$, and it does.
Edit: all of the above was done in $\mathbb{Z}_p$, so when I say $b\neq 0$ I really mean that $p$ does not divide $b$ as an integer.