## Friday, May 13, 2011

### Hash, Hash and Hash

(更新中)
Universal Hashing
A probability distribution H over hash functions from U to $\{1, \ldots, M\}$ is uni-
versal if for all x = y in U , we have
$$Pr\{h(x) == h(y)\} \leq 1/M$$

(c,k)-Universal Hashing
$\{h_i\} h_i : U \to R$, for any distinct elements $x_1,\ldots,x_k \in U$, and $y_1,\ldots,y_k \in R$, we have
$$Pr\{h_i(x_1) = y_1,\ldots, h_i(x_k) =y_k\} \leq c/|R|^k$$