哈尔滨市第三中学 刘翀

　　
　　下文提到的所有程序都能在附录中找到。

3. 效率对比

　　3.1简单的例子与实验

　　　下面是一个比较简单的例子：

　　　　　　　　　　　　　集合 ( Subset )

问题描述：

　　给定两个集合A、B，集合内的任一元素x满足1 ≤ x ≤ ，并且每个集合的元素个数不大于 个。我们希望求出A、B之间的关系。只需确定在B 中但是不在 A 中的元素的个数即可。（这个题目是根据 OIBH NOIP 2002 模拟赛 # 1 的第一题改编的。）

　　分析：我们先不管A 与 B 的具体关系如何，注意到这个问题的本质就是对于给定的集合A ，确定B 中的元素是否在 A 中。所以，我们使用哈希表来处理。至于哈希函数，只要按照除余法就行了，由于故意扩大了原题的数据规模， H(x) = x mod 15889;

　　当然本题可以利用别的方法解决，所以选取了速度最快的快速排序+二分查找，让这两种方法作效率对比。

　　我们假定 |A|=|B| ，对于随机生成的数据，计算程序重复运行50次所用时间。

　　对比表格如下：

　　对于数据的说明：在 Celeron566 下用 TP 测试，为了使时间的差距明显，让程序重复运了行50次。同时哈希表中的P= 15889 ，下标范围 0..15888 。由于快速排序不稳定，因此使用了随机数据。

　　3．2 对试验结果的分析：

　　注意到两个程序的用时并不像我们期望的那样，总是哈希表快。设哈希表的大小为 P .

　　首先，当规模比较小的时候（大约为a< 10% * P，这个数据仅仅是通过若干数据估记出来的，没有严格证明，下同），第二种方法比哈希表快。这是由于，虽然每次计算哈希函数用O(1) 的时间，但是这个系数比较大。例如这道题的 H(x)=x mod 15589 ，通过与做同样次数的加法相比较，测试发现系数 > 12 ，因为 mod 运算本身与快速排序的比较大小和交换元素运算相比，比较费时间。所以规模小的时候，O(N)（忽略冲突）的算法反而不如 O(NlogN)。这一点在更复杂的哈希函数上会体现的更明显，因为更复杂的函数系数会更大。

　　其次，当规模稍大 （大约为 15%*P < a < 85%*P） 的时候，很明显哈希表的效率高。这是因为冲突的次数较少。

　　再次，当规模再大 （大约为 90%*P < a < P ）的时候，哈希表的效率大幅下降。这是因为冲突的次数大大提高了，为了解决冲突，程序不得不遍历一段都存储了元素的数组空间来寻找空位置。用白箱测试的方法统计，当规模为13500的时候，为了找空位置，线性重新散列平均做了150000 次运算；而当规模为15000 的时候，平均竟然高达2000000 次运算，某些数据甚至能达到4265833次。显然浪费这么多次运算来解决冲突是不合算的，解决这个问题可以扩大表的规模，或者使用"开散列"（尽管它是动态数据结构）。然而需要指出的是，冲突是不可避免的。

　　初步结论：

　　当数据规模接近哈希表上界或者下界的时候，哈希表完全不能够体现高效的特点，甚至还不如一般算法。但是如果规模在中央，它高效的特点可以充分体现。我们可以从图像直观的观察到这一点。

　　试验表明当元素充满哈希表的 90% 的时候，效率就已经开始明显下降。这就给了我们提示：如果确定使用哈希表，应该尽量使数组开大（由于竞赛中可利用内存越来越多，大数组通常不是问题，当然也有少数情况例外），但对最太大的数组进行操作也比较费时间，需要找到一个平衡点。通常使它的容量至少是题目最大需求的 120% ，效果比较好（这个仅仅是经验，没有严格证明）。

　　　　　　　　　　　　　　　　　　　　　　相关链接：浅谈竞赛中哈希表的应用（一）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（二）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（三）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（四）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（五）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（六）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（七）