11.1 直接寻址表
什么是直接寻址表？
就是用一个数组，数组的每个位置都保存一个元素。每个数组的位置称作“槽(slot)”。下图描绘了一个直接寻址表，槽 k 指向集合中的一个“关键字”为 k 的元素。如果该集合中没有关键字为 k 的元素，则 T[k] = NIL。

特点：
最大复杂度：O(1)
最小复杂度 ：O(1)
排序空间使用：- （无排序）
使用条件：全域 U 不能很大
使用场景：todo
是否稳定：是

11.2 散列表
直接寻址技术的缺点是非常明显的：如果全域 U 很大，则在一台标准的计算机可用内存容量中，存储一大小为 U 的一张表可能不太实际。还有，有时候实际存储的关键字集合 K 相对 U 来说可能很小，很多空间都浪费掉了。

在散列方式下，该元素存放在槽 h(k) 中，即利用“散列函数(hash function) h ”，由关键字 k 计算出槽的位置。函数 h 将关键字的全域 U 映射到散列表（hash table）T[0…m-1]的位置上。h(k) 的值，称作关键字 k 的“散列值”。

这种方式存在一个问题：两个关键字可能映射到同一个槽中。我们称这种情形为“冲突（Collision）”。我们可以找到有效的办法来解决这个问题：链接法（chaining）和开放导址法（open addressing）。

链接法（chaining）：
在链接法中，把在同一个槽中的元素，放在一个链表中存储。
下面的例子中，链表是一个双向链表，这样“插入”和“删除”操作，可以在 O(1) 时间内完成。
如果散列表中“槽数”至少与“表中的元素数”成正比的话，则全部的字典操作平均情况下都可以在 O(1) 时间内完成。

特点：
最大复杂度：O(n)
最小复杂度 ：O(1)
排序空间使用：-（不排序）
使用条件：todo
使用场景：todo
是否稳定：否
其它：散列表中“槽数”至少与“表中的元素数”成正比的话，则全部的字典操作平均情况下都可以在 O(1) 时间内。

散列函数
好的散列函数的特点
每个关键字都被“等可能地”散列到 m 个槽位中，并且与其它关键字散列到哪个槽位无关。

一种好的方法导出的散列值，在某种程度上应独立于数据可能存在的任何模式。例如，“除法散列”用一个特定的素数来除所给的关键字，所得的余数即为该关键字的散列值。假定所选择的素数与关键字分布中的任何模式都是无关的，这种方法常常可以给出好的结果。

将关键字转换为自然数
如果所给的关键字不是自然数，就需要找到一种方法来将他们转换成为自然数。例如： pt 对应的十进制数为（112, 116），然后以 128 为基数来表示，则为 112 * 128 + 116 = 14452。在特定的场合，通常还能设计出其他类似的方法，将每个关键字转换为一个（可能是很大的）自然数。

11.3.1 除法散列法
什么是除法散列法？
通过取 k 除以 m 的余数，将关键字 k 映射到 m 个槽中的某一个上，即散列函数为：h(k) = k mod m。由于只需作一次除法操作，所以除法散列法还是非常快的。
例如，如果散列表的大小为 m=12，所给的关键字为 k=100，则 h(k)=4，把 k 放到第4个槽位上。

下面的内容请注意：
当使用除法散列时，要避免选择 m 的某些值，例如，m 不应该为 2 的幂，如果 m=2p，而 h(k) 就是 k 的 p 个最低位数字。除非已知各种最低 p 位的排列形式为等可能的，否则在设计散列函数时，最好考虑关键字的所有位。（原文一部分：When using the division method, we usually avoid certain values of m. For example, m should not be a power of 2, since if m=2p, then h(k) is just the p lowest-order bits of k.）

此处翻译的不是很好理解，感觉lowest-order bits of k没有翻译好。这句话到底是什么意思？
例如：
我们现在有3个数，m=23=8，下面我们进行看一下这3个数对 8 进行取模后的结果：

原数 原数的二进制 8的二进制 mod 8的商的二进制 mod 8 的余数的二进制
13 0000 1101 0000 1000 0000 0001 0000 0101
29 0001 1101 0000 1000 0000 0011 0000 0101
61 0011 1101 0000 1000 0000 0111 0000 0101
从上面的结果可以看出来，对于23=8取模的话，就是取“一个数的二进制的最低几位”（这是是最后3位）。对于其它的 2p 也是一样的，例如：22(0000 0100)，24(0001 0000) ……
2p 的最低位都是 0，所以对 2p 取模就等于就是把 k 截断保留低位的 p 位。除非已知各种最低 p 位的排列形式为等可能的，否则这种方式是很糟糕的。2p−1 也是一个糟糕的选择，因为 k 的各字符不会改其散列值（这个还没有看如何证明）。
一个不太接近 2 的整数幂的素数，常常是 m 的一个较好的选择。例如，假定我们要分配一张散列表并用链接法解决冲突，表中大约要存放 n=2000 个字符串，其中每个字符有 8 位。如果我们不介意一次查找需要平均检查 3 个元素，这样分配散列表的大小为 m=701。选择 701 这个数的原因是：它是一个接近 2000/3 但又不接近 2 的的任何次幂的素数。把这个关键字 k 视为一个整数，则散列函数为：h(k) = k mod 701

下面是为何使用素数的解释：

为什么求模运算要用素数（质数）—— 哈希表设计：这里的原因感觉有些道理。如果使用 8 这样的偶数的话，4这一列，4、12、20、28，这些哈希映射在同一个格子里的数都是前一个数+8，然后他们都能被2和4整除，这样就导致他们之间有很强烈的关系，很容易发生哈希冲突。如果我们把 4 这一列再进行散列化的话，这一列的数很容易发生冲突，例如，再进行 mod 4 的话，他们全都会到一个格子里；但如果进行 mod 5(素数) 的话，结果是 {4, 2, 0, 3}，可见素数的作用。

11.3.2 乘法散列法
主要思想：
使用关键字 k 乘上常数 A(0<A<1)，并提取 kA 的小数部分
用 m 乘以这个值，再向下取整
散列函数为：h(k) = ceiling( m(kA mod 1) )。
这里“kA mod 1”是取 kA 的小数部分，即 kA - ceiling(kA)。

乘法散列的一个优点是对 m 的选择不是特点关键，一般选择它为 2 的某个幂次（m=2p，p 为某个整数），这样可能正好使用计算机的一个字长。

关于 A 的取值，有一套算法，不是太明白。但比较理想的值为：A≈(5–√−1)/2=0.6180339887...
计算方法省略。。。

11.3.3 全域散列法（Universal hashing）
什么是全域散列法？
就是准备好一些散列函数，随机地使用散列函数，使之独立于要存储的关键字。

11.4 开放寻址法（Open addressing）
什么是开放寻址法？

总体概念为：所有元素都存放在线性的散列表里，每个槽位只存放一个元素，没有链表，也没有元素存放在散列表之外。当进行散列后，那个位置有值了，就在当前位置移动一定量的位置，然后再看有没有值；如果有值就再进行移动，直到有空位置；但如果散列表满了，就无法存放了。（开放导址法有很多种，不同点在于“在当前位置移动一定量的位置”。移动多少个位置，是每种方法的不同点）。

开放寻址法不用指针，而是计算出要存取的槽序列。不用指针而节省的空间，可以提供更多的槽，潜在地减少了冲突，提高了检索速度。但开放寻址法，散列表可能会被填满，以至于不能插入任何新的元素。该方法民到的一个结果便是装载因子 α 不会超过 1。（装载因子 α = 数据个数 n / 槽数 m，既然是一个槽只能装一个元素，所以 n/m 不能超过1)

为了使用开放寻址法插入一个元素，需要连续地检查散列表，称为“探查(probe)”，直到找到一个空槽来旋转待插入的关键字为止。检查的顺序不一定是 0，1，…，m-1，而是依赖于待插入的关键字。为了确定要探查哪些槽，我们将散列函数加以扩充，使之包含探查号（从0开始）以作为其第二个输入参数。对于每一个关键字 k，使用开放寻址法的“探查序列(probe sequence)”：

<h(k,0), h(k,1), h(k,2), ...h(k, m-1) >

例如，下面代码中散列表 T 中的元素为，无卫星数据的关键字 k，每个槽包含一个关键字，或是 NIL。HASH-INSERT 过程以一个散列表 T 和一个关键字 k 为输入，要反返回关键字 k 的存储槽位，要么返回“已满”的出错标志。

HASH-SEARCH 输入为一个散列表 T 和 关键字 k，如果槽 j 中包含了关键字 k，而返回 j；如果 k 不存在，则返回 NIL。（下面的图中感觉有错误，错：h(k, j)，对：h(k, i)）。

在分析中，做一个“均匀散列(uniform hashing)”的假设：每个关键字的探查序列等可能为<0, 1, ... m-1>组成的M!的任意一种。如果序列内容不是全包含<0, 1, ... m-1>的话，有的槽位可能就访问不到。例如：

第 1 个数插入时，用 h(k, 1)次，即 1 次；
第 2 个数插入时，用 h(k, 2) 次，即 2次。第 1 次用 h(k, 1)，但是有值了；第 2 次用 h(k, 2)，可以插入）
这样的话，每个数的插入，都是M!(M的阶乘种排序中的一种)。

散列函数的结果是一个数，但均匀散列的结果是一个完整的探查序列。例如：（这个在后面能具体地讲解，现在有个大概的印像就行）

k=7k=7，h′(7)=7h′(7)=7，Probing Sequence為{7,0,1,2,3,4,5,6}{7,0,1,2,3,4,5,6}
k=13k=13，h′(13)=5h′(13)=5，Probing Sequence為{5,6,7,0,1,2,3,4}{5,6,7,0,1,2,3,4}
k=50k=50，h′(50)=2h′(50)=2，Probing Sequence為{2,3,4,5,6,7,0,1}{2,3,4,5,6,7,0,1}
k=74k=74，h′(74)=2h′(74)=2，Probing Sequence為{2,3,4,5,6,7,0,1}
三种常用的开放导址法
真正的均匀散列是非常难以实现的，在实际应用中有一些近似方法，有三种技术常用来计算开放寻址法：线性探查、二次探查、双重探查。

(1) 线性探查(Linear Probing)
就是把 h(k) 的值，再进行迭代加 i (i=0,1,2…m-1)，来探查每个槽。
在线性探查中，初始探查位置决定了整个“探查序列”。例子请看 Hash Table：Open Addressing 中的 Linear Probing 部分

线性探查方法比较容易实现，但存在一个问题，称为一次群集（primary clustering）。随着连续被占用的槽不断增加，平均查找时间也随之不断增加。这种现像很容易出现。

(2) 二次探查(Quadratic Probing)

二次探查的话，增加了常数 C1、C2 来增加探查序列的分散性。但要注意 C1、C2、m 的选择，并不是所有 C1、C2、m 都可以产生 {0,1,…,m−1} 的排列组合。此外，如果两个关键字的初始探查位置相同，那么他们的探查序列也是相同的，这一改制可导致轻度的 clustering，称为二次群集（secondary clustering）。
例子请看 Hash Table：Open Addressing 中的 Quadratic Probing 部分

(3) 双重散列(double hashing)
双重散列是用于开放寻址法的最好的方法之一，因为它所产生的排列具有随机选择排列的许多特性：

其中 h1 和 h2 为辅助散列函数。然后，

  1. 第 1 次探查位置为 T[ h1(k) ]
  2. 接下来探查的位置是：( 前一个位置 + 偏移量 h2(k) ) mod m
  3. 循环第 2 步

因为 k = 14，散列表大小为13，h1(k) = k mod 13，h2(k) = 1 + (k mo 13)，所以 h1(k) = 1(14 mod 13)，h2(k) = 1 + 3(14 mod 11) = 4。

  1. 第 1 次探查 h1(k) 的结果 1。但 T[1] 已经有了 9，所以再进行探查。
  2. 第 2 次探查 i=1，( 1 + i * 4 ) / 14 = 5 / 14 = 5。但 T[5] 已经有了 98，所以再进行探查。
  3. 第 2 次探查 i=2，( 1 + i * 4 ) / 14 = 9 / 14 = 9。T[9] 没有值，所以放到了 T[9] 的位置。

为了能查找散列表，h2(k) 的值必须与表的大小 m 互质
为什么要是互质呢？这里有项神奇的事实：若 a 与 b 互质，那么 (a * i) mod b 且 i=0,1,2…b-1，正好可以形成 {0, 1, 2 … b-1}的排列组合（就是置换）。

若a=5,b=8a=5,b=8，那麼：

i=0，(5×0=0)mod8=0
i=1，(5×1=5)mod8=5
i=2，(5×2=10)mod8=2
i=3，(5×3=15)mod8=7
i=4，(5×4=20)mod8=4
i=5，(5×5=25)mod8=1
i=6，(5×6=30)mod8=6
i=7，(5×7=35)mod8=3
如何做到 h2(k) 与 m 互质呢？
有几种方法：
1，取 m 为 2 的幂，并设计一个总产生奇数的 h2。奇数和偶数总是为互质的。
2，取 m 为 素数，并设计一个总是返回比 m 小的正整数函数 h2。例如：h1(k) = k mod m，h2(k) = 1 + (k mod m’) 的话，m=701，可以设置 m’=700。
11.5 完全散列
什么是完全散列？
完全散列和链表散列有点像，只不过每个结点又一是个散列，而不是链表。

这个完全散列表是由两个散列表组成，一个是竖的一级散列表，还有就是横向的二级散列表。把一个 k 加入到散列表中过程如下：

首先用 h(k) 函数算出 k 在一级散列表中的槽位
再用 h(k) 公式和二级散列表中的参数，算出 k 在二级散列中的位置
例如，k=75，散列函数为 h(k)=(((a * k + b) mod p) mod m)，且 a=3，b=42，p=101，m=9，而一级散列表的位置是：(((3 * 75 + 42) mod 101) mod 9 = 2，所以首先把 k 放到 2 号槽位里面。接首，二级散列中有 a2、b2、m2 这三个参数，用这三个参数替换一级散列中的相应的 a、b、m 参数，则 h(k) = (((10 * 75 + 18) mod 101) mod 9 = 7，所以把 k 放到二级散列的 7 号槽位上。

为了确保在二级散列表上不冲突，一般二级散列表的槽数 m，为保存的数据个数的平方（n2）。适当地选择第一级散列函数，可以将预期使用的总体空间限制为 O(n)。