What is an example of a weakly universal hash function that is not pairwise independent? 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| &gt; 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| &gt; 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 &amp; \text{if } x \neq m+1, \\
i &amp; \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.