universal and $k$-universal hash functions

144 Views Asked by At

In my Datastructures and Algorithms lecture, $k$-universal hash functions have been defined differently than on, e.g., Wikipedia and I have trouble finding both definitions equivalent.

My lecture: A set of hash functions $\mathcal H$ is called $c$-universal if for all $k,l \in \mathcal U, k \neq l,$ the number of hash functions $h \in \mathcal H$ with $h(k)= h(l)$ is less than (or equal) $\frac {c |\mathcal H| } m$.

In this definition, $m$ is the number of buckets (i.e, $h:\mathcal U \to \{0,\dots, m-1\}$) and $\mathcal U$ is the set of all possible keys.

1

There are 1 best solutions below

0
On

The definition given in your lecture is about the $\epsilon$-almost universal hash function family, which is a different property from the $k$-wise independent universal hash function family, given in the linked Wikipedia article.

Definition 1: A random hash function $h : U \rightarrow [m]$ is $\epsilon$-almost universal if $\Pr[h(x) = h(y)] \le \epsilon$ for all $x, y \in U$ such that $x \ne y$. It is universal if $(1/m)$-universal.

Definition 2: A random hash function $h : U \rightarrow [m]$ is $k$-wise independent if for any disjoint $x_1, \dots, x_k \in U^k$, the random variables $h(x_1), \dots, h(x_k)$ are mutually independent.

"$\epsilon$-almost universal" is often shorthanded as "$\epsilon$-universal". Confusingly, a $k$-wise independent universal hash function (that is, both $k$-wise independent and universal) is also called "$k$-universal".