哈希学习笔记（NJU）

南京大学研究生课程 Advanced Algorithm。

Birthday Paradox

在一个 \(m>57\) 人的班里，有两个人生日相同的概率 \(>99\%\)。

形式化地说：\(n\) 个球放进 \(m\) 个箱子。定义事件 \(\mathscr{E}\)：每个箱子有 \(\leq 1\) 个球。

\[ \Pr[\mathscr{E}]=\prod\limits_{i=0}^{n-1}\left(1-\dfrac{i}{m}\right)\approx e^{-n^2/2m} \]

\[ \text{when}\ n=\sqrt{2m\ln\dfrac{1}{p}}\Rightarrow\Pr[\mathscr{E}]=(1\pm o(1))p \]

Hashing

Simple Uniform Hash Assumption

完美哈希。使用随机哈希函数。简称 SUHA。

\(m=n^2\) 的空间，可以做到冲突概率 \(<\dfrac{1}{2}\) （生日悖论）的概率完美哈希。

k-Universal Hash Family

称哈希函数 \(U\rightarrow [m]\) 的 family \(\mathscr{H}\) 是 k-universal 的，当对于一些不同的 \(x_1\cdots x_k\in U\)，满足：

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

Linear Congruential Hashing

线性同余哈希：\(h_{a,b}(x)=((ax+b)\bmod p)\bmod m\)

Back to Birthday Paradox

用 2-universal hashing 解释。

总 collision pairs：

\[ Y=\sum\limits_{i<j}I[X_i=X_j] \]

其线性期望

\[ \mathbb{E}[Y]=\sum\limits_{i<j}\Pr[X_i=X_j]\leq {n\choose 2}\dfrac{1}{m} \]

Markov's Inequality：

\[\Pr[X\geq t]\leq \dfrac{\mathbb{E}[X]}{t}\]

\[ \Pr[\lnot \mathscr{E}]=\Pr[Y\geq 1]\leq \mathbb{E}[Y]\leq \mathbb{E}\ (\text{when}\ n\leq\sqrt{2m\epsilon}) \]

因此可以将 SUHA 换为线性同余函数。

不完美哈希概率 \(\leq \dfrac{n(n-1)}{2m}<1\)。因此一定可以找一个哈希方式 \(h\in \mathscr{H}\) 使得其成为完美哈希，且 \(\mathscr{H}\) 很小。

但是空间仍为平方级别。

FKS Prefect Hashing

用一个 primary hashing 随机哈希将 \(N\) 个元素分为 \(n\) 个 buckets，每个 bucket 开一个平方空间的完美哈希表。

时间复杂度是显然的 \(O(1)\)，空间呢？

\(n\) 个球放进 \(n\) 个 buckets，其平方和为线性的。为什么？因为 collision pairs 的期望是线性的。因此期望空间花费为 \(O(n)\)。

形式化地说：

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

总空间 \(O(n\log N)\) bits。

Bloom Filters

布隆过滤器。用于近似查询。

\(k\) 个随机独立哈希函数 \(h_1\sim h_k:U\rightarrow [m]\)。

共用一个 bit 串，每次插入映射 \(k\) 个位置。

查询时候查询 \(k\) 个映射，如果有 \(0\)，则一定不在集合中。否则有概率误判。

显然，\(x\in S\) 总正确。

错误概率：

\[ \begin{align} \Pr[\forall 1\leq j\leq k:v[h_j(x)]=1]&\leq (1-(1-1/m)^{kn})^k\\ &\approx(1-e^{-kn/m})^k\\ &=2^{-c\ln 2}\leq (0.6185)^c \end{align} \]

选取 \(k=c\ln 2\)。空间 \(m=cn\) bits，时间 \(k=c\ln 2\)。