斯坦福算法专项课程Course2 week4内容回顾

这一周的内容主要介绍了Hash表以及bloom-filters。

Course 2 Week 4

Hash Table

Hash表是一种存放键值对的数据结构,时间复杂度几乎为$O(1)$,支持的操作如下:

High-Level Idea

Hash表的原理是构造一个映射$h$,将元素映射到$h(x) \in \{0,1,2,…,n-1\}$,然后访问$A[h(x)]$,其中$A$是一个数组,$A$中每个元素可以是链表或者元素本身,这两者的区别如下:

如果$A$中每个元素是链表,那么一个格子中可以装很多元素。

hash表的运行时间为:

Resolving Collisions

如果存在$x,y$使得$h(x)=h(y)$,那么称其为冲突,这是我们不想看到的,解决方法如下:

如果$A$中元素是链表,那么可以在$A[h(x)]$尾部直接添加元素(这种方法称为Chaining);否则可以根据某个规则让$x$找到下一个空位置,例如linear probing (这种方法称为Open addressing)

The Load of a Hash Table

为了后续讨论,这里定义一个变量:

其中bucket表示hash表中格子数量,即之前提到的$n$,注意在Open addressing方式,$\alpha$必然小于等于$1$,而在Chaining方式下,$\alpha$可能大于$1$。不难发现,hash表的性能取决于$\alpha$,我们希望$\alpha$越小越好,但是注意,仅考虑$\alpha$的大小是不够的,还要考虑hash函数输出的均匀性,即不要让大量元素映射到同一个值,下面将讨论这点。

Performance Guarantees (Open Addressing)

在Open Addressing条件下,我们有如下结论:

这个不难理解,因为$\alpha$表示bucket的占用率,那么插入成功的概率为$1-\alpha$,所以插入时间服从参数为$1-\alpha$的几何分布,几何分布的期望为$\frac 1{1-\alpha}$

Performance Guarantees (Chaining)

讨论之前,要给出一个重要的定义:

Universal Hash Functions

从一个例子中来了解Universal Hash Functions:

那么我们该如何构造Universal Hash Functions呢,有如下定理:

证明该定理之前先证明一个引理:

解上述同余方程:

因为$p$是质数,$x_1 \neq x_2$,所以对于$a\in [1,p-1]$只有一解,从而

结论成立。

定理证明:

所以

由上述定理可知,因为$(x_1,y_1)$可以唯一确定$a,b$,所以满足$h_{a,b}(x_1) = h_{a,b}(x_2),(x_1\neq x_2)$的$(a, b)$数量与

数量一致,在模$p$的意义下,$y_1$有$p$种选择,在$y_2$的$p-1$个选择中,$y_1 \equiv y_2 \mod n$的概率小于等于

所以满足条件的数量小于等于

注意注意$|F|=(p-1)p$,那么

因此结论成立。

Universal Hash Functions 之所以重要,是因为我们有如下结论:

Theorem : [Carter-Wegman 1979]

下面来证明这个结论:

假设元素全体为$S$,则$\alpha=\frac{|S|}{n}$,我们假设$|S|=O(n)$,即$\alpha=O(1)$,考虑查找$x \in S$,那么时间复杂度为如下:

令$L=A[h(x)]$的链表长度,定义如下函数:

注意H为Universal Hash,那么$P[h(x)=h(y)]\le \frac 1 n $,从而

Bloom Filters

Bloom Filters的组成元素如下:

我们来计算$S$中元素被全插入后某个格子没有被置为$1$的概率。

一次插入后,该格子中没有被置为$1$概率为:

从而$|S|$次插入后该格子中没有被置为$1$概率为:

从而$|S|$次插入后该格子中被置为$1$概率为:

我们来分析上述概率,注意当$x$充分小时:

从而

如果一个元素$x\notin S$,那么判别它找到的概率约等于:

固定$b$,变化$k$,上述$\epsilon$的最小值为