0
$\begingroup$

I encountered the notion of 4-universal hash function and I cannot understand what exactly it means. This article https://en.wikipedia.org/wiki/Universal_hashing did not really help to clarify it.

Thanks!

$\endgroup$
1
  • 1
    $\begingroup$ what did you not understand ? the concept of universal hash function or the construction of an example of it ? $\endgroup$
    – reuns
    Commented Jan 14, 2016 at 3:38

2 Answers 2

0
$\begingroup$

Unfortunately, the jargon around this is not consistent. 4-universal hashing is 4-independent hashing.

Note that there is no such thing as a 4-universal hash function - k-independence and k-universality are a function of families of hash functions.

$\endgroup$
0
$\begingroup$

Actually, there is a pretty standard definition of a k-universal hashing, as stating here.

What is says is that if you pick any K elements in the first set, choosing uniformly a hash function from the reference K-universal family will imply a uniform distribution over all combinations of K elements in the second set.

From an informational-bayesian perspective, this means that observing any k-1 hash results won't give you any information about the k'th value: $P(h(x_k) | h(x_{k-1})...h(x_1)) = P(h(x_k))$.

$\endgroup$

You must log in to answer this question.

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