搞定算法与数据结构(05):散列表的冲突解决方案与复杂度分析

作者: 王炳明 分类: 算法与数据结构 发布时间: 2021-10-04 10:48 热度:1,300

查看完整目录 –>《搞定算法与数据结构


散列思想

散列思想的基础,有两个内容:

  1. 散列函数:通过 key 快速找到存储该 key 对应值的插槽位置,这个位置可以是一个数组的索引下标值
  2. 数组索引:数组是真正存储所有 key 对应的 value 的数据结构,经过散列函数后得到索引下标值,就可以从数组中取得对应的 value

搞定算法与数据结构(05):散列表的冲突解决方案与复杂度分析

对于散列函数的三点要求:

  1. 散列函数计算得到的散列值是一个非负整数;
  2. 如果 key1 = key2,那 hash(key1) hash(key2);
  3. 如果 key1 ≠ key2,那 hash(key1) ≠ hash(key2)。

关于第一点,由于数组的下标是从0开始,因此散列值必须是非负整数,可以理解。

关于第二点,相同的 key,经过散列函数后得到的散列值也应该是一样的,同样可以理解。

但第三点,就需要着重说明一下,不同的 key,按理说得到的散列值应该是不一样的,但实际上,这却是很难实现的,需要一些手段来规避这个冲突的情况。

散列冲突

再好的散列函数(诸如 MD5、SHA、CRC)也无法避免散列冲突。

那么对于这种散列冲突,有什么样的解决方法吗?

第一种:开放寻址法

开放寻址法解决散列冲突的方法有三种:

  1. 线性探测
  2. 二次探测
  3. 双重散列

1. 线性探测

  • 插入时:先用散列函数得到对应的散列值,若此散列值对应数组中的位置还是空的,就把 {key:value} 放入该位置。但若此散列值对应数组中的位置不是空的,说明已经出现了散列冲突,那怎么办呢?以该散列值的索引为起点,从数组中再往下寻找,直到找到有一个空闲的位置就放入该 {key:value}
  • 查找时:先用散列函数得到对应的散列值,找到该散列值对应数组中位置的值,对应其 key 是否等于我们的查找的 key,若是则直接返回,若不是,则说明出现了散列冲突,需要按线性继续往下遍历查找,直到找到散列表中的 key 刚好等于我们查找的 key才返回。

2. 二次探测

所谓二次探测,跟线性探测很像,线性探测每次探测的步长是 1,那它探测的下标序列就是 hash(key)+0,hash(key)+1,hash(key)+2

而二次探测探测的步长就变成了原来的“二次方”,也就是说,它探测的下标序列就是 hash(key)+0,hash(key)+1^2,hash(key)+2^2

3. 双重散列

所谓双重散列,意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key),hash2(key),hash3(key)

我们先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置。

这个线性探测和二次探测的过程,在散列表中空闲位置不多的时候,散列冲突的概率就会变大,最坏的情况下,可能会遍历整个数组,性能比较差,因此开放寻址法比较少用。

第二种:链表法

链表法是一种更加常用的用于解决散列冲突的方法。

传统散列表中,一个 slot (槽)只会存储一个 key-value 对应关系,而在链表法中,会打破这种常规思路,一个 slot 可以存储多个 key-value 的对应关系,发生冲突了怎办呢?没关系,我全部存下来,并把他们串成一个链表,查找的时候,发现冲突了,不用去遍历散列表,而只要遍历该链表即可,链表的长度可要比散列表小多了,效率自然就上去了。

搞定算法与数据结构(05):散列表的冲突解决方案与复杂度分析

时间复杂度

通常我们都会认为哈希散列表,只要查询一次就能立马给出结果,时间复杂度为 O(1)。

但实际上,如果你学习上面关于散列冲突的知识,你就不会这么认为了。

若散列函数的设计出现了问题或者装载因子过大,导致了大量的散列冲突,散列表就会退化成链表,查找的时间复杂度就会变成 O(n)。

文章有帮助,请作者喝杯咖啡?

发表评论