hash冲突的2种解决方法

一般情况下,哈希算法的查询效率可以达到常数级别,哈希表成为直接寻址的有效替代方案。然而由于关键字的取值可能在一个很大的范围,数据在通过哈希函数进行映射的时候,很难找到一个哈希函数,使得这些关键字不能映射到唯一的值,就会出现多个关键字映射到同一个值的现象,这种现象我们称为冲突。

这就对哈希函数的设计提出了更高的要求,如果哈希函数设计得不好,查询效率可能会降低为顺序查找的效率。找到绝对完美的、没有任何冲突的哈希算法也是较困难的。对于特定的数据集而言,好的哈希算法也是少之又少,因此如果想高效地解决哈希冲突,降低解决哈希冲突时的查询时间也是一个需要重点考虑的方面。

在使用哈希算法时,第一步是用哈希函数将关键字转化为数组的一个索引。理想情况下,不同的关键字都能转化为不同的哈希值。当然,这只是理想情况,所以我们需要面对两个或多个关键字都会映射到相同的哈希值的情况。因此,哈希算法的第二步就是一个处理冲突的过程。

解决哈希冲突的方法有很多种,如开放定址法、链地址法、二次再散列法、线性探测再散列等方法。

开放定址法

所谓开放定址法,就是当一个关键字插入到哈希表中遇到冲突时,可以连续地检查哈希表的各个位置,直到找到一个空位置把数据插入进去为止。

接下来,我们介绍 3 种开放定址法:线性探查法、二次探查法、双重散列法。

1) 线性探查法

线性探查法的思想非常简单,对每一个关键字 x,通过哈希函数得到的哈希值为 key,那么当发生冲突时,依次查看 key+1,key+2,直到 key+m-1,然后循环到哈希表的第 0 位,第 1 位,……,直到查询到某一个位置为空,把关键字存储到该位置即可,公式为:

h(key, i)=(key+i)%m, 0≤i≤m-1


例如,有一组数据 3、11、8、6、15、1 需要存储,哈希函数为 h(x)=x%7。关键字 8、15 和 1 的哈希值都为 1,当把 15 放到哈希表中时,由于 8 已经存放到下标为 1 的位置,因而发生冲突。采用线性探查法把 15 放到 key+1 的位置,即放到下标 2 的位置。

关键字 1 也会发生冲突,采用线性探查法把 1 放到 key+1、key+2、key+3 的位置都不行,直到 key+4 的位置为空才可以。

那么利用哈希函数存储的数据如图 1 所示,注意数组下标从 0 开始。
哈希函数示例(1)
图 1:哈希函数示例

线性探查法相对比较容易实现,只需要顺着哈希表的顺序查找即可。但是,线性探查法也存在一个问题,随着数据存储的越来越多,数据很容易聚集起来,那么平均查找时间也会随着不断增加。

2) 二次探查法

二次探查法的公式为:

h (key,i)=(key+i⋅i)%m


二次探查法和线性探查法类似,改变的只是每次探查的偏移量,以 i 的二次方的方式进行变化。探查时从地址 key 开始,首先探查 key,然后依次探查 key+1,key+4,key+9,……,直到探查到有空余的位置为止。

例如,还是这组数据 3、11、8、6、15、1 需要存储,哈希函数为 h(x)=x%7。在解决关键字 15 的冲突时,采用二次探查法计算出下一个位置为 key+1,15 则被放到下标 2 位置。解决关键字 1 的冲突时,由于 key+1 的位置已经存放 15,下一次探查为 key+4,这个位置为空,因此把关键字 1 放到下标为 5 的位置。

3) 双重散列法

双重散列法的公式为:

h(x,i)=(h 1(x)+i⋅h2(x))%m


双重散列法更进一步,需要两个哈希函数 h1 和 h2,首先探查 h1(x) 的位置,然后在此位置的基础上加上一些偏移量 i · h2(x),最后再对 m 取余。和之前的方法不同的地方在于两个哈希函数都依赖于关键字 x,因此不同的关键字会有不同的偏移量。

在实际应用中,h2(x) 的值要与表的大小 m 互质,才会使得得出的哈希值均匀地分布在哈希表中。

链地址法

链地址法处理冲突的方法本质上是一种数组加链表的处理方法。当发生多个数据通过哈希函数映射后得到相同的哈希值时,通常把具有相同哈希地址的关键字放在同一个链表中,该链表称为同义词链表或桶。

当把相同哈希地址的关键字数据都放在同一个链表中时,有 N 个哈希地址就有 N 个链表。同时,用数组 Hash[0..N-1] 存放每个链表的头指针,之后把哈希地址为i的数据全部以节点的方式插入对应的链表里,如图 2 所示。
链地址法处理冲突
图 2:链地址法处理冲突

链地址法存储数据的过程是这样的,首先建立一个数组存储所有链表的头指针,由数据的关键字 key 通过对应的哈希函数计算出哈希地址,找到相应的桶号,之后建立新的节点存储该数据,并把节点放到桶内链表的最后面或者最前面。

和存储数据的方法类似,查找数据的时候,也是由数据的关键字通过哈希函数计算关键字对应的哈希地址,之后顺序比较桶的内部节点是否与所查找的关键字一样,直到找到数据为止。如果全部节点都不和关键字一样,则说明哈希表里没有该数据。这个解决冲突的方法对哈希函数的要求很高,如果哈希函数选得不太好的话,哈希表的查找效率会退化为链表的查找,也就是顺序查找。

用链地址法构造的散列表,插入和删除节点操作易于实现,所以构造链表的时间开销很低,但是指针需要开辟额外的地址空间,当数据量很大时,会扩大哈希表规模,内存空间需求较大。

从上面的分析可以看到,构造优秀的哈希函数和选择解决冲突的方法是哈希查找算法的关键。不管多么高明的算法都不可能避免冲突问题,但是构建计算简单、高效快速,并且能够将关键字集合均匀地分布在地址集中,使得冲突达到最小的哈希算法,一直是计算机科学家追求的目标。