# Finding a hash function, so that the set of hash functions is universal

Problem:

Let $$U = \{0,1,2,3,4,5\}$$ be a universe of keys and $$T = \{0,1,2\}$$ we observe follwing 5 hash functions which map from $$U$$ to $$T$$ :

$$h_1(x) = (x+1) \mod{3} \hspace{5mm} h_2(x) = (x+2) \mod{3} \hspace{5mm} h_3(x) = x \mod{2} \\ h_4(0) = h_4(5) = 2 \hspace{5mm} h_4(1) = h_4(2) = 1 \hspace{5mm} h_4(3) = h_4(4) = 0 \\ h_5(0) = h_5(1) =2 \hspace{5mm} h_5(2) = h_5(3) = 1 \hspace{5mm} h_5(4) = h_5(5) = 0$$

Find a hash function $$h_6 : U \to T$$ so that the set $$\{h_1,h_2,h_3,h_4,h_5,h_6\}$$ is a universal set of hash functions.

Questions:

So, I am new with the topic of universal hashing and hash functions. I am although knowledgeable enough to know, that a set of universal hash functions is composed of this following definition.

$$\frac{|\{h \in \mathcal{H} |h(a) = h(b)\}|}{|\mathcal{H}|} \leq \frac{1}{t}$$

when $$t = |T|$$

So right now i have the idea that i should choose my hash function so, that:

$$\frac{|\{h \in \mathcal{H} |h(a) = h(b)\}|}{6} \leq \frac{1}{3}$$

Though i do not really understand what the set above means, or how i can manipulate it so that i can essentially get a chance of $$\frac{1}{3}$$ overall. Essentially choosing that $$h_6$$ so that my above set is equal to $$2$$.

The value $$|\{h\in \mathcal{H}\mid h(a)=h(b)\}|$$ is meant to represent: for arbitrary $$a\neq b \in U$$, this value is the number of hash functions for which $$a$$ collides with $$b$$.
For example, for $$a=0,b=1$$ we have that $$h(0)=h(1)$$ only when $$h$$ is $$h_5$$ - so this here will be $$1$$.
But for $$a=0,b=3$$ we have that $$h(0)=h(3)$$ when $$h$$ is either $$h_1$$ or $$h_2$$ - thus here, the value will be $$2$$.
So your task is to find an $$h_6$$ that will not increase this value for combinations of $$a,b$$ that already have a lot of collisions.