2

Suppose that we sample a hash function $h$ at random from a collection $\mathcal{H}\subseteq [m]^U$ (we denote by $[m]$ the set $\{0,1,...,m-1\}$). The best possible thing we can require from this choice is that $\left(h(x_1),h(x_2),....,h(x_{|u|})\right)$ are jointly uniformly distributed over $[m]^U$, where $U=\{x_1,...,x_{|U|}\}$ (this in turn implies ...


Only top voted, non community-wiki answers of a minimum length are eligible