4
$\begingroup$

After reading definitions of universal and k-universal (or k-independent) hash function families, I can't get the difference between them. Also, I couldn't find any examples of hash function families being universal, but not k-universal (it's written, that k-universality is stronger, so they must exist).

Could you please clarify the subject to me, or give a good piece of literature/articles to read about it?

$\endgroup$

1 Answer 1

5
$\begingroup$

The Wikipedia pages give good definitions:

https://en.wikipedia.org/wiki/Universal_hashing

https://en.wikipedia.org/wiki/K-independent_hashing

For a family that is universal but not k-universal, consider the family $H = \{h(x) \mapsto x\}$. It hashes a domain $D$ to itself. It is universal, because given $x \neq y, P(h(x) = h(y)) = 0 < 1/|D|$. However, it is not 2-universal, because $P(h(x) = x \land h(y) = y) = 1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .