基于哈希表查找方法的优势及其算法的改进

摘要：当前是一个信息爆炸的时代，海量的信息充斥了人们生活的各个方面，所以从大量的数据中快速的找到所需信息已经成为一个热门的课题。一般的搜索方法，在搜索时需进行关键字的比较。这一类建立在比较的基础上的搜索方法，其效率依赖于搜索过程中所进行的比较次数。而通过使用哈希表人们可以不经任何比较，一次存取便能得到所需的信息，从而大大提高了搜索的效率。然而，建立哈希表不可能没有冲突，解决冲突则会产生诸如堆积、二次聚集等现象，降低了查找效率。文中通过举例阐明了该过程，并提出了有效的解决方法。

关键词:哈希表冲突查找关键字

1 一般查找方法和哈希表的比较

最容易理解的莫过于按照顺序查找，它的查找过程为:

从表中的第一个记录开始，逐条地进行记录的关键字和给定值的比较，这时可能会发生两种情况，第一种情况是找到关键字和给定值相等的记录，查找成功，第二种情况是找遍所有记录却没有找到满足条件的记录，查找失败。当表中存储的数据量非常多的时候，该方法效率就会变得很低，最糟糕的情况就是可能要把所有的数据都读一遍才找到指定记录。由此可见顺序查找方法效率不高。而其他查找方法如折半查找法，也称为二分查找法，它充分利用了元素间的次序关系，它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事，甚至Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。其问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定。

综上所述，查找的效率依赖于查找过程中所进行的比较次数。比较的次数越多，查找时间就越长。理想的情况是希望不经任何比较，一次存取便能得到所查找的记录。而这个理想的情况可以用哈希表和它的算法来实现。

2 哈希表的概念

哈希表（Hash table，也叫散列表），是根据关键码值而直接进行访问的数据结构。它是通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。哈希表的最大特点，就是数据存储位置和数据记录的内容相关，存在着一个函数换算关系：

Offset=Hash (K)

其中，Offset为数据存储的偏移量，Hash（K）为哈希函数(Hash Function)，K为关键字，若表中存在关键字和K相等的记录，则必定在Hash(K)的存储位置上。哈希函数，是计算机科学中一个重要的课题。其实，哈希概念并没有一个严格的定义。一般说来，哈希函数满足以下的条件：

①对输入值运算，得到一个固定长度的摘要(Hash value)；

②散列函数的输出值尽量接近均匀分布；

③k的微小变化可以使Hash(k)发生非常大的变化，即所谓“雪崩效应”；

原来，这是为了减少“哈希冲突”（Hash collision），也就是两个不同输入产生了相同输出值的情况。根据抽屉原理，Hash算法不可能没有冲突(collision)，但是，由于冲突会造成一些问题，可能会影响到应用Hash函数的某些算法的效率，所以，我们需要尽量避免之。这样，对Hash算法的选择，就是很重要的了。

3 除留余数法建立哈希表

构造哈希函数的目标是使哈希地址尽可能均匀地分布在连续的内存单元地址上，以减少冲突发生的可能性，同时使计算尽可能简单以达到尽可能高的时间效率。根据关键字的结构和分布不同，可构造出与之适应的各不相同的哈希函数。

除留余数法是采用取模运算（MOD），把关键字除以某个不大于哈希表表长的整数得到的余数作为哈希地址。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。哈希函数的形式为：

Hash(k)=k MOD p(p≤m，m为哈希表表长)

而除留余数法的关键就是选好p，一般p取素数或m。若p选的不好，容易产生同义词，即发生冲突。冲突会造成一些问题，可能会影响到应用Hash函数的某些算法的效率，所以好的p值可以使得记录集合中的每个关键字通过该数转换后映射到哈希表范围内任意地址上的概率相等，从而尽可能减少发生冲突的可能性。但是，根据抽屉原理，Hash算法不可能没有冲突。

冲突解决技术可分为两大类：开散列法（又称为链地址法）和闭散列法（又称为开放地址法）。哈希表是用数组实现的一片连续的地址空间，两种冲突解决技术的区别在于发生冲突的元素是存储在这片数组的空间之外还是空间之内。

下面以闭散列法中的线性探测法为例说明，线性探测法的基本思想是：当发生冲突时，从冲突位置的下一个单元顺序寻找，只要找到一个空位，就把元素放入此空位中。可用如下公式表示：

Hi=(Hash(k) + i)MODm 公式(1)

其中Hash(k)为哈希函数；m为哈希表长；i为增量。

一组关键字为（12，19，23，28，39，51，56，76，84），哈希表长m=13，哈希函数为：Hash(k)=k MOD11，并使用线性探测法处理冲突，可得表如下：

根据除留余数法的计算规则，12，19，28，76这4个关键字是直接添加到第1，8，6，10这4个位置，而其他的关键字则都要经过线性探测法才能确定其填充的位置，例如关键字39，由哈希函数Hask（39）=39 MOD 11=6，可知，39应该填充到位置6，可是位置6已经被关键字19占据，所以必须进行再次计算。根据公式(1)，

H1=(Hash(39)+1) MOD 13=7，即关键字39对应位置为7，但是，这样就出现一个问题，根据哈希函数计算，Hask（51）=51 MOD 11=7，可以看出根据除留余数法规则，原本属于关键字51的位置7却被关键字39占据了，这就导致57也必须进行线性探测法寻找自己的位置：

H1=(Hash(51)+1) MOD 13=8 （冲突，位置8已被关键字19占据）

H2=(Hash(51)+2) MOD 13=9 （成功，位置9为空，关键字51填充到位置9）

每个元素经哈希函数计算出来的地址称为基地址，这种不同基地址的元素争夺同一个单元的现象叫做二次聚集。二次聚集实际上是在处理同义词之间的冲突时引发的非同义词的冲突。显然，这种现象对查找不利。线性探测很容易出现二次聚集，小的聚集能汇合成大的聚集，最终导致很长的探测序列，从而降低哈希表的运算效率。

4 改进的除留余数法建立哈希表

使用哈希表的主要目的是为了加快查找速度，提高查找效率，任何导致查找速度和效率降低的问题都是我们尽力去解决的。由上面的论述可知二次聚集的产生，是由在建立哈希表时采取了遇到冲突立刻解决的方法引起的。我们针对这一特点，可以采用以下的策略:在建立哈希表时先依次填入所有不产生冲突的元素，在填入的过程中，将遇到冲突的元素暂时放入一临时表中，并且记下它发生冲突位置，等全部数据处理完后，再去专门解决产生冲突元素(暂存入队列中的元素) 。

例如，一组关键字为（12，19，23，28，39，51，56，76，84），哈希表长m=13，哈希函数为：Hash(k)=k MOD 11。下面分析一下它的存储过程:Hash(12)=1，位置1为空，将12存入；Hash(19)=8，位置8为空，将19存入；Hash(23)= 1，位置1不为空，将23存入临时表；Hash(28)=6，位置6为空，将28存入；Hash(39)=6，位置6不为空，将39存入临时表；Hash(51)=7，位置7为空，将51存入；Hash( 56)=1，位置1不为空，将56入临时表；Hash(76)=10，位置10为空，将76存入；Hash(84)=7，位置7不为空，将84入临时队列。这时建表如下:

队列中的每个元素包括两项：数据元素和其产生冲突的位置。要解决冲突元素问题，将临时表中的元素填入哈希表，处理过程为:

取队列中第一个哈希地址上冲突的数据元素得Hash(23)=1，寻找下一个空的哈希地址:

H1=(Hash(23)+1) mod11=2地址2为空，将23存入。取队列中第二个哈希地址上冲突的数据元素得Hash(39)=6，寻找下一个空的哈希地址:

H1=(Hash(39)+1) mod11=7位置7不为空

H2=(Hash(39)+2) mod11=8位置8不为空

H3=(Hash(39)+3) mod11=9位置9为空，将39存入。取队列中第三个哈希地址上冲突的数据元素得Hash(56)=1，寻找下一个空的哈希地址:

H1=(Hash(56)+1) mod11=2位置2不为空

H2=(Hash(56)+2) mod11=3位置3为空，将56存入。

取队列中第三个哈希地址上冲突的数据元素得Hash(84)=7，寻找下一个空的哈希地址:

H1=(Hash(84)+1) mod11=7位置7不为空

H2=(Hash(84)+2) mod11=8位置8不为空

H3=(Hash(84)+3) mod11=9位置9不为空

H4=(Hash(84)+4) mod11=10位置10不为空

H1=(Hash(84)+5) mod11=11位置11为空，将84存入

最终结果如下:

5 结论

改进方法之后，避免了非同义词抢占同一个位置，不会再带来新的冲突，所以能有效的减少冲突次数，从而大大的提高了查找效率。而且，改进方法之后，在读取数据时不需面对非同义词的冲突，所以绝大部分数据不需要进行比较便可直接获得查找结果，这就更符合使用哈希表的初衷。

参考文献:

[1]严蔚敏，吴伟民.数据结构（C语言版）[M].4版.北京:清华大学出版社，2007.

[2]Weiss M A.数据结构与算法分析[M].北京:机械工业出版社，2004.

[3]王川，王岁花.地址哈希排序算法的设计与实现[J].平原大学学报，2004，21(5):61-63.