旅游小网站怎样做精不做全,项目管理平台系统,电脑培训网上培训班,wordpress版权图片文章目录 JDK7 vs JDK8 的 HashMap 结构变化Java8 中哈希表的红黑树优化机制HashMap 添加元素的完整流程解析1. 计算 key 的哈希值并确定索引2. 检查该索引位置是否已有元素3. 处理哈希冲突4. 判断当前存储结构#xff08;链表还是红黑树#xff09;5. 判断链表长度是否超过 … 文章目录 JDK7 vs JDK8 的 HashMap 结构变化Java8 中哈希表的红黑树优化机制HashMap 添加元素的完整流程解析1. 计算 key 的哈希值并确定索引2. 检查该索引位置是否已有元素3. 处理哈希冲突4. 判断当前存储结构链表还是红黑树5. 判断链表长度是否超过 86. 触发扩容的判断7. 进行扩容8. 迁移元素 流程图补充HashMap 的初始容量与负载因子优化 JDK7 vs JDK8 的 HashMap 结构变化
在 JDK7 及更早版本HashMap 采用 数组 链表 结构当哈希冲突较多时链表可能变得很长导致查询性能从 O(1) 退化到 O(n)。
在 JDK8为了优化链表查询性能引入了红黑树
仍然采用 数组 作为底层存储。当某个桶中的链表长度 超过 8并且 table 的大小 ≥ 64 时链表转换为 红黑树。这样在极端情况下查询性能从 O(n) 降低到O(log n)。
Java8 中哈希表的红黑树优化机制
从JDK8开始为了优化哈希冲突情况下的查找性能当哈希桶中的链表长度超过 8 时链表会转换为红黑树。红黑树是一种自平衡二叉搜索树将最坏情况下的查找复杂度从 O(n) 降低到 O(log n)。如果没引入红黑树则最坏查找复杂度是O(n)
当树中元素数量低于 6 时红黑树会退化回链表以减少不必要的树操作开销提高小规模数据场景下的性能。
HashMap 添加元素的完整流程解析
1. 计算 key 的哈希值并确定索引
通过 key.hashCode() 计算出哈希值。采用 (哈希值 (table.length - 1)) 计算索引以确定 key 应该存放在 table 数组中的那个位置。 2. 检查该索引位置是否已有元素
如果该索引位置为空table[index] null说明当前 key 没有发生哈希冲突直接存入该位置并检查是否需要扩容。【在 HashMap 里负载因子loadFactor默认值是 0.75表示当元素个数达到 容量 * 0.75 时就会触发扩容】如果该索引位置已有元素说明发生了哈希冲突进入下一步处理。 3. 处理哈希冲突
在索引位置已有元素的情况下需要判断该 key 是否已经存在
如果 key 与已有节点的 key 相同说明是更新操作直接替换 value。如果 key 不同说明该索引位置是个链表或红黑树需要进一步处理。 4. 判断当前存储结构链表还是红黑树
如果该索引处存储的是红黑树按照红黑树的插入规则执行插入操作流程结束。如果是链表则遍历链表 如果链表中存在相同的 key则更新 value流程结束。如果链表中没有相同 key则在链表末尾插入新节点并继续下一步处理。 5. 判断链表长度是否超过 8
如果链表长度 ≤ 8不做额外处理。如果链表长度 8则需要判断是否转换为红黑树 如果 table 长度 64则将链表转换为红黑树流程结束。如果 table 长度 64则不转换为红黑树而是触发扩容见步骤 7。 6. 触发扩容的判断
在完成插入后需要判断是否需要扩容
size 阈值threshold table.length * 0.75 时触发扩容。扩容是基于整个 HashMap 的大小而不是单个链表的长度即使单个链表过长也不会单独扩容而是考虑整体 size。 7. 进行扩容
扩容策略table 容量翻倍如 16 → 3232 → 64。调整扩容阈值新阈值 新容量 * 0.75。重新计算 key 的索引 由于 table.length 发生变化所有 key 需要重新计算索引并迁移到新的 table。HashMap 采用高位 低位拆分的方式优化了 rehash 过程使得某些 key 的新索引保持不变而另一些 key 需要移动到新位置。 8. 迁移元素
旧 table 的数据逐个迁移到新 table。迁移规则 计算 oldIndex hash (oldCapacity - 1)newIndex hash (newCapacity - 1)。低位不变高位索引变化减少数据迁移的计算量。
流程图 补充
HashMap 的初始容量与负载因子优化
HashMap 的默认初始容量为 16负载因子为 0.75这一组合在性能与空间之间取得了平衡。较高的负载因子如 1.0可减少空间浪费但会增加哈希冲突的概率较低的负载因子则减少哈希冲突但会增加内存开销。 如果可预估 HashMap 的存储需求建议提前设置合适的初始容量以减少动态扩容带来的性能损耗。
❤觉得有用的可以留个关注~~❤
