Given a family of hash functions in table form, how can I know whether it's universal?

Question

I've been given the following two families of hash functions:

H

and

G

Each family has three functions $\{0,1,2,3,4\} \to \{0,1,2\}$ that can be seen in the tables above. For each family I need to decide whether it's universal. I know that a family of hash functions $F$ is called universal if for every $x \neq y$, $\text{Pr}(f(x) = f(y)) \le \frac{1}{m}$ ($f$ is a function in $F$). However, I don't understand how to calculate this probability. Should I calculate it for any one of the functions or for the whole family?

Answer 1

As you have stated, given a family $H$ of hash functions, the condition for universality is $\forall x,y, x \neq y: \text{P}_{h \in H}(h(x) \neq h(y)) \le \frac{1}{m}$. The probability is taken over $h \in H$, which is picked following a uniform distribution.

If you think for a while about what that means, you'll realize you need simply check whether there is at most one collision (i.e., equal entries) for any two distinct columns (i.e., every pair of $x$ and $y$) in the respective family's table. Hence, $G$ is universal, but $H$ is not; I'll let you figure out why.