算法导论第十一章散列表学习总结

散列表是可以实现字典操作(INSERT、SEARCH和DELETE)的一种有效数据结构，是普通数组概念的推广，把关键字k映射到槽h(k)上的过程称为散列，多个关键字映射到同一个数组下标位置称为冲突，好的散列函数应使每个关键字都等可能地散列到m个槽位中，以上即为本章介绍的主要内容。

直接寻址表

直接寻址表也即是数组，其中每个位置称为槽，一个槽对应一个关键字，是一种简单而有效的技术，但有一个明显的问题：若域U很大，要在机器中存储大小为|U|的一张表T就有点不切实际，且当实际要存储的关键字集合K相对数组的域U来说小时，分配给数组的大部分空间都要浪费掉。

散列表

在直接寻址方式下，具有关键字k的元素被存放在槽k中，而在散列方式下，该元素处于h(k)槽中，也就是说可以利用散列函数h，根据关键字k计算出槽的位置，散列函数h将关键字域U映射到散列表T[0…m- ]的槽位上。
实际上，两个关键字可能映射到同一个槽上，这种情形称为冲突，为了解决冲突，主要从两方面考虑，通过精心设计的随机散列函数来尽量减少碰撞以及解决冲突的方法。
链接法是最简单的冲突解决方法，在该方法中，把散列到同一槽中的所有元素都放在一个链表中，如下图所示：

散列方法的平均性能依赖于所选取的散列函数h，将所有的关键字集合分布在m个槽位上的均匀程度。简单均匀散列即是任何一个给定元素等可能地散列到m个槽中的任何一个，且与其他元素被散列到什么位置上无关。
定理11.1：在简单均匀散列地假设下，对于用链接法解决冲突的散列表，一次不成功查找的平均时间为θ(1+α)。
定理11.2：在简单均匀散列地假设下，对于用链接法解决冲突的散列表，一次成功查找的平均时间为θ(1+α)。

散列函数

好的散列函数应满足简单均匀散列的假设，且是以独立于数据中可能存在的任何模式的方式导出散列值。多数散列函数都假定关键字域为自然数集N = {1, 2, 3, … }，如果所给关键字不是自然数，则必须有一种方法来将它们解释为自然数。
除法散列表：散列函数为h(k) = k mod m，即通过取k除以m的余数，来将关键字k映射到m个槽位中的对应位置中。
乘法散列法：散列函数为h(k) = m*(k*A mod 1) (0<A<1)，其优点是对m的选择没有什么特别的要求，一般选择它为2的某个幂次方。

开放寻址法

开放寻址法中，所有的元素都存放在散列表里，这种情况下，散列表可能会被填满，以致于不能插入任何新的元素，即每个表项要么包含动态集合中的一个元素，要么为空。 当查找一个元素时，要检查所有的表项，直到找到所需的元素或者最终发现该元素不在表中。开放寻址法的优点在于它不需指针，只要计算出要存取的各个槽位，这也就节省了空间，以提供更多槽位。
在开放寻址法中插入元素，需连续探查散列表的各项，直到找到空槽，其检查的顺序是要依赖于待插入的关键字，对于每一个关键字k，探查序列必须是<0, 1, … m - 1>的一个排列。
查找关键字k的探查序列与其插入时是一样的，在查找过程中碰到空槽时即停止，这里的假设是关键字没被删除。
在开放寻址方法的删除操作较困难，因为当删除关键字时，不能仅将该槽位标记为NULL来表示它是空的。

有三种技术常用来计算开放寻址中的探查序列：线性探查，二次探查，以及双重探查，其中，双重散列产生的探查序列数最多。
线性探查：使用的散列函数为h(k, i) = (h1(k) + i) mod m i = 0, 1, …, m-11，其初始探查位置确定了整个探查序列。该方法较易实现，但存在一次群集问题，从而加大平均查找时间。
二次探查：使用的散列函数为h(k, i) = (h1(k) +c1 i+c2i2) mod m i = 0, 1, …, m-1，其中h1(k)是一个辅助散列函数，c1和 c2为辅助常数，后续探查位置在此基础上加偏移量，其效果比线性探查好很多，但也会导致轻度的群集即二次群集。
双重散列：使用的散列函数为h(k, i) = (h1(k) +i(h2(k)) mod m i = 0, 1, …, m-11，它是用于开放寻址法的最好方法之一。