云服务器 部署网站,wordpress如何配置伪静态页面,网络营销的新特点,h5网站开发 源码平日里面经常使用map这种数据结构#xff0c;令人称奇的是他的访问速度为什么那么快#xff1f;为什么可以通过key以接近O(1)的速度查找#xff1f; 一、基础数据结构特点分析
1.1数组
查找的时间复杂度为O(1)
插入时间复杂度为O(n)
1.2链表
查找的时间复杂度为O(n)
插…平日里面经常使用map这种数据结构令人称奇的是他的访问速度为什么那么快为什么可以通过key以接近O(1)的速度查找 一、基础数据结构特点分析
1.1数组
查找的时间复杂度为O(1)
插入时间复杂度为O(n)
1.2链表
查找的时间复杂度为O(n)
插入时间复杂度为O(1)
1.3红黑树
一种平衡树能以较低的时间复杂度进行搜索、添加和查找操作Ologn
可以优化节点查找速度
所以如果我们能找到一种通过数组进行范围筛选通过链表对数据进行增删的数据结构来存储数据那么就能够获得较快的查询速率
二、hashMap基本实现原理
2.1hash过程
将这个数据节点进行hasCode操作获取一个hash值
2.2hash定位
hash值对数组长度取模获取一个模值相同模值的数据节点挂载在同一个链表上
2.3查找
获取数据的时候就将该key转成hash计算其模值在对应的链表上面进行顺序查找
2.4hash冲突过多的优化
什么是hash冲突不同的key算出了相同的hash
解决方案1Java采用——链地址法相同的hash值转到一个链表链表长度大于8转换成红黑树红黑树规模小于6退化成链表
特点
1要减少hash冲突需要很大的散列利用率不够大
2默认大小为16超过就扩充一倍
解决方案2Python采用——开放寻址法算出了相同的hash值就继续往下遍历寻找第一个找到的空hash值
特点
1适用于负载不大的散列负载过大会长时间找不到空hash
2负载超过一定阙值就扩容而不是满了再扩容
