散列冲突及解决方案

本文主要是介绍散列冲突及解决方案，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

散列冲突
对于散列表而言，无论设置的存储区域（n）有多大，当需要存储的数据大于 n 时， 那么必然会存在哈希值相同的情况。这就是所谓的散列冲突。一般解决散列冲突的方法有开放寻址法与链表法。

开放寻址法
定义：将散列函数扩展定义成探查序列，即每个关键字有一个探查序列h(k,0)、h(k,1)、…、h(k,m-1)，这个探查序列一定是0….m-1的一个排列（一定要包含散列表全部的下标，不然可能会发生虽然散列表没满，但是元素不能插入的情况），如果给定一个关键字k，首先会看h(k,0)是否为空，如果为空，则插入；如果不为空，则看h(k,1)是否为空，以此类推。

线性探测方法

向散列表中插入数据时，某个数据经过散列函数得到散列值之后，如果存储位置已经被占用，我们就从当前位置开始，依次往后查找，直到找到空闲位置。

缺点：当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，需要从头到尾探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。

二次探测方法

二次探测进行探测的步长变成了原来的“二次方”，也就是说，它探测的下标序列为 hash(key)+0，hash(key)+1^2或[hash(key)-1^2]，hash(key)+2^2或[hash(key)-2^2]。

双重散列方法

所谓双重散列，意思就是不仅要使用一个散列函数，而是使用一组散列函数 hash1(key)，hash2(key)，hash3(key)。。。。。。先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

总结：

事实上，不管采用哪种探测方法，只要当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，需要尽可能保证散列表中有一定比例的空闲槽位。

一般使用加载因子（load factor）来表示空位的多少。

加载因子是表示 Hsah 表中元素的填满的程度，若加载因子越大，则填满的元素越多,这样的好处是：空间利用率高了,但冲突的机会加大了。反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了，但空间浪费多了。

链表法
链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。如下动图所示，在散列表中，每个位置对应一条链表，所有散列值相同的元素都放到相同位置对应的链表中。
 

这篇关于散列冲突及解决方案的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！