Note on Advanced Algorithm II: Hashing and Sketching

生日悖论 Birthday Paradox

---

$n$ 个球投入到 $m$ 个格子中，每个格子都得到少于等于1个球的概率 $\Pr(\mathscr C)=\prod\limits_{i=0}^{n-1}\left(1-\dfrac im\right)\approx e^{-\frac{i}{m}}\approx e^{-n^2/2m}$

当 $n=\sqrt{2m\ln\dfrac1p}$ 时，$\Pr(\mathscr C)=(1\pm o(1))p$

集合查询问题

---

问题描述

对于一个包含 $n$ 个元素 $x_1,x_2,\dots,x_n\in U=[n]$ 的集合 $S$，查询 $x$ 是否在集合中

Perfect Hashing

完美哈希即不发生冲突，哈希函数 $h$ 是从 $[N]\to[M]$ 的所有映射中随机选取的.

$\Pr(\text{perfect})\approx e^{-n^2/2m}>1/2$，当 $m=n^2$.

Universal Hashing

照搬一下原话

A family $\mathscr H$ of hash functions in $U\to [m]$ is $k$-universal if for any distinct $x_1,\dots,x_k\in U$,

$\Pr\limits_{h\in\mathscr H}[h(x_1)=\cdots=h(x_k)]\le\frac1{m^{k-1}}$

$\mathscr H$ is strongly $k$-universal($k$-wise independent) if for any distinct $x_1,\dots,x_k\in U$ and any $y_1,\dots,y_k\in[m]$

$\Pr\limits_{h\in\mathscr H}\left[\bigwedge\limits_{i=1}^k h(x_i)=y_i\right]=\frac1{m^k}$

生日悖论在两两独立时是 2-universal hashing.

$Y=\sum\limits_{i<j}I[X_i=X_j]$, $\mathbb E[Y]\le\dbinom n r\dfrac1m$

FKS Perfect Hashing

先通过 primary hashing 到 $n$ 个 bucket 中，每个 bucket 再使用 secondary hashing 到对应的位置

对于 $n$ balls into $m$ bins 问题，分析冲突的个数 $Y=\sum\limits_{i>j}I[X_i=X_j]$. 考虑 2-universal 的情况

$\mathbb E[Y]=\sum\limits_{i<j}\Pr[X_i=X_j]\le\dbinom n 2\frac1m$

而 $Y=\sum\limits_{i=1}^{n}\dbinom {|B_i|}{2}=\dfrac12\sum\limits_{i=1}^n|B_i|(|B_i|-1)$

于是有

$\mathbb E\left[\sum\limits_{i=1}^n|B_i|^2\right]=\dfrac{n(n-1)}m+n=O(n)$

Approximate set

使用 hash 的方法记录集合中的元素

Bloom Filters

使用多个 hash function hash 到多个位置

当 $s\notin S$ 时，

$\begin{aligned} &\Pr\left[\forall1\le j\le k:A[h_j(x)]=1\right]\\ =&\left(\frac{\#\{\text{not empty}\}}{m}\right)^k=\left(\frac{\sum I[A[j]=1]}{m}\right)^k\\ =&\left(\Pr[A[j]=1]\right)^k,\ \ \text{w.h.p}\\ =&(1-(1-1/m)^{kn})^k\approx(1-e^{-kn/m})^k \end{aligned}$

元素个数计数

---

问题描述

给定一串数的序列，估计单独的元素个数 $z=|\{x_1.x_2,\dots,x_n\}|$

使用一个均匀分布的哈希函数 $h:U\to[0,1]$. 相当于将 $[0,1]$ 分成 $z+1$ 个区间

$\mathbb E\left[\min\limits_{1\le i\le n}h(x_i)\right]=\dfrac1{z+1}$

所以有估计 $\hat Z=\dfrac{1}{\min_i h(x_i)}-1$. 令 $Y=\min_ih(x_i)$，则有

$\Pr[Y>y]=(1-y)^z\ \ \ \ \ \ \ p(y)=z(1-y)^{z-1}\\ \mathbb E[Y^2]=\int_0^1y^2z(1-y)^{z-1}\mathrm d y=\frac2{(z+1)(z+2)}\\ \text{Var}[Y]=\mathbb E[Y^2]-\mathbb E[Y]^2=\frac{z}{(z+1)^2(z+2)}\le\frac1{(z+1)^2}$

使用多个 hash function 降低方差

此外还有两种估计的方法：Flajolet-Martin Algorithm, BJKST Algorithm

元素频率估计

---

问题描述

依然是给定一串数，估计某个数出现的频率 $f_x=|{i:x_i=x}|$

跟前面的思路一样，利用多个 hash function 得到的值来进行存储