散列（hash）又称哈希，是一种组织数据的方式。从其中文译名来看，有打乱排列的意味，事实上也正是这样。散列函数能够将一组数据随机排布到某个输出区间上，这种随机性使得我们可以借其实现更高性能的容器数据结构。
本文从基本的散列表（hash table）开始，介绍链接法和开放寻址法对冲突的不同解决方案，进一步引出全域散列（universal hashing）与完全散列（perfect hashing）的概念与实现方式，并推导它们的时间和空间复杂度。最后，看看实际中，Java是如何实现散列表的。
目录
散列表的由来
考虑某一类数据，如果关键字的取值范围是有限的，比如所有由三位十进制数字组成的整数，其取值范围为0~999。那么我们可以直接创建一个大小为1000的数组，将每个元素保存在相同下标对应的位置上，需要访问哪个直接通过下标索引，时间复杂度为。
这种方法的问题是，虽然有1000种可能的数据，但实际上总的数据量可能很小，也许只有10个，它们在数组中分布的很稀疏，相当于浪费了大量的存储空间。
此时，散列的作用就凸显出来了。我们可以使用某个散列函数将关键字的定义域映射到的范围内，只需要大小为10的数组即可装载这些数据。不过，问题也很明显，将这10个数据恰好映射到范围内的不同位置恐怕不太容易，这样的散列函数是不容易找到的。况且就算找到了，针对不同的数据，这一性质肯定是无法保证的。
大多数情况下，至少会有两个数据被映射到了同一个位置，这种情况我们称为冲突。解决冲突的方式有两种，链接法和开放寻址法，我们将分别阐述这两种方法。
链接法
链接法在每个数组中链接一条链表，将冲突的元素依次放置在链表中。访问时，先根据散列函数计算数组的下标，然后遍历对应的链表，找到目标元素。下图展示了链接法的存储结构。
其中，和具有相同的散列值，因此以链表的形式挂接在数组的第二个位置上。其它元素同理。数组的每个位置称为一个槽（slot），记数组的长度为。
散列表的原理很简单，但问题是这种数据结构的性能如何呢？
可以想象，最好的情况下，散列函数将关键字均匀地分布在整个数组上，此时，每个链表的平均长度很短。最坏情况下，散列函数将所有关键字恰好都映射到同一个下标，链表长度与数据总数相同，导致时间复杂度为。
这样看来，散列表的性能比较依赖于散列函数的选取。我们将最好情况归纳为一个假设，称为“简单均匀散列”。该假设认为我们选择的散列函数可以将任何一个元素等可能地散列到个槽中的任意一个。在这一假设下，每个槽链接的元素数平均为个，于是平均情况下，访问任意一个元素的时间复杂度都应该不超过。其中，表示计算散列函数所需的时间。
我们将称为装载因子（load factor），它的实际意义是每个链的平均长度。根据上文的分析，当装载因子为常数时，散列表的时间复杂度为。
接下来的问题是如何选取散列函数，使其尽量接近简单均匀散列的假设。
对于前面提到的将散列到的案例，最简单的方法是对取模，即，其中，记散列函数为。可惜这个散列函数并不优秀，因为的值只依赖于该数的最后一位。如果最后一位在所有数据中的分布并不均匀，我们离均匀散列假设就渐行渐远了。当可以自行决定的大小时，我们倾向于将其设为一个不接近2的整数幂的素数，并仍然取。此时，的任意位数都不会单独决定落入的槽，各个数字对求模结果的影响是近乎随机的，因此可以得到更接近于简单均匀散列的效果。
不过这里需要明确指出，我们并不能证明这种方法符合简单均匀散列，因为无法事先得知取值的概率分布。对于不同的的集合，同一个散列函数显然会得到均匀程度各异的结果。
试想存在一个恶意的对手，他针对我们提供的散列函数，强行构造出一个发生严重冲突的数据集，比如，让所有关键字全部落入同一个槽中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。
那么问题又来了，如何增加随机性，以及增加多大的随机性呢？如果提供两个散列函数，每次随机选择使用其中之一，攻击者还是可以分别构造出针对这两种情况的数据，相当于我们有50%的几率被攻击成功，这显然不行。如果每次使用的散列函数都完全不一样，攻击者自然无从下手，这是可以的，但问题是不可行。我们无法令计算机生成无限多个不同的散列函数，因为即便是随机数生成器，我们也要指定在多大的范围内生成数据，且散列函数用到的随机数是整数，这就注定了它的有限性。
让我们从另一个角度衡量散列函数的随机性。首先，我们的目标是，对于对手构造的任意关键字集合，我们随机生成的散列函数都能将关键字均匀分散在所有槽中，且每个槽中链表长度的期望为。之所以目标是，是因为上文证明过这种情况下散列表的时间复杂度为。为了达成这一目标，倒推回去，可以发现对于任意两个不同的关键字，只要我们随机选取的散列函数使两者发生冲突的概率不大于，就能满足要求。简单解释下怎么得出的这个结论。对于某个特定的关键字，其它个关键字与其冲突的概率都是，且冲突与否在各个关键字之间是独立的，那么与其冲突的关键字数量的期望就是，这正是该关键字所在链表的长度，它是不大于的。
接下来，如何找出符合条件的散列函数呢？显然，我们需要准备一个散列函数组，每次从组中随机取出一个。这样的散列函数组称为全域散列函数组，下面给出一种实现方式。
首先，选择一个足够大的素数，使得所有关键字都处在的范围内。然后，全域散列函数组中的任意一个函数定义如下。
其中，为中的任意整数，为中的任意整数。照此方式可以产生个不同的散列函数，这些函数构成了一个全域散列函数组。实际使用时，在创建散列表后，随机对和取值，得到该散列表应当使用的散列函数即可。
现在，我们的重点是证明这样生成的散列函数组的确是全域的。证明过程如下。
对于任意不同的两个关键字和，我们计算式(11.3)的前半部分，令
注意到
其中，意味着左右在模的意义上相等。由于和模都不为0，那么它们的乘积模后也不为0（这一结论可以证明，但这里我们略过）。于是，进而可以发现选择不同的和，生成的和也是不同的。换句话说，数对与数对有一一对应关系。
接下来我们看看与是否会落入同一个槽。对于某个给定的，由于且，的取值只有种。其中发生冲突的情况，即的次数至多为。这个式子可以这样理解，的每个取值中就存在一个与冲突的情况，表示最多有这么多组，减一去掉的是的那一项。化简该式，得到
既然冲突的情况有这么多种，那么冲突的概率为。终于，我们证明了这种方法的确生成了全域散列函数组。
开放寻址法
除了使用链表解决冲突，开放寻址法提供了另外一种解决方式。
简单来说，要想插入一个元素，计算出散列值后，如果该位置已经被占用，则需要向后检查整个散列表，找到第一个空位置并插入。很自然地，如果多个数存在冲突，它们会依次向后排布。查找元素时也一样，我们需要从散列值对应的位置开始向后查找，直到找到目标元素。这一逐次检查或查找的过程称为探查（probe），探查的顺序可以是逐个遍历，也可以是以某种特殊的序列跳着遍历。不同的探查序列具有不同的时间复杂度，下面我们会详细介绍。
最容易想到的是从散列值位置开始逐个遍历的探查序列，称为线性探查。该方法的散列函数可以表示为
注意到，对于开放寻址法，散列函数多了一个参数，表示探查序列的第个位置。也就是说，开放寻址法的散列函数给出的不是一个散列值，而是一个探查序列，共个数。
从线性探查的散列函数可以看出，对于任意不同的关键字，探查序列的可能性只有种，只要起始散列值相同，探查序列就相同。这会导致严重的群集现象，当一个空槽前面有连续的多个满槽时，任何一个可能落入这些满槽的散列值最终都会放入该空槽。这样较高的概率使得连续的满槽变得越来越长，大量元素聚集在一起。
为了解决这种群集问题，我们可以将散列函数改为如下形式。
此形式称为二次探查，因为探查序列的分布是探查序号的二次函数。可以想象，二次探查不会导致上面介绍的群集现象，因为同一个散列值的探查序列是跳着放置的，一般不会占用相邻的槽。不过，二次探查探查序列的总数仍然只有个，还是取决于起始位置，函数值相同的两个关键字必然会发生冲突。
进一步解决这一问题，我们可以采用双重散列（double hashing）方法，其散列函数如下。
它与前两种方法有很大的不同，探查序列的总量变成了个，因为对于函数值相同的两个关键字，仍然可能产生种不同的探查序列。
读到这里，也许会产生这样的想法，是不是三重散列、四重散列会更好？书上没有谈到这方面的内容。但可以想象，增加散列函数的数量应当可以扩展探查序列的可能性，比如将上式中的替换为，双重散列变成了一个二次探查，而且是和随关键字随机变化的二次探查，显然探查序列会多出很多。
实际上，最好的探查方法称为均匀散列（uniform hashing），每个关键字的探查序列等可能地为个位置所能产生的种排列中的任意一个。均匀散列很难实现，上面介绍的方法都是对它的近似。
完全散列
回顾前面介绍的全域散列，它在任意输入的情况下都能达到比较好的平均情况性能。但值得注意的是“平均情况性能”这六个字，就像BFPRT——Top k问题的终极解法一文中介绍的随机快速选择算法一样，虽然很难遇到导致最坏情况发生的输入，但这种可能性仍然是存在的，没有完全消除。我们需要继续追寻，找到像BFPRT一样，能在确定情况下提供出色的最坏情况性能的散列算法。
完全散列算法给出了关键字集合为静态时的解决方案。我们来看看它如何在最坏情况下达到的时间复杂度。
首先，解释一下为什么强调关键字集合是静态的。所谓静态，是指所有关键字已经给定，后续的操作只有查询，而不需要插入或删除。比如程序设计语言中的保留字集合，或者CD-ROM上的文件名集合，它们都是固定的，一旦产生就绝不可能再更改。这种情况下，我们可以事先花一些时间选择合适的散列函数，所以相对于动态关键字集合，更容易达到较高的性能。
接下来，我们考虑在不限制空间复杂度的情况下如何达到的时间复杂度。最直接的想法，让散列数组的长度尽量大，因为对于固定的关键字集合，越大，冲突的可能性就越低。但是，无论取多大的数，冲突的可能性都不会降到0，只会越来越接近0。此时，静态关键字集合的好处就出来了，当冲突的可能性较低时，我们可以多试几个散列函数，找到不发生冲突的那个，确定为最终使用的散列函数。这样，任意关键字的查询时间都为1。那么，取多大的数最合适呢？我们可以做一个数学推导。对于个关键字的集合，两两组合共有对。如果从全域散列函数组中随机取一个散列函数，那么每一对关键字发生冲突的概率为。由于每一对关键字是否发生冲突是独立事件，假设是一个统计冲突次数的随机变量，我们可以得出该随机变量的期望。
观察该式，发现如果取，可以得到。再根据马尔可夫不等式，当时，有。也就是说，当散列数组长度为关键字数量的平方时，发生冲突的概率小于。这个概率告诉我们，在的空间代价内，我们可以尝试若干个散列函数，很容易找到一个不发生冲突的情况，从而实现的时间复杂度。
简单解释一下，马尔科夫不等式提供了用期望估计概率的一种途径，下面是其证明过程。
当然，实际应用中，不考虑空间复杂度毕竟不太现实。我们还是需要把散列数组限制在的数量级，但与普通的散列表不同的是，我们可以把链表替换成二级散列表。假设我们直接取，用某个全域散列函数将个数散列到个槽中。对于每个槽中的关键字数量，我们用大小为的二级散列表来提供无冲突的常数时间查找。刚才已经推导过，当槽的数量是关键字数量的平方时，很容易找到一个无冲突的散列函数。因此，该方案总体时间复杂度是，只需要计算两次散列函数即可。
接下来的问题就是，这种方法的空间复杂度是否低于？答案是肯定的，而且只有。证明过程非常巧妙，我们来详细介绍一下。
首先明确推导的目标是，所有二级散列表的总大小与的关系。假设散列函数是从一个全域散列函数类中随机选取的，那么二级散列表总大小的期望可以表示为。借助一个显而易见的恒等式，代入上式，得
注意到恰好是一级散列表中发生冲突的总对数，因为对于个进入同一个二级散列表的关键字，我们认为它们两两之间都发生了冲突，即冲突次数为。根据全域散列的性质，任意两个关键字冲突的概率至多为，于是总冲突的数量至多为。也就是说，。代入上面的推导，得到
如此，我们证明了所有二级散列表总大小的期望不超过。这里的期望表示随机选取散列函数导致的平均情况，当然，我们有可能随机选择出一个导致二级散列表总大小很大的散列函数，但这种情况不常见。为了给出一个直观的结果，我们再次利用马尔可夫不等式将期望转换为概率，令，有
该结果的含义是，随机选取散列函数，使得二级散列表总大小超过的概率不大于。在静态关键字集合的情况下，我们仍然可以多试几次，每次随机选择一个散列函数并计算二级散列表的总大小，如果不满意，就重新选取，根据这一概率，不需要太多次就可以找到满意的结果。
下图是一个使用完全散列的具体案例，可以看到，每个二级散列表中存储了该散列表的全域散列参数，在实际计算时根据这些参数就可以构造出对应的散列函数。
总结一下，完全散列使用两级散列表的结构，每级的散列函数都选自于全域散列函数组。由于处理的是静态数据，所有散列函数一旦确定，无需更改。但确定的过程可能需要多次尝试，以满足时间复杂度和空间复杂度。
实际应用中的散列表
虽然全域散列和完全散列具有良好的理论性能，但实现起来不太方便，前提条件也多。在真实的开发中，我们往往使用的是更简单直接的散列表。
以Java为例，HashMap就是典型的散列表实现，实现方式与我们介绍的链表法基本一致。但不同的是，为了在数据量动态变化时仍然保证的时间复杂度，HashMap会在链表长度过长时将槽的数量扩大一倍，并修改散列函数以重新分布元素在散列表中的位置。这种方法可以保证链表长度维持在常数范围内，从而达到时间复杂度。但由于未引入随机性，有可能出现大量关键字聚集的现象，从而导致HashMap迅速扩容，占用过多的空间。不过，在实际使用中，HashMap还是表现得不错的，若非恶意攻击，一般不会出现这种情况。此外，JDK 1.8改进了HashMap的实现，当链表长度较长时将其转换为红黑树（一种二叉搜索树，查找速度比链表快，我们将在后续的文章中介绍），也在一定程度上缓解了冲突的问题。
对于用户而言，我们能做的是提供良好的hashCode方法，使其生成的散列值尽量随机。我在另一篇文章中介绍了如何给自定义类编写良好的hashCode代码，感兴趣的同学可以前往查看。