Universal hash functions - Proof

Question

Problem statement

Let $K$ be a set of keys with $|K| = n$ and define the index set $I = \{0, \ldots, m-1\}$. Now let $H = \{h \mid h : K \to I\}$, i.e. $H$ contains all hash functions which map the keys from $K$ to the set $\{0, \ldots, m-1\}$.

Prove or disprove that $H$ is universal.

Attempt

Reiterating the definition

A family of hash functions $H$ is universal if and only if for $\forall x, y \in K, (x \neq y)$ we have $\left|\{h \in H : h(x) = h(y)\}\right| = \frac{|H|}{m}$

I know you can construct specific families of universal hash functions and there are families which aren't universal. But if you consider all of them how would you know which part would outweigh which to decide if this statement still holds?

I'm probably going the wrong way so I would appreciate any help or hints!

Answer 1

Let us first look at the total number of hash functions in $H$. Since each key can be mapped to $m$ different indexes and there $n$ different keys. We get:

\begin{align} |H| = m^{n} \end{align}

Now, without loss of generality, let us consider the first two keys $x = k_{1}$ and $y = k_{2}$. We will compute the number of hash functions where $x$ and $y$ will collide i.e., $h(x) = h(y) = i$ for any $i \in \{0,\dotsc,m-1\}$.

\begin{align} |\{h \in H : h(x) = h(y) = i\}| = m^{n-2} \end{align}

Therefore, summing up for all $i \in \{0,\dotsc,m-1\}$, we get: $$|\{h \in H : h(x) = h(y)\}| = m^{n-1} = \frac{|H|}{m}$$

Hence, $H$ is a universal hash family.