这一周的内容主要介绍了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$的最小值为