哈希学习笔记(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\)。
- 标题: 哈希学习笔记(NJU)
- 作者: 夏佑 | XiaU
- 创建于 : 2023-09-26 00:00:00
- 更新于 : 2023-09-26 20:08:23
- 链接: https://summace.cc/Hashing-Sketching/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。