算法导论其五：哈希表
目录
哈希表的使用概率实在是太高太高啦，毕竟常数级的期望时间复杂度是真的诱惑。大部分语言都提供良好的哈希表数据结构。底层的原理进来了解一下呀。
基本概念
- 散列表（hash table）：哈希表的真正学名。提供根据关键字进行访问数据能力的一类数据结构。
- 散列函数：即哈希函数，用于将关键字转换为散列地址，进行数据访问。
- 关键字（key）：不同元素之间用来区分的数据字段。
- 槽（slot）：散列表中的一个存储单元，其对应的地址叫做散列地址。
- 装载因子（load factor）：一个能存放n个元素，具有m个槽位的散列表，其装载因子$\alpha = n / m$，$\alpha$可以小于、等于、大于1。
直接寻址表
如果关键字的域$\mathrm{U}=\{0,1,2….,n-1\}$比较小，则可以让每个关键字都直接对应表中的一个下标值。这种方法实际上不需要经过散列函数。
散列表
- 直接寻址法有相当明显的问题，如果域U很大，我们是不能把它全存在内存里的。而且如果数据分布并不均匀，大部分空间都将被浪费。
- 散列表做出的改进就是，利用散列函数h，将关键字域U映射到散列表的m个散列地址上，即$h:U\to \{0,1,…,m-1\}$。经过散列函数的映射，散列表实际上只需要管理m个大小的表空间。
- 新的问题：不同的关键字可能被映射到同一个槽（碰撞）。需要想办法避免。
选择更好的散列函数
- 目标：针对输入的关键字域，提供尽量满足简单一致散列（任何元素散列到任何槽中的概率均相同，且和其他元素已被散列情况独立无关）假设的映射。
- 首先：将关键字解释为自然数。多数散列函数都需要输入的关键字域为自然数集，如果输入不是，如字符串、浮点数。需要有办法先转换为自然数。
- 除法散列法：$h(k)=k mod m$。$m$的选取是一门玄学，一般可选一个质数（碰撞发生概率相对更小一些）。
- 乘法散列法：$h(k)=\lfloor m(kA mod 1) \rfloor$。关键字$k$乘一个常数$A ( 0 < A < 1 )$，并抽出小数部分。最后用$m$乘，并对结果取整。这里说的方法是在实数域上进行运算的。
- 实际上也有一些关于$m$、$A$等的推荐。例如Knuth建议选择$A$接近黄金分割比。而$m$为了方便计算，一般选择2的整数次幂（乘法就相当于位移运算了）。
- 按照以上推荐，我们可以实现一个很方便的算法。稍微改变原有的公式。
- 不乘$A$，转而计算$ks$，其中$s=A \cdot 2^{w}$，$w$为计算机的位长。
- 此时计算结果即为小数部分（高位已经溢出的部分是$mod 1$的整数部分）。其高位即为最后乘$m$后再取整的部分。
- 只需要进行一次乘法，而且由于$A$和$w$都已知，可以提前计算。因此只需要进行一次整数乘法，而不是浮点数乘法。
- 根据$m=2^{p}$，取当前结果的高$p$位。
- 不乘$A$，转而计算$ks$，其中$s=A \cdot 2^{w}$，$w$为计算机的位长。
- 全域散列法：
- 前面讲到的散列方法，都有一个共性问题，就是一定能找到一系列会被散列到同一个槽中的关键字。这是由散列函数的性质决定的。
- 全域散列实用随机选择的散列函数，使得散列函数独立于要存储的关键字。保证不会出现性能退化。
- 全域定义：设$\mathcal{H}$为有限的一组全域函数组，则满足对任意一对不同的关键字$k,l$，满足映射后$h(k)=h(l)$的散列函数$h\in\mathcal{H}$的数量至多为$|\mathcal{H}|/m$。即任意选择的散列函数，使碰撞几率低于$1/m$。这样的函数族称为全域的。
- 基于这个定义要求，使用全域散列和链表法，可以证明具有良好的期望性能。
- 一种设计一个全域散列函数类的方法：
- 选择一个足够大的质数$p$，使每一个关键字$k\in [0,p-1]$。
- 设$\mathbf{Z}_p=\{0,1,…,p-1\}$，$\mathbf{Z}_p^*=\{1,2,…,p-1\}$。
- 函数族为$\mathcal{H}_{p,m}=\{h_{a,b}=((ak+b)mod p)mod m):a\in \mathbf{Z}_p , b\in \mathbf{Z}_p^* \}$
散列后解决碰撞
- 链接法：每一个槽内保存一个链表，再存储具体数据元素。
- 有围绕装载因子的严格证明，在简单一致散列前提，和在槽数和元素数成正比的情况下，能保证操作时间满足平均$\mathrm{O}(1)$。
- 因为只需要成正比关系，因此装载因子$\alpha$允许超过1。
- 开放散列法：插入时用一个散列函数序列，依次探查散列表，直到找到一个空槽。
- 好理解的来说就是：一次hash找不到空位置，再重新hash一次，重复直到能找到位置。
- 链接法的问题在于，每一个记录多了一个和自己无关的链接地址，在有些情况下，这浪费的空间实在是没有必要。
- 现在我们的散列函数，还需要包含一项代表当前探查号的参数，即$h:U\times\{0,1,…,m-1\} \to \{0,1,…,m-1\}$，其中$m$还是槽的数量。
- 可用的探查方式($\acute{h}$代表原散列函数)
- 线性探查：$h(k,i)=(\acute{h}(k)+i) mod m$，即从第一次探查的槽位置，逐个向后查找空槽。很容易因为群集现象（连续占用的槽越来越多）导致性能降低。
- 二次探查：$h(k,i)=(\acute{h}(k)+c_{1}i+c_{2}i^{2}) mod m$，即带有两个常数，以平方形式向后探查。但仍然具有**二次群集**（第一次探查结果相同的键，二次探查序列仍然相同）。而且其中$c_{1}$$c_{2}$必须仔细设置才能让整个序列都有机会探查到。
- 双重散列：$h(k,i)=(h_{1}(k)+ih_{2}(k)) mod m$，其中$h_{1}$$h_{2}$是两个散列函数，需要满足和$m$的一定关系，来保证能够探查到整个序列。
- 依然有围绕装载因子的证明，可以得出结论，装载因子为$\alpha < 1$的开放散列表中，成功探查时的期望探查次数至多为$\frac{1}{a}ln\frac{1}{1-\alpha}$。
- 新问题：插入和查找依然很方便，但是删除操作简直要命。一般来说需要在槽上给出一个删除标记，但是这样做之后，查找时间就无法保证。因此如果需要删除操作，开放散列法并不是很好的选择。
- 完全散列法：
- 定义：如果一种散列技术在进行查找时拥有最坏$O(1)$的复杂度的话，则称其为完全散列。
- 使用场景：关键字集合是静态的，已经确定，不再改变。
- 思路：用一个两级散列的结构。第一级用一个全域散列$h\in\mathcal{H_{p,m}}$将关键字映射到某个槽$m_j$内，在该槽再内进行第二级散列$h_j \in \mathcal{H_{p,m_j}}$，将数据最终映射到存储地址。完全散列的神奇之处在于，能确保第二级散列不出现碰撞。
- 关键要点：
-
时间复杂度$O(1)$的证明：第二级散列表要求，槽数量是关键字数量的平方，即第二级的任何一个散列表有$m=n^2$。这能保证随机选择的第二级散列表碰撞次数的期望小于$1/2$，经过几次尝试，则一定能找到无碰撞的情况（实际上根据马尔可夫不等式可知有半数的函数能满足这一点）。
-
空间复杂度$O(n)$的证明：设第一级槽数和关键字数量相等$m=n$，第二级满足平方要求$m_j=n_j^2$。这里的证明还是很漂亮的所以我保留了下来（也可以去回想一下桶排序，那里也是类似的平方和最后仍然满足线性）
$E(\sum_{j=0}^{m-1} n_j^2 )= E(\sum_{j=0}^{m-1}(n_j + n_j(n_j-1)))$
$= E(\sum_{j=0}^{m-1}(n_j) + E(\sum_{j=0}^{m-1}(n_j(n_j-1)))$
$= n + 2E(\sum_{j=0}^{m-1}(n_j(n_j-1)/2))$
注意到和式$\sum_{j=0}^{m-1}(n_j(n_j-1)/2)$就是总的碰撞数，根据全域散列性质可知。
$E(\sum_{j=0}^{m-1}(n_j(n_j-1)/2))\le \frac{n(n-1)}{2m} = \frac{n-1}{2}$
综上，$E(\sum_{j=0}^{m-1} n_j^2 ) \le n + 2\frac{n-1}{2} < 2n$
-
一点点思考
散列表虽然引入了各式各样的方法，其实本质上都是希望用空间换一些时间。我们并不希望一个散列表具有99.99%之类的装填率，因为那样会显著降低散列表的性能。实际上当你使用散列表的时候，你多多少少都会浪费一些空间的。
散列表处的分析方法非常多样，引入了数论、概率等多种领域的内容。如果对理论感兴趣可以阅读原书，证明部分都是比较好懂的。
数据结构还是算法
虽然看起来散列表是一种数据结构，但是其实取散列的思想是一种非常常见的算法套路。比如当我们需要判断两个元素的内容是否完全相同时，就可以先判断其散列值是否相同，相同再在内容中逐字段深度比较，散列值不同则一定不相同。以此来加快速度。