哈希表冲突处理方法浅析
来源:用户上传
作者:
【摘 要】哈希表的理想情况是无需比较一次存取便能找到所查的记录，但是在实际应用中，哈希表通常存在冲突的情况，这就需要反复查找处理冲突。各种处理冲突的方法都有其适用范围及优缺点，需要根据实际情况灵活的选择适当的冲突处理方法。
【关键词】哈希表；冲突；处理方法
0 引言
在哈希表中，哈希函数的设置是非常灵活的，只要能使任一关键字由此所得的哈希地址都分布在哈希表允许的范围内就可以了。因此常常会出现不同的关键字值对应到同一个存储地址的现象，这就叫冲突。即关键字key1≠key2，但H（key1）= H（key2）。
适当的选择分布均匀的哈希函数能有效地减少冲突的发生，但是不能不免冲突。发生冲突后，必须解决，也即必须寻找下一个可用的地址。因此哈希表的建立通常为如下步骤：第一步，取出一个数据元素的关键字key，根据哈希函数计算其在哈希表中的存储地址D，若地址为D的存储空间还没有被占用，则将该数据元素存入，否则发生冲突，执行下一步；第二步，根据规定的冲突处理方法，计算关键字为key的数据元素的下一个存储地址，若该地址的存储空间没有被占用，则存入，否则继续执行第二步，直到找出一个空闲的存储空间为止。由此可见，如何处理冲突是哈希表不可缺少的部分。
1 开放定址法
这是应用最为广泛的一种冲突处理方法。其公式描述为：Hi=（H（key）+di） MOD L i=1，2，…，k（k<=L-1）
其中：H（key）为哈希函数，L为哈希表的表长，di为增量序列。
根据增量序列取值方法的有三种：（1）线性探测再散列di=1，2，3，…，m-1；（2）二次探测再散列di=12，-12，22，-22，32，...，k2，（k<=L/2）；（3）伪随机探测再散列di=伪随机数序列。
用线性探测再散列处理冲突可以保证做到，只要哈希表未满，总能找到不发生冲突的地址，但是容易发生二次聚集的情况，即在处理同义词的冲突过程中又添加了非同义词的冲突，效率不高。比如当哈希表中k，k+1，k+2位置上已存放有数据时，下一个哈希地址为k，k+1，k+2和k+3的数据都将填入k+3的位置，这样原本不冲突的哈希地址在经过冲突处理后，反而发生冲突，这种现象对查找不利。
二次探测再散列能够减少二次聚集的情况，提高效率，但是只能在哈希表的长度为4n+3（n为整数）的素数时才能使用。随机探测再散列，则取决于伪随机数序列。
2 再哈希法
Hi=RHi（key） i=1，2，...，k
RHi均是不同的哈希函数，在同义词发生地址冲突时用另一个哈希函数产生新的地址，直到不再发生冲突为止。再哈希法不易产生二次聚集，但是增加了计算的时间和哈希函数的数量，而且不能保证在哈希表未满时，总能找到不发生冲突的地址。
除了对同一关键字用不同的哈希函数进行再哈希外，还可以用同一哈希函数对次要关键字进行计算得到新的哈希地址。即：Hi=RH（keyi） i=1，2，...，k。
比如对中文词典的进行哈希查找，关键字为一个四字成语，可以把成语的第一个字当做关键字key1，计算出哈希地址，若发生冲突，则把第二个字当做key2，计算新的哈希地址，以次类推，还可以计算key3和key4。
3 链地址法
将所有关键字为同义词的记录存储在同一个线性链表中。可以在哈希函数产生的哈希地址区间上设计一个指针数组，其每个元素的初始状态都是空指针，作为一个单链表的头指针。凡是哈希地址为i的记录都插入到第i个单链表中。在单链表中的插入位置可以在表头或表尾，也可以按一定的顺序插入到单链表的中间，以保持同义词在同一线性链表中按关键字有序。采用链地址法能用有限的哈希地址存放任意多的记录，但是增加了单链表的查找操作。
4 建立一个公共溢出区
建立一个基本表，基本表的大小等于哈希地址的个数，另外再建立一个溢出表。所有哈希地址的第一个记录存放在基本表中，其他关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都存放在溢出表中。
建立基本表需要事先能够知道哈希地址可能的个数，而溢出表中的数据则不能太多，不然难以高效地查找溢出表。也就是说，所有需要存放的记录的关键字，不能有太多的冲突。
5 结束语
在哈希表上进行查找的过程和哈希造表的过程基本一致。对于给定关键字，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则说明该哈希表中无此数据，查找结束。若有记录，就比较关键字，若相等，则查找成功；若不相等，则根据造表时设定的冲突处理方法查找下一个地址。因此要提高查找的效率，就要尽量减少发生冲突的情况。
由于哈希表查找的复杂度只与哈希表的装填充因子有关，随着硬件技术的不断发展，内存容量不断提高，可以通过简单的降低哈希表填充因子，增大哈希表的长度来降低系统复杂度，减少冲突发生的概率。
【参考文献】
[1]张科.多次Hash快速分词算法[J].计算机工程与设计，2007（4）.
[2]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2007.
[3]李志敏，郑世慧，杨义先.可用于哈希函数的安全迭代结构[J].北京邮电大学学报，2008（12）.
[责任编辑：曹明明]
转载注明来源:https://www.xzbu.com/8/view-12718927.htm
