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

HashMap扩容和Redis中Dict 扩容

news 文章来源：https://blog.csdn.net/qq_46274595/article/details/132059772 2025/5/4 15:41:06

扩容时机：

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

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