admin管理员组

文章数量:1037775

HashMap工作原理的理解，1.7和1.8，数据结构，怎么切换红黑树和链表

一、数据结构演进
  1. JDK 1.7
    1. 数组 + 链表：底层使用 Entry 数组存储键值对，每个 Entry 包含 key、value、hash 和 next 指针。哈希冲突时，新元素以头插法加入链表头部，可能导致链表逆序甚至死循环（多线程扩容时）
    2. 哈希计算：通过多次扰动（4次位运算 + 5次异或）减少哈希冲突
  2. JDK 1.8
    1. 数组 + 链表 + 红黑树：底层改用 Node 数组，链表长度超过 8 且数组容量 ≥ 64 时，链表转为红黑树（时间复杂度从 O(n) 优化为 O(log n)）；当节点数 ≤ 6 时，红黑树退化为链表，避免频繁转换的资源浪费
    2. 哈希计算：简化扰动处理（1次位运算 + 1次异或），依赖红黑树弥补可能的哈希冲突问题
二、核心工作机制对比

<!--br {mso-data-placement:same-cell;}--> td {white-space:nowrap;border:0.5pt solid #dee0e3;font-size:10pt;font-style:normal;font-weight:normal;vertical-align:middle;word-break:normal;word-wrap:normal;}

特性

JDK 1.7

JDK 1.8

插入方式

头插法（链表逆序，扩容时可能死循环） 16 37

尾插法（避免逆序，解决死循环） 11 37

扩容触发时机

插入前扩容（可能无效扩容） 37

插入后检查扩容（减少无效扩容） 37

扩容逻辑

重新计算所有元素索引，链表元素顺序反转 16

优化索引计算（原位置或原位置+旧容量），保留顺序 37 59

线程安全性

非线程安全，多线程扩容可能导致死循环 11

仍非线程安全，但尾插法避免死循环 11 37

三、红黑树与链表的转换机制
  1. 链表转红黑树条件
    1. 链表长度 ≥ 8（阈值选择基于泊松分布，概率极低，防止用户哈希算法劣化导致性能问题 ）。
    2. 数组容量 ≥ 64（否则仅扩容，不树化）
  2. 红黑树退化为链表条件
    1. 树节点数 ≤ 6（阈值差异避免频繁转换）
  3. 转换触发时机
    1. 插入时：若链表长度达到阈值且容量足够，触发树化
    2. 删除或扩容时：检查树节点是否需退化
四、性能优化关键点
  1. 负载因子与扩容
    1. 默认负载因子 0.75，平衡空间利用率和哈希冲突概率
    2. 扩容后容量为 2倍，保证索引计算高效（hash & (length-1)）
  2. 红黑树引入的意义
    1. 极端情况下（如哈希碰撞攻击），避免链表过长导致查询性能骤降 。

总结

JDK 1.8 的 HashMap 通过红黑树优化、尾插法和扩容逻辑改进，显著提升了高并发场景下的稳定性和性能。理解其底层数据结构差异及转换机制，有助于合理设计哈希函数、优化存储结构，并避免多线程问题。实际开发中，若需线程安全，应优先选择 ConcurrentHashMap

HashMap工作原理的理解，1.7和1.8，数据结构，怎么切换红黑树和链表

一、数据结构演进
  1. JDK 1.7
    1. 数组 + 链表：底层使用 Entry 数组存储键值对，每个 Entry 包含 key、value、hash 和 next 指针。哈希冲突时，新元素以头插法加入链表头部，可能导致链表逆序甚至死循环（多线程扩容时）
    2. 哈希计算：通过多次扰动（4次位运算 + 5次异或）减少哈希冲突
  2. JDK 1.8
    1. 数组 + 链表 + 红黑树：底层改用 Node 数组，链表长度超过 8 且数组容量 ≥ 64 时，链表转为红黑树（时间复杂度从 O(n) 优化为 O(log n)）；当节点数 ≤ 6 时，红黑树退化为链表，避免频繁转换的资源浪费
    2. 哈希计算：简化扰动处理（1次位运算 + 1次异或），依赖红黑树弥补可能的哈希冲突问题
二、核心工作机制对比

<!--br {mso-data-placement:same-cell;}--> td {white-space:nowrap;border:0.5pt solid #dee0e3;font-size:10pt;font-style:normal;font-weight:normal;vertical-align:middle;word-break:normal;word-wrap:normal;}

特性

JDK 1.7

JDK 1.8

插入方式

头插法（链表逆序，扩容时可能死循环） 16 37

尾插法（避免逆序，解决死循环） 11 37

扩容触发时机

插入前扩容（可能无效扩容） 37

插入后检查扩容（减少无效扩容） 37

扩容逻辑

重新计算所有元素索引，链表元素顺序反转 16

优化索引计算（原位置或原位置+旧容量），保留顺序 37 59

线程安全性

非线程安全，多线程扩容可能导致死循环 11

仍非线程安全，但尾插法避免死循环 11 37

三、红黑树与链表的转换机制
  1. 链表转红黑树条件
    1. 链表长度 ≥ 8（阈值选择基于泊松分布，概率极低，防止用户哈希算法劣化导致性能问题 ）。
    2. 数组容量 ≥ 64（否则仅扩容，不树化）
  2. 红黑树退化为链表条件
    1. 树节点数 ≤ 6（阈值差异避免频繁转换）
  3. 转换触发时机
    1. 插入时：若链表长度达到阈值且容量足够，触发树化
    2. 删除或扩容时：检查树节点是否需退化
四、性能优化关键点
  1. 负载因子与扩容
    1. 默认负载因子 0.75，平衡空间利用率和哈希冲突概率
    2. 扩容后容量为 2倍，保证索引计算高效（hash & (length-1)）
  2. 红黑树引入的意义
    1. 极端情况下（如哈希碰撞攻击），避免链表过长导致查询性能骤降 。

总结

JDK 1.8 的 HashMap 通过红黑树优化、尾插法和扩容逻辑改进，显著提升了高并发场景下的稳定性和性能。理解其底层数据结构差异及转换机制，有助于合理设计哈希函数、优化存储结构，并避免多线程问题。实际开发中，若需线程安全，应优先选择 ConcurrentHashMap

本文标签： HashMap工作原理的理解，17和18，数据结构，怎么切换红黑树和链表

版权声明：本文标题：HashMap工作原理的理解，1.7和1.8，数据结构，怎么切换红黑树和链表 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748234119a2273111.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。