哈希

哈希表¶

第一幕¶

哈希解决的是内存占用过大的问题, 试想, 一个长度为为$m$的二进制位其全域的大小为$2^m$, 而实际情况下, 根本用不到全域. 例如, 一张位深为8bit, 分辨率为3072*4080的图片, 它的全域大小是$8^{3072\times 4080}$, 而实际上这个全域里面的很多值代表的都是一张没有意义的图片.

哈希表的基本思想是"The universe is a big place, but it's mostly empty". 所以, 如果我们能够map我们的宇宙$\mathcal{X}$到一个小得多的集合$\mathcal{Y}$, 使得任何由$n$个不同元素组成的子集$S\subset \mathcal{X}$都能映射到一个仍然由$n$个不同元素组成的子集$S'\subset \mathcal{Y}$, 我们就处于有利位置. 如下图所示.

但是, 上述的思路真的可行吗? 很可惜, 是不行的. 不管我们怎么选择映射的方法, 我们总能找到一个$n$个元素的集合, 经过映射之后, 小于$n$个元素. 这就是大名鼎鼎的"鸽子洞原理":

设定任意两个集合$\mathcal{X}, \mathcal{Y}$, 且满足$m>m'$. 然后, 对于任意映射$h: \mathcal{X}\rightarrow \mathcal{Y}$, 存在一个子集$\mathcal{S}\subseteq \mathcal{X}$, 它的大小为$\lfloor \frac{m-1}{m'}\rfloor +1 \geq 2$, 该子集中的所有元素都会被映射到$\mathcal{Y}$中的同一个值.

很重要的是, 这个"bad set of elements"是依赖于映射函数$h$的, 这就告诉我们, 如果我们确定性的从大宇宙$\mathcal{X}$做一个映射(hashing)到小宇宙$\mathcal{Y}$, 存在最坏情况输入导致会被映射到小宇宙中的同一个值. 但是, 如果这个映射不是确定的呢?

第二幕¶

我们需要考虑三种选项:

假设我们要处理的数据是随机分布的.

我们可以把这些元素视作从集合$\mathcal{X}$中随机抽取, 然后选择用一个确定性的哈希函数, 依然能在平均情况下得到不错的保证. 问题在于, 这种给完全随机的假设其实并不现实, 只能算是一种heuristic, 而不是一个rigorous guarantee, 但是, 有了总比没有好.
假设哈希函数是完全随机的.

如果哈希函数完全随机, 那么对于每个$x\in \mathcal{X}$的哈希值都可以看作在$\mathcal{Y}$上相互独立, 均匀分布, 这样我们就能用各种随机变量分析方法来估算碰撞概率, 例如, 某个$\mathcal{Y}$的bucket的平均哈希元素数量, 任意bucket的最大哈希元素数量等等.

但是, 完全随机的哈希函数需要存储大量的信息, 大约需要$m\log_2 m'$位, 比用数组还占空间. 一种可能的解决方法是generate哈希函数on-the-fly. 可以尝试在第一次想要hash $x$的时候生成. 但是问题在于, 之后每次遇到它的时候也要保证给出的值不变. 要做到这点, 就得有个字典记录这个$x$之前分配过什么哈希函数, 同样的, 这是很占空间的. 和我们想要解决的问题背道而驰.
假设哈希函数并不是完全随机的

我们已经看到了上面确定性的哈希函数和完全随机的哈希函数并不能有效的解决问题. 所以, 我们退而求其次, 希望找一类规模适中(足够小能够节省存储, 但是又足够大保证碰撞概率降低)的哈希函数族$\mathcal{H}, 在初始化的时候随机地从里面选一个哈希函数$h$.
- 这个集合$\mathcal{H}$不大, 存储函数只需要$\log_2|\mathcal{H}|$位
- 只要设计得好, 随机选取这个$h$在碰撞表现上看起来就像是真的来自一个完全随机得函数, 足以在期望意义上获得较好得性能.

那么, 我们怎么选取这个哈希函数族$\mathcal{H}$呢?

等下, 这玩意是不是似曾相识? 在derandomization那里也讲过这个东西. 其实, 那里讲的是strongly universal(强泛哈希家族), 它要求对任意一对不同的元素$x\neq x'$, 在随机选择哈希函数$h$后, $h(x)$和$h(x')$在映射到目标集合$\mathcal{Y}$的时候就想两个相互独立, 均匀分布的结果. 这是一种非常强的要求, 构造起来比较复杂(家族的规模比较大).
其实, 另外还有一个家族, 叫做泛哈希加速(unviersal), 只需要对于任意一对不同的元素$x\neq x'$, 它们碰撞(即$h(x)=h(x')$的概率不超过$1/|\mathcal{Y}|$)就行. 也就是说, 不需要完全像两个独立的均匀随机变量, 只要保证碰撞的概率并不比真正的独立随机分配更糟糕就行. 这样家族的规模就可以更小, 构造也更加简单了一些.

也就是说对于每个$x, x'\in \mathcal{X}, x\neq x'$, 需要满足下列式子:

\[ \Pr_{h\sim \mathcal{H}}[h(x)=h(x')]\neq \frac{1}{|\mathcal{Y}|} \]

任何强泛哈希族都是泛哈希族, 但反之不成立.

那么, 如何来构建这个"泛哈希族"呢?

首先, 选取一个合适的素数$p$, 对于给定的整数$a, b$, 定义哈希函数:

\[h_{a,b}(x) = (ax + b \mod p) \mod m', \quad x \in \mathbb{Z}_p\]

注意, $1\leq a<p$并且$0\leq b<p$, 这个哈希家族的大小满足$|\mathcal{H}|\leq 2^{2\log_2 p}$. 证明在Lecture Notes中给出, 这里就不讨论了.

在做算法分析的时候, 我们通产先假设哈希函数是完全随机的(前面提到的第二种option), 按这种假设把所有结论推导完. 然后再回头检查整个推导过程使用的概率工具(例如期望的线性性质, 或者Chebyshev不等式等等), 看看它们是不是只需要有限/配对独立就够了, 如果确实只依赖这些有限独立级别, 那这个分析是成立的; 反之, 如果要用到Chernoff或者Hoeffding之类的需要完全独立的工具, 那么这个分析就不再成立.

第三幕¶

所以什么是哈希表呢? ... 终于, 我们到这一部分了. 一个hash table包含三个要素:

一个哈希函数 $h$ 把大集合 $X$ 映射到较小集合 $Y$ (大小约为 $m' = O(n)$);
一个数组 $A$ 的大小就是 $m'$, 用来存储或表示元素是否在哈希表中;
一种用来处理"碰撞(collisions)"的策略.

为什么仍然需要第三步(处理碰撞)? 因为无论哈希函数多么精心设计, 都不可避免会有不同元素映射到同一个数组位置(尤其生日悖论会告诉你, 当有足够多元素时, 碰撞几率大增). 所以除了尽量减少碰撞, 我们还必须有一整套机制来解决或缓解碰撞带来的问题(例如把同一位置上的元素用链表链接起来, 或者使用开放寻址等).

处理碰撞¶

幸运的是, 有很多策略来处理碰撞, 大致上可以分为两类: separate chaning和open addressing.

第一幕¶

Seperate chaining就是当若干元素哈希到相同的bucket的时候, 就在这个bucket后面挂一条链表, 把所有的碰撞到这个桶的元素都保存在这条链表里面. 插入, 查找, 删除操作就直接在对应桶的链表中进行.

负载因子, 令$\alpha = \frac{n}{m'}$,. 表示每个桶期望存放多少的元素. 空间复杂度计算: 需要存储哈希函数, 大小为$m'$的数据, 所有链表节点, 总空间大概是$O(\log m+m'+n\log m)$. 时间复杂度计算: 所有的操作都是$O(1+\alpha)$, 因为在期望里, 每个桶的链表长度大约是$\alpha$. 但是若考虑最大负载(最坏的那个桶的链表长度), 可能达到$\Omega (\log n/\log\log n)$个元素, 操作成本较高.

第二幕¶

传统哈希表只有一个哈希函数, 而open addressing这个方法会准备一系列的哈希函数$h_1, h_2, ..., h_{m'}$. 插入元素$x$的时候, 先看$h_1(x)$指向的位置是否空闲, 若已经被占用就继续看$h_2(x)$, 依次下去, 直到找到空位. 查找或者删除也同理.

一些插入/查找/删除操作的细节:

插入: 从$t=1$开始依次检查数据桶$A[h_t(x)]$, 如果碰到$A[h_t(x)]=x$, 不用管, 如果是空或者tomstone符号(⊥), 就在那里插入并停止
查找: 和插入相同
删除: 依次查找, 若碰到$A[h_t(x)]=x$, 则将其置为⊥, 表示曾经有过数据, 但是被删除. 如果删除后直接把桶变成空, 那么后续查找的时候, 一旦撞见这个空桶就会错误地认为查不到了, 但是实际可能还需要继续往后查.

问题是, 我们该怎么选取这些哈希函数呢? 我们想要它具有以下的特征: 首先, 对所有元素$x$而言, 得到的哈希函数序列$\{h_1(x), h_2(x), ..., h_{m'}(x)\}$能够在$\{0, 1, ..., m'-1\}$上形成一个随机排列(random permutation), 从而在处理碰撞和查找的时候能够覆盖所有可能桶的位置. 其次, 因为要存储和评估多重哈希函数, 如果$m'=O(n)$, 可能会带来$O(n\log m)$级别的空间开销, 我们需要避免这种情况.

第三幕¶

在讨论一些常见的选取这些哈希函数的方法前, 我们分析三种操作(插入/查找/删除)的时间复杂度, 在一些非常不可能的假设下. 假设对于每个元素$x\in \mathcal{X}$, 序列$(h_1(x), ..., h_{m'}(x))$是一个$[m']$的均匀随机排列. 那么, 对于每一个$x\in \mathcal{X}$, 查找所需的期望时间是$O(\frac{1}{1-\alpha})$. 证明见Lecture Notes.

一些常见的实现open addressing的方法:

线性探测

思路就是只是用一个哈希函数, 当发生冲突的时候, 下一个位置为$h(x)+(t-1)\mod m'$. 实现简单, 只需要一个哈希函数, 并且在计算和空间上开销较小. 缺点是比较容易出现"聚簇"的问题, 当$\alpha$接近1的时候, 插入, 查找, 删除的代价会上升到$O(1/(1-\alpha)^2)$.
二次探测

思路和线性探测类似, 但在冲突时使用二次函数的偏移量, 即$h(x) + c₁t + c₂t² \mod m'$, 其中$t$为探测次数, $c₁$和$c₂$是常数. 相比线性探测, 可以降低"聚簇"效应, 保留了开地址法只使用一个哈希表空间的好处. 虽然聚簇现象有所减少, 但如果选择$c₁$和$c₂$不当, 仍可能出现冲突分布不均的情况.
双哈希

使用两个不同的哈希函数$h$和$g$, 当发生冲突时, 计算$h(x) + (t - 1) * g(x) \mod m'$.极大减少了聚簇问题, 可以视作探测间隔更"随机", 理论上能获得更均匀的探测序列. 需要维护两个哈希函数, 实现复杂度稍高, 并且需要保证$g(x)$与$m'$的互质性等条件, 使得探测序列能遍历所有位置.
Cuckoo哈希

使用两张哈希表($A1$与$A2$), 分别对应两种不同的哈希函数($h1$与$h2$). 当插入一个元素$x$时, 只需要将它放到$A1[h1(x)]$或者$A2[h2(x)]$中即可. 如果其中某个位置为空, 那就直接插入. 如果都被占用, 则会发生所谓的 "鸠占鹊巢" 式替换 (也叫逐出): 新元素$x$会挤走原本占位的元素, 而被挤走的元素则需要去自己的另一张表对应的位置. 如果那个位置还被占, 就继续挤走下一个元素, 依此类推, 直到找到空位或者替换达到一定上限.

Lookup(x) 时, 只要分别去 A1[h1(x)] 和 A2[h2(x)] 检查是否存放了 x, 如果任何一个位置包含 x 就代表存在, 否则不存在. Remove(x) 时也是类似: 只需要检查并清空这两个可能的位置.

这样设计的好处在于: Lookup 和 Remove 的时间复杂度可以保证在 O(1), 而 Insert 平均期望也能达到 O(1), 虽然在最坏情况下可能出现多次替换循环, 但在实践中通常很快就能找到空位.

布尔过滤器¶

第一幕¶

布尔过滤器(Bloom Filter)是一种只支持插入和查询的概率型数据结构, 主要特点是能够在相对较小的空间内快速判断元素是否"可能存在"或者"一定不存在". 它由一个位数组和若干个不同的哈希函数构成:

插入: 对元素$x$依次使用$k$个哈希函数$h_1, h_2, ..., h_k$进行哈希运算, 得到$k$个索引值, 并将位数组中的这些位置全部置为$1$
查询: 同样对元素$x$计算$k$个哈希值. 如果其中任何一个对应位置为$0$, 则可以确定$x$一定不在集合中, 如果全部为$1$, 则说明$x$可能存在集合中

第二幕¶

布尔过滤器的查询可能产生False Positive的问题, 例如:

插入 1 会设置 A[1], A[5], A[10] 为 1.
插入 2 会设置 A[9], A[4], A[6] 为 1.
插入 4 会设置 A[7], A[3], A[8] 为 1.

当我们插入了 {1, 2, 4} 后, 这些对应的位都变成了 1.

接下来, 如果要查询 3, Bloom Filter 会查看 A[1], A[6], A[3] 是否全部为 1. 由于在插入其他元素时, 这些位置已经被置成 1, 所以最终查到的结果是"存在"(yes), 尽管 3 并没有真正被插入. 这就是 Bloom Filter 可能产生的假阳性 (False Positive): 报告一个不存在的元素 "存在".

在所有哈希函数都是彼此独立且像真正的随机函数一样, 可以推导出当插入了$n$个元素后, 布尔过滤器在查询的时候出现假阳性的概率大约是:

\[ \left(1 - \left(1 - \frac{1}{m'}\right)^{nk}\right)^k \;\approx\; \Bigl(1 - e^{-\frac{nk}{m'}}\Bigr)^k. \]

第三幕¶

位数组本身的大小是$m'$, 需要存储$k$个哈希函数, 假设每个哈希函数能在$O(\log m)$空间内表示并在$O(1)$时间内求值, 那么整体空间复杂度大约为$O(k\log m+m')$. 插入和查询的最坏时间复杂度均为$O(k)$, 因为每次都要计算检查$k$个哈希值.