当前位置: 首页 > news >正文

HashMap扩容和Redis中Dict 扩容

扩容时机:

Hash Map:要在某个临界点进行扩容处理,该临界点就是HashMap中元素的数量在数值上等于threshold(table数组长度*加载因子)

Dict:

 当每次新增键值对的时 , 会检测 负载因子(LoadFactor) , 判断以下两种条件会触发扩容 :

  • LoadFactor >= 1 , 并且 Redis 没有进行持久化
  • LoadFactor > 5

HashMap扩容的优化:

1.先插入再扩容 

调用put不一定是新增数据,还可能是覆盖掉原来的数据,这里就存在一个key的比较问题。以先扩容为例,先比较是否是新增的数据,再判断增加数据后是否要扩容,这样比较会浪费时间,而先插入后扩容,就有可能在中途直接通过return返回了(本次put是覆盖操作,size不变不需要扩容),这样可以提高效率的。

2.链表转红黑树

3.插入改成尾插,避免扩容后死链问题

4.扩容的两点核心优化

1.(e.hash & oldCap)== 0时就放入lo链表( low 插入到 新数组中 当前数组下标的位置),否则就是hi链表( low 插入到 新数组中 当前数组下标的位置);

2。j + oldCap就是键值对在新的table数组中的位置

扩充HashMap的时候,不需要像JDK1.7的实现那样重新hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,这个设计确实非常的巧妙,既省去了重新hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了,这一块就是JDK1.8新增的优化点。
 

Dict

1.扩容:

Dict中的 table 是数组与单向链表 的结构 , 当集合的元素较多时 , 必然会导致哈希冲突 , 和链表过长问题 , 甚至会影响效率 因此 Dict内置了 自动扩容机制 , 当每次新增键值对的时 , 会检测 负载因子(LoadFactor) , 判断以下两种条件会触发扩容 :

2.收缩:

Dict还有收缩机制 , 正是和扩容机制相反 . 每当删除元素的时候 , 会检测 负载因子(LoadFactor)

触发条件 : LoadFactor < 0.1

3.rehash:(渐进式迁移)

rehash是dict的一种重建哈希表的机制(扩容/收缩 新Hash) . 当dict 的 size发生变化 , 都会检测 扩容/收缩 条件 , 为此要 将 原Hash 中的所有键值对重新插入到 新Hash 中 , 这个过程叫做 rehash

  1. 计算 新Hash 的大小 , 取决于当前 扩容/收缩
    • 扩容 : 新size >= 原Hash元素总数+1 的 2^n
    • 收缩 : 新size >= 原Hash元素总数 的 2^n (不得小于4)
  2. 新Hash 申请内存空间 , 创建dictht , 并赋值给dict.ht[1]
  3. 设置 dict.rehashidx = 0 , 标示 开始rehash (可以理解成数组的索引)
  4. 每次新增,查询,修改,删除,检查 dict.rehashidx > -1 , 如果是则将 dict.ht[0].table[rehashidx]的 键值对 插入 dict.ht[1] , 并且 rehash++ , 直到 dict.ht[0] 所有数据都插入完 (插入时 会重新分配 hash值)
  5. 插入完后 , 给dict.ht[1]初始化为空哈希表 , 释放原来的dict.ht[0]的内存
  6. 将 dict.rehashidx = -1 , 标示 结束rehash 

http://www.lryc.cn/news/105771.html

相关文章:

  • 【Redis】内存数据库Redis进阶(Redis持久化)
  • 在PHP8中检测数据类型-PHP8知识详解
  • ​​​amoeba实现MySQL读写分离
  • angr学习-入门篇
  • 基于java SpringBoot和HTML的博客系统
  • 动态sql以及常用的标签
  • DID以及社交网络中的ZKP
  • 基于SWAT-MODFLOW地表水与地下水耦合
  • 2023拒绝内卷!两年转行网络安全真实看法!
  • 【SA8295P 源码分析】57 - libDSI_MAX96789_0.so驱动库 之 QDI_Panel_Init 显示屏初始化函数 代码分析
  • IDEA偶尔编译的时候不识别lombok
  • rust学习-构建服务器
  • Java并发----进程、线程、并行、并发
  • 【计算机网络】第 4 课 - 物理层
  • 深入理解MVVM架构模式
  • 配置IPv6 over IPv4手动隧道示例
  • Vue3--->组合式API与Pinia
  • 三言两语说透柯里化和反柯里化
  • 细讲TCP三次握手四次挥手(四)
  • HarmonyOS/OpenHarmony元服务开发-配置卡片的配置文件
  • mac安装nacos,M1芯片
  • 老板说把跳针改过去,什么是主板跳针
  • PyTorch代码实战入门
  • TSINGSEE青犀视频汇聚平台EasyCVR多种视频流播放协议介绍
  • Vivado进行自定义IP封装
  • 开放自动化软件的硬件平台
  • AdvancedInstaller打包程序
  • 无穷限积分习题
  • AI 3D结构光技术加持,小米引领智能门锁新标准
  • 管理类联考——逻辑——形式逻辑——汇总篇