A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :

$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$

Here the function $h:U \rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.

A family of hash functions $H_s$ is said to be strongly universal if for all $x \ne y$ and $k, \ell \in [m]$:

$$P_{h \in H_s}(h(x) = k \land h(y) = \ell) = 1/m^2$$

What is a concrete example of a hash function family which is weakly universal but not strongly universal?


Let $U = [m]$, and let $h$ be the identity function.

If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$ h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \text{if } x = m+1. \end{cases} $$ The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.

  • $\begingroup$ Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that. $\endgroup$ – Anush Feb 14 '19 at 17:07
  • 2
    $\begingroup$ Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question. $\endgroup$ – Yuval Filmus Feb 14 '19 at 17:12
  • $\begingroup$ No I don’t think so. Thank you for your very nice answer to the first version. $\endgroup$ – Anush Feb 14 '19 at 17:13
  • 1
    $\begingroup$ Well, it makes a nice exercise. $\endgroup$ – Yuval Filmus Feb 14 '19 at 17:24
  • 1
    $\begingroup$ I don’t see any lookup tables in your question. Perhaps you need to spend more time formulating your question. When you have a concrete follow-up question, you can ask it separately. $\endgroup$ – Yuval Filmus Feb 14 '19 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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