哈希表是一种高效的数据结构。本文分五个部分：首先提出了哈希表的优点，其次介绍了它的基础操作，接着从简单的例子中作了效率对比，指出其适用范围以及特点，然后通过例子说明了如何在题目中运用哈希表以及需要注意的问题，最后总结全文。
[正文]. 引言
哈希表（ ）的应用近两年才在中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。
哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
哈希表又叫做散列表，分为\开散列\和\闭散列\。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的\哈希表\仅指\闭散列\，关于其他方面读者可参阅其他书籍。
. 基础操作 基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素\分类\，然后将这个元素存储在相应\类\所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了\冲突\，换句话说，就是把不同的元素分在了相同的\类\之中。后面我们将看到一种解决\冲突\的简便做法。
总的来说，\直接定址\与\解决冲突\是哈希表的两大特点。
1 / 12
函数构造
构造函数的常用方法（下面为了叙述简洁，设 () 表示关键字为 的元素所对应的函数值）： ) 除余法：
选择一个适当的正整数 ，令 ( )
这里， 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
) 数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。 冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 ，则当 () 已经存储了元素的时候，依次探查 (()) , …… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。 支持运算
哈希表支持的运算主要有：初始化()、哈希函数值的运算(())、插入元素()、查找元素()。
设插入的元素的关键字为 ， 为存储的数组。 初始化比较容易，例如
; 用非常大的整数代表这个位置没有存储元素 ; 表的大小
2 / 12
; ; []; ;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： (); ; ;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 (); ; (); ;
(<)([() ]<>)([() ]<>) ();
当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元 素存储的单元，要么表已经满了 () ; ; 插入元素 (); ;
3 / 12
(); 定位函数的返回值 [] []
; 即为发生了错误，当然这是可以避免的 ;
查找元素是否已经在表中 (); ; (); []
; ;
这些就是建立在哈希表上的常用基本运算。
下文提到的所有程序都能在附录中找到。
. 效率对比 简单的例子与实验
下面是一个比较简单的例子：
集合 ( ) 问题描述：
给定两个集合、，集合内的任一元素满足 ≤ ≤
，并且每个集合的元
素个数不大于 个。我们希望求出、之间的关系。只需确定在 中但是不在 中的元素的个数即可。（这个题目是根据 模拟赛 的第一题改编的。）
分析： 我们先不管 与 的具体关系如何，注意到这个问题的本质就是对于给定的集合 ，确定 中的元素是否在 中。所以，我们使用哈希表来处理。至于哈希函数，只要按照除余法就行了，由于故意扩大了原题的数据规模， () ;
当然本题可以利用别的方法解决，所以选取了速度最快的快速排序二分查
找，让这两种方法作效率对比。
我们假定 ，对于随机生成的数据，计算程序重复运行次所用时间。
4 / 12
对比表格如下：
复杂度 测试数据规模
哈希表（） 快速排序二分查找() () (只有忽略了冲突才是这个结果。当然
实际情况会比这个大，但是重复的几率与( ) ( ) 哈希函数有关，不容易估计)
对于数据的说明： 在 下用 测试，为了使时间的差距明显，让程序重复运了行次。同时哈希表中的 ，下标范围 。由于快速排序不稳定，因此使用了随机
数据。 ． 对实验结果的分析：
注意到两个程序的用时并不像我们期望的那样，总是哈希表快。设哈希表
的大小为 . 首先，当规模比较小的时候（大约为< * ，这个数据仅仅是通过若干数据估记出来的，没有严格证明，下同），第二种方法比哈希表快。这是由于，虽然每次计算哈希函数用() 的时间，但是这个系数比较大。例如这道题的 () ，通过与做同样次数的加法相比较，测试发现系数 > ，因为 运算本身与快速排序的比较大小和交换元素运算相比，比较费时间。所以规模小的时候，()（忽略冲突）的算法反而不如 ()。这一点在更复杂的哈希函数上会体现的更明显，因
为更复杂的函数系数会更大。
其次，当规模稍大 （大约为 * < < *） 的时候，很明显哈希表的效率高。
这是因为冲突的次数较少。
再次，当规模再大 （大约为 * < < ）的时候，哈希表的效率大幅下降。这是因为冲突的次数大大提高了，为了解决冲突，程序不得不遍历一段都存储了元素的数组空间来寻找空位置。用白箱测试的方法统计，当规模为的时候，为了找空位置，线性重新散列平均做了 次运算；而当规模为 的时候，平均竟然高达 次运算，某些数据甚至能达到次。显然浪费这么多次运算来解决冲突是不合算的，
5 / 12
哈希表是一种高效的数据结构。本文分五个部分首先提出
