0
$\begingroup$

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$.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much ! This really helped me in understanding the problem. I even solved it today ! $\endgroup$
    – Mark Lauer
    Dec 10, 2021 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.