当前位置: 代码网 > it编程>编程语言>C/C++ > 【哈希表】为什么哈希表的插入/删除/查找时间复杂度为O(1)

【哈希表】为什么哈希表的插入/删除/查找时间复杂度为O(1)

2024年08月01日 C/C++ 我要评论
线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: = ( + )% m, 或者:= ( - )% m。, 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

✍1.先说结论

在使用哈希表时,往往会出现哈希冲突,此时就会通过链表/红黑树的方法来解决冲突,此时引入链表/红黑树那么时间复杂度就不是严格的o(1)。
我们首先要明白n代表什么,n是指问题的规模大小。
在使用哈希表时,所有的数据个数为n,链表的长度肯定不是n,(因为存在着很多链表,理论上时存在着所有的数据都在一个链表上,但在实际的开发中,是不会出现的),此外,在哈希表的插入中,当负载因子过大时,哈希表会进行扩容,数据会重新哈希,重新分配到链表上,确保每个链表上的元素不会过多,就近似会认为是o(1)了。

✍2.哈希表的概念

当向该结构中:

  • 插入元素
    根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
  • 搜索元素
    对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。
    该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(hashtable)(或者称散列表)

✍3.哈希冲突

了解哈希表中数据发生冲突时的处理方法,也就是了解哈希表的底层原理。

3.1闭散列

闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。

  • 通过哈希函数获取待插入元素在哈希表中的位置
  • 如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素
  • 采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
    在这里插入图片描述

二次探测

线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: = ( + )% m, 或者:= ( - )% m。其中:i = 1,2,3…, 是通过散列函数hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。 对于2.1中如果要插入44,产生冲突,使用解决后的情况为:
在这里插入图片描述

3.2开散列/哈希桶

开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
在这里插入图片描述

  1. 每个桶的背后是另一个哈希表
  2. 每个桶的背后是一棵搜索树

以上就是本文所有内容,如果对你有帮助的话,点赞收藏支持一下吧!

(0)

相关文章:

版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2386932994@qq.com 举报,一经查实将立刻删除。

发表评论

验证码:
Copyright © 2017-2025  代码网 保留所有权利. 粤ICP备2024248653号
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com