数据结构：散列表 gaunthan Posted on Aug 7 2016 ? Searching ? ? Hashing ? ? Data Structures ? ## 散列的概念 根据设定的散列函数和处理冲突的方法将一组关键字映像到一个连续的有限地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为**散列表**(hashing table)，这一映像过程称为**散列**(hashing)，所得存储位置称为**散列地址**。 散列是一种用于以**常数平均时间**执行插入、删除和查找的技术。但是，散列不支持任何排序。 ## 散列表 理想的散列表数据结构就是一个包含有关键字的具有固定大小的数组。典型情况下，一个关键字就是一个带有相关值的字符串。表的大小记为$TableSize$，其将作为散列数据结构的一部分。表下标范围从$0$到$TableSize - 1$。 散列表的**装填因子**(load factor)$ \lambda$ 为散列表中的元素个数与散列表大小的比值，即： $$ \lambda = {当前元素个数 \over 散列表的最大容量}$$ ## 散列函数 每个关键字被映射从$0$到$TableSize - 1$这个范围中的某个数，并且被放到适当单元中。这个映射就叫做**散列函数**(hash function)。 ### 影响选择散列函数的因素 在现实中，应该视不同的情况采用不同的散列函数，下面是一些可能的考虑因素： - 计算散列函数所需的时间 - 关键字的长度 - 散列表的大小 - 关键字的分布情况 - 记录查找的频率 综合这些因素，才能决策选择哪种散列函数更合适。 ### 好的散列函数的特点 一个好的散列函数应（近似地）满足简单均匀散列假设：每个关键字都被等可能地散列到m个槽位中的任何一个，并与其他关键字已散列到哪个槽位无关。遗憾的是，一般无法检查这一条件是否成立，因为很少能知道关键字散列所满足的概率分布，而且各关键字可能并不是完全独立的。 ### 将关键字转换为自然数 多数散列函数都假定关键字的全域为自然数集，因此，如果所给关键字不是自然数，那就需要找到一种方法来将它们转换为自然数。 由于关键字在计算机中都是以二进制形式存储的，我们可以将关键字视作一串二进制字节。 ### 除法散列法 如果输入的关键字是整数，则一般合理的方法就是直接返回$Key \mod TableSize$的结果，除非关键字具有某些不理想的性质。在这种情况下，散列函数的选择需要仔细考虑。例如表的大小是10而关键字都以0为个位，这将导致所有关键字的散列地址都为0，使得冲突100%发生。 为了避免上面那种情况，好的方法通常是确保表的大小是一个素数。当输入的关键字是随机整数时，散列函数不仅算起来简单而且关键字的分配也很均匀。 通常来说，输入都是字符串。在这种情形下，需要仔细选择散列函数。一种简单的选择方法是把字符串中的所有字符的ASCII码值加起来： ```c typedef unsigned int Index; Index Hash(const char* key, const int tableSize) { unsigned int hashVal = 0; while(*key) { hashVal += *key++; } return hashVal % tableSize; } ``` 这种方法实现简单而且计算快速，但是当表很大时，分配关键字将变得很困难。例如设表长$TableSize = 10007$，并且所有关键字至多8个字符长。由于char型量的值最多是127，因此散列函数只能取值在0到1016之间，其中$1016 = 8 * 127$。显然这不是一种均匀的分配。 ### 全域散列法 如果让一个恶意的对手来针对某个特定的散列函数选择要散列的关键字，那么它会将n个关键字全部散列到同一个槽中，使得平均的检索时间为$\theta(n)$。任何一个特定的散列函数都可能出现这种最坏情况。唯一有效的改进方法是随机地选择散列函数，使之独立于要存储的关键字。这种方法称为**全域散列**(universal hashing)，不管对手选择了怎么样的关键字，其平均性能都很好。 全域散列法在执行开始时，就先从一组精心设计的函数中随机地选择一个作为散列函数。就像在快速排序中一样，随机化保证了没有哪一种输入会始终导致最坏情况性能。因为随机地选择散列函数，算法在每一次执行时都会有所不同，甚至对于相同的输入都会如此。这样就可以确保对于任何输入，算法都具有较好的平均时间性能。 ## 冲突及其解决方法 由于关键字集总是大于表的单元集，因此不同的关键字是有可能会映射到相同的单元中的。这种情况称为**冲突**(collision)。 为了能够让冲突的关键字都能够存放到散列表中，需要解决冲突的方法，主要有两种： - 分离链接法 - 开放定址法 ### 分离链接法 **分离链接法**(separate chaining)是解决冲突的一种方法，其做法是将散列到同一个值的所有元素保留到一个链表中（默认插入到表头后）。为了方便起见，这些链表都有表头，如：  关键字"John Smith"和"Sandra Dee"发生冲突，因此将冲突项"John Smith"插入到"standra Dee"的前面。 如果空间不充裕，可以不使用这些表头。如：  链接法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也带来了查找时需要遍历单链表的性能损耗。 使用这种方法的散列表，其时间复杂度如下表所示： |操作|最坏时间复杂度|备注| |--| |插入|$O(1)$|只要插入位置在头部，就可以常数时间完成插入，因为不需要再查找插入位置| |查找|$O(N)$|所有关键字的散列值都一样（但发生概率显然极小），且被查找的关键字位于链表末端| |更新|$O(N)$|显然更新操作的时间复杂度与查找是一致的| |删除|$O(N)$|同上道理| 虽然最坏时间复杂度很糟糕，但是平均来说，散列表的操作都只需要常数时间。当然，这要求有一个不那么差的散列函数和冲突解决方法。 ### 开放定址法 分离链接散列算法的缺点是需要动态分配/释放内存，这导致了算法的速度多少有些减慢。同时，它还要求对另一种数据结构——链表的实现，这又增加了系统的复杂性。 **开放定址法**(Open addressing)是另外一种不用链表解决冲突的方法。在开放定址法中，如果有冲突发生，则要尝试另选单元，直到找到空的单位为止。 根据查找空单元的方式，开放定址法又细分为好几类： - 线性探测法 - 平方探测法 - 其他 #### 线性探测法 在**线性探测法**中，探测函数$f$是$i$的线性函数，典型情形是$f(i) = i$。这相当于逐个探测每个单元（必要时可以绕回）以查找出一个空单元。只要表足够大，总能找到一个自由单元，但是花费的时间是相当多的。更糟的是即使表相对较空，占据的单元也会开始形成一些区块，其结果称为**一次聚集**(primary clustering)，于是，散列到区块中的任何关键字都需要多次试选单元才能够解决冲突，然后该关键字才被添加到相应的区块中。 示意图如下：  使用这种方法的散列表，其时间复杂度如下表所示： |操作|最坏时间复杂度|备注| |--| |插入|$O(N)$|可能几乎遍历完整个表才发现插入位置。注意，没有空闲空间的情况下，插入操作将失败| |查找|$O(N)$|聚集情况太严重| |更新|$O(N)$|显然更新操作的时间复杂度与查找是一致的| |删除|$O(N)$|同上道理| 注意使用线性探测法删除元素时，只需简单地将其标记为无效（注意我们不能真的删除它，因为查找元素时空单元是查找的终止条件）。而使用分离链接法的话，还得释放内存。 #### 平方探测法 平方探测法是消除了线性探测法中一次聚集问题的冲突解决方法。平方探测就是冲突函数为二次函数的探测方法，因此也称为二次探测法，流行的选择是$f(i) = i^2$。 对于平方探测法，一旦表被填满超过一半，或者当表的大小不是素数同时表还未被填满一半，就已经无法保证能够查找一次就找到空单元。因为最多有表的一半可以用作解决冲突的位置。 注意，二次探测法虽然可以消除一次聚集，却可能会造成**二次聚集**(secondary clustering)：两个元素经散列函数计算出来的位置若相同，则插入时所探测的位置也相同，从而形成某种无用功。 #### 随机探测法 还有一种方法是在冲突时，随机生成一个位移量，以决定探测位置。 #### 再散列 对于使用平方探测的开放定址散列法，如果表的元素填得太满，那么操作的运行时间将开始消耗过长，且插入操作可能失败。这可能发生在有太多的移动和插入混合的场合。此时，一种解决方法是建立另外一个大约两倍大的表（并且使用一个相关的新散列函数），扫描整个原始散列表，计算每个（未删除的）元素的新散列值并将其插入到新表中。整个操作就叫**再散列**(rehashing，或重新散列)，其运行时间为$O(N)$。 再散列可以用平方探测以多种方式实现： * 表满一半就再散列 * 只有当插入失败时才再散列 * 途中(middle-of-the-road)策略：当表到达某一个装填因子时进行再散列 #### 双散列 如果冲突解决函数本身也是一个散列函数的话，那么解决冲突时，遇到上面问题的概率应该会大大减小。毕竟，散列函数本身就要尽量阻止冲突。 **双散列**(double hashing)就是在遇到冲突时，使用一个散列函数来计算查找位置，以降低因为聚集而激增的查找次数。 ### 公共溢出区法 这种方法为所有冲突的关键字建立一个公共的溢出区来存放它们。在查找时，对给定值通过散列函数计算出散列地址后，先与基本表中的相应位置进行比较，如果相等，则查找成功；如果不相等，则顺序查找溢出表。 对于冲突数据很少的情况下，公共溢出区的查找性能是很不错的。 ## 查找性能分析 如果没有冲突，散列表查找是所有查找中效率最高的。因为无论输入规模有多大，它总可以在常数时间内完成操作，即查找操作是$O(1)$阶的。 可惜，没有冲突的散列只是一种理想。在实际的应用中，冲突是不可避免的。我们用散列查找的平均查找长度来衡量它的查找性能。平均查找长度与某些因素密切相关。 ### 散列函数的均匀性 散列函数的好坏直接影响着出现冲突的频繁程度。对同一组随机的关键字，不同的散列函数产生冲突的可能性是相同的（因为随机），因此可以不考虑它对平均查找长度的影响。 ### 处理冲突的方法 相同的关键字、相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测法处理冲突可能会产生聚集，显然就没有平方探测法好，而链接法处理冲突不会产生任何聚集，因此具有更佳的平均查找性能。 ### 散列表的平均查找长度 散列表的查找性能可以用**平均查找长度**(Average Search Length, ASL)度量。平均查找长度的计算非常简单，只需将查找每个元素的比较次数相加，并除以元素总数即可。 例如，假设某使用开链法的散列表共有5个元素，其中某个槽有三个元素、另外有两个槽分别有一个元素，则ASL的计算过程如下： $$ASL = {(1 + 2 + 3 + 1 + 1) \over 5} = 1.6$$ ### 散列表的装填因子 装填因子标志着散列表的装满的程度。当填入表中的记录越多，装填因子就越大，发生冲突的可能性就越大。散列表的平均查找长度取决于装填因子，而不是记录的个数。 不管记录个数有多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内，此时散列表查找操作的时间复杂度就真的是$O(1)$了。为了做到这一点，往往将散列表的空间设置得比查找集合大。这又是时空权衡的一个例子了，虽然是浪费了一定空间，但却换来了查找效率的大大提升。 ## References - MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010. - ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013. 赏 Wechat Pay Alipay 版本控制与代码托管仓库 基数排序(Radix sort)
