数据结构——散列表

---

前言

散列表是实现字典操作的一种有效数据结构。尽管最坏情况下，散列表中查找一个元素的时间与链表中查找的时间相同，达到了$\theta (n)$。然而在实际应用中，散列查找的性能是极好的。在一些合理的假设下，在散列表中查找一个元素的平均时间是$O(1)$。散列表是普通数组概念的推广。由于对普通数组可以直接寻址，使得能在$O(1)$时间内访问数组中的任意位置。本文介绍了散列表相关概念，解决散列冲突的两种方法，介绍3种散列值计算方法，最后还会介绍一种适用于静态存储的完全散列技术，它可以在$O(1)$最坏情况时间内完成关键字查找

---

一、直接寻址表

直接寻址法就是直接使用key的值作为槽位索引，直接寻址表的插入、搜索、删除操作都只需要$O(1)$时间。

二、散列表

当实际存储的关键字数目比全部的可能关键字总数要小时，采用散列表就成为直接数组寻址的一种有效替代，因为散列表使用一个长度与实际存储的关键字数目成比例的数组来存储。在散列表中，不是直接把关键字作为数组的下标，而是根据散列函数与关键字计算出相应的下标。

这里存在冲突问题，即两个不同的k被映射到同一个槽，这种冲突想要完全避免是不可能的，因为我们是把一个更大的全域$|U|$内的key映射到有限的哈希表$T$的空间。因此，为了尽可能减少冲突，我们可以从两个方向努力。一方面设计尽可能均匀散列的散列函数使得散列值尽可能均匀分布，另一方面必须要有解决冲突问题的策略。

其中一种解决冲突的主流方法是链表法，它通过将所有冲突的key存放在一个链表中来解决冲突。使用双向链表，这是为了更快的执行删除操作，删除操作的输入是一个给定的元素x，而非key，而如果使用单向链表那就不得不在删除前通过遍历链表来找到这个元素的前一个元素。

有如下的定理：

这些定理可通过概率计算来证明。

对于链表法，插入、删除操作都可以在$O(1)$内完成，而搜索操作取决于链表中元素个数。其期望值为$\alpha$，当散列表槽位数与关键字个数n成正比，即$n=O(m)$，则有$\alpha =n/m=O(m)/m=O(1)$,因此搜索操作也可在常数时间内完成。

三、散列函数

一个好的散列函数需要满足简单均匀散列假设，有时散列函数的某些应用可能会要求比简单均匀散列更强的性质。例如，可能希望某些很近似的关键字具有截然不同的散列值，而后文将要讲解的全域散列法通常能提供这种性质。

1.除法散列法

在用来设计散列函数的除法散列法中，通过取k除以m的余数，将关键字k映射到m个槽中的某一个上，即散列函数为：$h(k)=k$ $mod$ $m$。

m的选择有一定要求，例如，m不应为2的幂，因为如果m=2^p，则h(k)就是k的p个最低位数字。除非能够保证这p个数等可能分布，否则设计时最好考虑所有位数。

一个不太接近2的整数幂的素数，常常是m的一个较好的选择。

这里解释一下为什么选择素数，这其实涉及数论中的知识，假如m取9，它不是一个素数，如果输入序列分布存在一定规律，包含大量3或者6的等价类（即x mod 9等于3或6的所有key），这些key的增长步长会与m相吻合，这些key会落在固定的几个槽中，从而使的其他的槽利用率降低，而如果m是素数，那么它与任何数公约数都是1（当然输入序列不能是一个m的倍数的序列，这种可能性很小），即它的步长是1，从而key能够在m个槽位上均匀分布。也就是说选择素数的目的是为了屏蔽输入序列自身的分布规律性带来的影响，如果能确保输入序列的分布随机性，m的选取其实无关紧要，但实际情况是key之间往往存在关联性。

2.乘法散列法

这里A公认的通常取黄金分割比0.618…。根据Weyl均匀分布定理，如果A 是无理数，则序列{KA mod 1} 会无限接近[0,1) 中的任意点，避免周期性重复。

$kA$ $mod$ $1$的意义在于把key的域等可能的映射到区间[0,1)中 。在把这个值放大m倍就得到了对应的槽位。

乘法散列法的一个优点是对m的选择不是特别关键，一般选择它为2的某个幂次（m为2^p,p为某个整数）

如果m是2的幂次，那么我们在实现时可以将复杂的浮点数与乘法运算优化为定点数+移位运算，使用32位表示小数部分（其精度是1/2³²），把它与key相乘，高32位溢出，得到低32位，这32位即为小数部分放大2³²倍的结果，乘以m即右移（32-p）位取其高p位，就是所得的散列值。如果m不是2的幂次，因为得到的小数部分是个随机值（它屏蔽了key自身分布规律的影响），我们可以通过用此值对m取余替代右移操作来计算散列值。

3.全域散列法

上述两种方法虽好，但如果人为恶意构造序列，依然可以构造出一个序列使得所有key散列到一个槽中，唯一有效的改进方法是随机地选择散列函数，使之独立于要存储的关键字。这种方法称为全域散列，不管对手选择了怎么样的关键字，其平均性能都很好。

全域散列使用一个函数族，其中每个函数都能够将key均匀散列到m个槽位，即每个key散列到任意槽位的可能性都是1/m，每次初始化表时从中随机选择一个函数。

全域散列法的插入、删除时间均为$O(1)$，搜索操作的期望时间也为$O(1)$。

其中通过$（a\ast k+b）modp$屏蔽 key 的原始分布规律，使得散列值均匀分布，再通过与m取余将值压缩到$[0,m)$。m不必是一个素数，保证选择的素数p>m即可。对于素数p的全域散列函数类包含p（p-1）个散列函数。

四、开放寻址法

开放寻址法是解决散列冲突的另一个办法，它将散列值从一个数推广到一个序列，这个序列作为扫描探查特定key的序列，简单来说，开放寻址法将所有key包括冲突key存放在同一张表中。当给定key与表中某个现有key发生冲突时，它通过对散列值添加一个偏移量来产生新的散列值，而这样产生的散列值可能会继续与其他的key发生冲突，那就换一个新的偏移量，直到找到一个空槽为止，这个过程会对应某个散列值序列来进行。

因为这样的工作方式，所以它对删除操作的支持不如链表法友好，因为如果直接删除了某个key，那么在它之后插入的与他冲突的key就找不到了，这就好像链表法中，删除了链表表头一样。所以一般只能软删除，这样的话就好比，链表中前面插了一些多余的空节点，肯定对搜索操作产生影响。

开放寻址法的关键在于如何设计这个产生偏移量的函数，这直接关系着表的性能。

线性探查与二次探查很好理解，但是它们都只能产生m个探查序列，且会产生群集问题，即key最终都群集在一起，那么下一次插入key发生冲突的概率自然大大增加，二次探查因为偏移量更大，key的分布相当更分散一些，群集问题相对弱一些。

双重散列法通过使用两个辅助散列函数，产生更加随机的增长步长，它能产生m²个不同的探查序列，因为每个key会散列两次，总共有m*m种可能性，$h_2(k)$要求与m互质，这与除法散列法m取素数道理类似，防止产生的偏移量步长与m吻合，使得某些槽位永远探查不到。常用的方法是取m为素数，$h_2(k)$取较m小的一个整数。

五、完全散列

完全散列适用于静态集合，它使用两级散列方式来保证最坏情况$O(1)$的查询，当第一次散列发生冲突时，会使用二次散列函数将key散列到一个大小为m_j=n_j²的二次散列表中（n_j为散列到槽j中的key的个数），两个散列函数全部取自自己对应的全域散列函数类。

根据上述定理可以通过有限次尝试来选出一个不会产生冲突的二次散列函数。使得二次散列表中的key不产生冲突。

通过概率计算可以证明，完全散列使用的总体存储空间的期望数为O(n)，这里包括主散列表和所有的二级散列表所占的空间。