3
$\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$
3
$\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$

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.