写在前面：本节内容相当抽象，适合睡前催眠。为了让描述变得简单，对于一些结论，我省略了使用数论的复杂证明过程。
散列表
散列表是一种较为抽象的数据结构。散列表的理解和实现的难度要远大于前述的三个线性数据结构。
回忆之前接触的两种数据组织方式：顺序式和链式，顺序式的结构逻辑是数据元素在物理上（内存中）相邻，而链式的逻辑是数据元素之间的链接关系。上述的这两类定址/寻址方式都与数据本身的值无关，这也就造成了“在数组中查找值是x的元素”这一操作的开销较大(开销是O(n))。
于是我们想到，如果我们可以依据每个数据元素的特征来为其定址，就可以有效降低这种搜索的时间消耗。也就是说，当我看到一个数据元素，我马上就可以通过它的特征来求出它应该在的位置，从而找到它。
例1：比如，现在我有13个盒子，分别标上数字1-13，我从一副去掉大小王的扑克牌里抽到一张牌(比如红桃3)，我马上就可以知道：这张牌应该属于标号是3的盒子。同样的，如果我们希望在已被放进盒子的牌中找一张黑桃8，我们应该去标号是8的盒子里找。
这样“数据位置与数据的特征直接相关”的数据结构被称为散列表，又称为哈希表，上述装扑克牌的盒子在逻辑上就是一种特殊的散列表。散列表使用到的这种提取出某一个元素特征，并映射到哈希表对应位置的算法（在例子中是“返回扑克牌的数字部分”）被称为散列函数或者哈希函数。作为分组依据的数据元素值（在例子中是牌的花色+点数）被称为键或者关键字。
理想的散列表是一个定长度数组，数组中存放键值。对于不同种类的键值，散列函数也会有所不同：对于整数键值，一个直观的散列函数是求“这个整数和散列长度的模”。
例2：有一内核为长度10的数组的散列表（实际上把长度定为10是一个非常差的选择），其散列函数是hash(x) = x mod 10。将列表[1,8,25,69,187,222,230]放入散列后的结果是：
下标 键
0 230
1 1
2 222
3
4
5 25
6 69
7 187
8 8
9
这就是一个直观的散列。实际上，我们通常会在散列的数据元素中加入一个或数个数据成员，使它存放更加充分的数据，相当于在扑克牌上附加一些额外的信息，比如“杀”、“闪”、“桃”。应用到程序中，比如，我想存入“学号为x的学生的考试成绩是y分”，就可以给每一个散列键x绑定一个值y。这种做法在python3中被称为字典（实际上python3的字典是更高级的散列），在C++中以STL容器unordered_map<typeA, typeB>实现
散列冲突
例3：在例2的散列表中再加入一个键240时，根据散列函数hash(x) = x mod 10，键240的下标理应是0，但是这个位置已经被键230所占据，而用240覆盖230又不是一个很好的做法。这种多个键值被对应至一个位置的情况被称为散列冲突。
分离链接法
散列冲突是不可避免的，无论使用多大的数组或者使用多么精妙的散列函数。为了想出一个解决散列冲突的方式，我们回到扑克牌的例子中：在这个例子中，我们使用了13个能放很多扑克牌的盒子，虽然在将一整副去鬼扑克牌分配至13个盒子中会发生39次散列冲突，但是在发生散列冲突之后我们没有必要将后来的键值覆盖掉原先的键值，也就是说我们扩大散列数组中的每一个下标对应的键存放区的空间即可。常见的做法是使用类似二维数组的做法，表中存放指针，指针指向存放键的数组等存储结构。
这种做法被称为分离链接法。
分离链接法使用了若干线性表来存放键，每一次寻址/插入新值都需要遍历一遍对应散列值的线性表。随着散列冲突次数的增加，这个线性表会越来越大，因此插入和寻址会变得越来越慢，在插入的数据规模特别大时，散列的查找时间退化为O(n)。
优化分离链接法的关键在于优化在散列外部接续部分的查找效率，比如可以使用平衡二叉查找树储存数据。C++STL中的unordered_map就会对于较大规模的键集合使用红黑树以提高查找效率。
开放定址法
线性探查
另一个想法是通过某种确定的规则，给出现冲突的新加入元素分配新的地址。注意：这种分配规则一定应是确定且稳定的以便寻址。这种确定的规则一般用函数表达，我们叫他冲突函数，它一般是“当前元素散列冲突次数”的函数。
那么一个键经过开放定址法所确定的最终的地址就是(hash(x) + F(i)) mod n，i是本次定位所调用F(i)的次数。
例4：用开放定址法解决例3的散列冲突。定义冲突函数F(i) = i：
迭代0：散列函数的结果是0，此时调用函数F的次数是0。因此最终定位是(0 + 0) % 10 = 0，发生散列冲突。
迭代1：散列函数的结果是0，此时调用函数F的次数是1。因此最终定位是(0 + 1) % 10 = 1，发生散列冲突。
迭代2：散列函数的结果是0，此时调用函数F的次数是2。因此最终定位是(0 + 2) % 10 = 2，发生散列冲突。
迭代3：散列函数的结果是0，此时调用函数F的次数是3。因此最终定位是(0 + 3) % 10 = 3，成功插入键240。
我们发现，如果冲突函数是F(i) = i，我们实际上是在按顺序查找空闲位置，因此这种使用F(i) = i的开放定址法又叫线性探测法。很容易知道，只要散列还有空闲位置，通过线性探测法寻找插入位置就一定不会失败。（当然，广义的线性探测法使用的是广义的一次函数而不是y = x，这种情况下不能保证插入不会失败这一性质。）
通过线性探测法查找元素也是简单的。首先求出希望查找的键的散列值，再依次查找，直到找到这个键或找到不属于这一系列的键（即散列值与目标键散列值不相等的）或空位置或循环散列一周。
稍加思考。我们发现，线性探查法倾向于将键放在一起，而放在一起的键又更容易引发散列冲突，导致新进的键又堆在这一堆键之后。最终的结果就是散列表中元素聚集为若干个区域，这是一个糟糕的现象，因为我们对于这种散列的插入和查找操作都需要很多次冲突解决迭代，这样最终我们的散列可能会退化。这种现象被称为一次聚集。一次聚集是一种类似于滚雪球的效应，越聚集则越容易聚集。
一次聚集来源于线性探查中的“一个接一个寻址”，因此我们可以通过调整冲突函数来轻松解决这一问题。
平方探查
扩大幂次带来分散。我们将冲突函数改为F(i) = i ^ 2，通过放大插入位置与上一次探查位置的平均距离来减慢聚集的速度。当然，这种情况下聚集仍然会发生，但是由于很难形成连续的插入区，聚集会减慢许多。使用二次函数的探查被称为平方探测法。平方探测法带来的慢速聚集叫做二次聚集。
平方探查是一种跳跃的探查方式，这就意味着当散列的大小、键的散列值和散列中键的分布情况“刚刚好”时，平方探查可能永远都不会找到一个空的位置来存放新元素，也就是平方探查可能导致插入失败。数学证明表示：如果使用平方探测的散列表大小是素数，那么当表的1/2为空时，插入一定不会失败。
换句话说，当表的占用大小超过了表的1/2时，插入就有可能失败。这就需要一个新的技术来解决这个问题。（一会再说）
因为查找过程需要依靠现有的“寻址途径中”的键来作为是否继续查找的标志，所以通过开放定址法构建的散列不支持标准的删除操作，仅可以使用标记的形式进行懒惰删除（比如在扑克牌上画一个叉表示删除）。（这个细节将在实现中展开说明）
二次散列法 / 双散列
线性探查法的问题主要是由于它的冲突函数“不够随机”，但是散列寻址要求冲突函数是稳定的，那么我们很自然地想到：使用一个额外的散列函数决定线性探查的步长即可。
二次散列法，又叫双散列，实际上是一种特殊的开放定址法。我们将线性探测法的冲突函数乘上一个额外的散列函数，得到新的冲突函数F(i, x) = i * doubleHash(x)，求出的索引可以表示为hash(x) + i * doubleHash(x)。
二次散列法也可以有效地避免一次聚集。但是二次散列法的难点在于：函数doubleHash(x)必须要严格设计，比如：它对于任意的输入，均不能输出0，否则线性探查的步长变为0，程序陷入死循环；再比如，它需要根据散列的大小来适当调整，使得所有的单元都能被探测到以避免插入失败。
再散列
再散列实际上是由平方探查法派生出的技术。我们知道，平方探查法对于散列的空闲空间有一定要求，对于素数尺寸的散列，空闲空间小于50%时散列将难以保证插入操作的稳定性。解决这个问题的非常直观的方案就是扩大散列尺寸。
我们一般会将散列扩大大约两倍大。当然，扩大刚好的两倍大也是可以的，但是这会导致散列尺寸不再是素数，可能导致散列性能下降，但是因为只引入了一个因数2，在扩大次数不多的情况下，这种性能下降可以忽略。具体的操作流程是这样的：
- 新建一个大小约为旧散列表2倍的新散列表（大小尽可能是素数）
- 生成新的散列函数
- 对于旧表的每一个键，将其插入到新散列中
- 删除旧散列表
这个过程叫做再散列。直观地看，再散列的开销是很大的，对于尺寸为n的旧散列，运行时间是O(n)。但实际上由于再散列的执行频率较低，它对于运行时间的影响也不是特别显著。
什么时候执行再散列？两种极端的做法是：
1.当散列表即将装满50%时（假设表的大小是素数）就执行
2.当发生了散列插入失败时才执行
方式1可能导致再散列执行次数过低，减慢程序的平均运行效率；方式2可能会导致失败的插入操作耗费过高的时间，减慢程序运行的最差效率。因此我们确定一个阈值，在散列占用率超过这个阈值或发生插入失败时进行再散列。
散列的性能
散列最具有竞争力的功能在于由键值查找。
比如，在一个长度为n的数组中查找一个值为x的数是否存在，平均渐近时间是O(n)；而在一个分布良好的稀疏散列中，这个操作的最差时间界是O(1)。即使发生了少量聚集，这个操作的平均时间仍是O(1)。在大量聚集的情况下，这一操作的平均复杂度退化至O(n)。
但是散列不维护键的顺序性质。虽然散列可以使用数组实现，但需要注意的是，这个数组对于用户不可见，并且数组中键的分布也是无序或近似无序的。所以我们不可能有”找到散列中第4个元素“这种操作。
