MIT《算法导论》课程第7课《哈希表》学习笔记.
哈希表
用于解决Symbol-table问题
设表S有n条记录，每条记录为x，包含键key和值value。
在哈希表上的操作
Insert(S, x)用于在哈希表S中插入一条记录x，Delete(S, x)用于在S中删除一条记录x，Search(S, k)在S中搜索以k为键值的记录，如果找到的返回该记录，如果没有找到则返回空。
直接映射法
假设key来自一个含有m个元素的集合$U={0, 1, 2, \dots,m-1}$，设这些键值相互独立。
建立一个从0到m-1的数组$T[0\cdots m-1]$来表示S。
$$
T[k]=
\begin{cases}
x,&\mathtt{if}&x\in S & \mathtt{and} & \mathtt{key}[x]=k \
\mathtt{nil},&其他
\end{cases}
$$
时间复杂度$O(1)$
哈希法
运用一个哈希函数$H$来“随机地”将键(key)映射到槽(slot)。当一个键被映射到一个已经存在记录的槽时，碰撞(collision)就发生了。
链接法
把映射到同一槽的键值保存在链表中。
分析
最坏情况：S中所有键映射到同一个槽，此时的时间复杂度$\Theta(n)$，其中$n=|S|$。
平均情况：假设S中的每一个键有同样的概率被映射到任意一个槽中。定义一个存放n个键、映射到m个槽的哈希表，其装载因子$\alpha=\frac{n}{m}$（平均每个槽里键的数量）。
预期的失败搜索次数$=\Theta(1+\alpha)$
当$\alpha = \Theta(1)$，即$n=O(m)$时，预期的搜索次数为$\Theta(1)$。
选择一个哈希函数
我们期望选择这样的哈希函数，它能够把键(key)均匀地映射到槽(slot)里，而键本身的一些分布的特性不会影响它在哈希表中的均匀性。
除法哈希法(Division method)
$$
h(k) = k \pmod m，其中m是槽的数量
$$
注意不要选择太小的$m$值作为除数。如当除数=2，key都为偶数时，永远用不到奇数槽。
当$m=2^r$时，哈希表取决于k的二进制的某些位，而同类数据的二进制形式常常存在某种规律性（“随机性”不好），这样的哈希函数就不好。
好的方法是选取指数作为除数，不要太接近2的幂或10的幂。
乘法哈希法 Multiplication method
设槽的数量$m=2^r$，计算机的字长为$w$。选取如下的哈希函数：
$$
h(k)=(A \cdot k \pmod {2^w}) \mathtt{rsh}(w-r)
$$
其中A是一个奇数，且$2^{w-r} \lt A \lt 2^w$，“rsh”表示二进制右移运算。A的取值不能太接近$2^{w-r}$或$2^w$。
对于计算机来说，先乘以$A$再对$2^w$取余比直接取余快。
如，取$m=8=2^3，w=7，A=(1011001)_2$。
$$
A \cdot k = (10010100110011)_2
$$
对$2^w$取模，即取二进制的后$w$位，得到
$$
(0110011)_2
$$
右移$w-r=7-3=4$位，得到
$$
(011)_2
$$
于是$h(k)=(011)_2$
开放寻址法 Open addressing
在这种方法里，没有链表。这种方法要求系统地探查哈希表，直到找到一个空的槽为止。
探查方法
线性探查：
$$
h(k,i)=(h(k,0)+i) \pmod m
$$
这种方法会遇到“一次集群”的问题，即一段区域内的槽都被占满。
二次哈希：
$$
h(k,i)=[h_1(k)+i\cdot h_2(k)] \pmod m
$$
通常选择$m=w^r$，且$h_2(k)$总为奇数。
开放探查的分析
假设“均匀哈希”，即所有键都均等地有$m!$种探查序列，且每个键都相互独立。
如果$\alpha \lt 1$（即$n \lt m$），则预期的探查次数$\le \frac{1}{1-\alpha}$。
证明：
假设一个失败的探查案例，一次的探查是必须的，发生碰撞的概率是$\frac{n}{m}$。第二次探查是必须的，发生碰撞的概率是$\frac{n-1}{m-1}$。第三次的探查是必须的，发生碰撞的概率是$\frac{n-2}{m-2}$。
注意到$\frac{n-i}{m-i} \lt \frac{n}{m} = \alpha$, for $i$ = $1,2,\dots,n-1$。
那么，预期的探查次数为：
$$
\begin{align}
& 1+\frac{n}{m}(1+\frac{n-1}{m-1}(1+\frac{n-2}{m-2}(\dots (1+\frac{1}{m-n})\dots))) \
\le & 1+\alpha(1+\alpha(1+\alpha(\dots(1+\alpha)\dots))) \
\le & 1+\alpha + \alpha^2 + \alpha^3 + \dots \
= & \sum \limits_{i=0} \limits^{\infty} \alpha^i \
= & \frac{1}{1-\alpha}
\end{align}
$$
证毕。
$\alpha \lt 1$为常数，平均需要$\Theta(1)$次探查。
$\alpha=0.5$，表示哈希表有50%为空，平均需要2次探查。
$\alpha = 0.1$，平均需要10次探查。
如果$\alpha = 1$，哈希表的利用率为100%，理论上的平均探查次数为$\infty$。