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

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?

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.