哆啦A梦之HashMap的原理
- 2025-12-09 21:03:23
哆啦A梦之HashMap的原理
📝 Java HashMap 原理速记
🧱 核心结构
HashMap 底层是数组 + 链表 + 红黑树。数组也叫“桶”，默认长度16。当多个 key 哈希到同一个桶，用链表串起来。链表太长（长度≥8）且数组长度≥64时，链表会转成红黑树，查询效率更高。
🔎 哈希和定位
计算 key 的哈希值时，会用“扰动函数”：把 hashCode 的高16位和低16位异或一下，减少碰撞。桶的位置用 (数组长度-1) & hash 算出来，位运算比取模快很多。
➕ Put 流程
第一次 put 会初始化数组。
定位到桶，如果桶空，直接放进去。
桶不空，就顺着链表或红黑树往下找，key 相同就覆盖，没有就新增。
新增后检查是否要树化或扩容。
🔄 扩容机制
当元素个数超过“容量×负载因子”（默认16×0.75=12），就会扩容。新数组是原来的2倍。旧数据迁移到新数组时，链表会被拆成两份：一部分留在原位置，另一部分放到“原位置+旧容量”的位置。扩容不用重新算哈希，效率高。
⚠️ 线程安全
HashMap 不是线程安全的！多线程 put 可能导致数据错乱或死循环（JDK7头插法问题，JDK8已改尾插）。高并发场景用 ConcurrentHashMap，性能更好也更安全。
💡 面试常问
为什么负载因子是0.75？
答：折中考虑，太小容易冲突，太大浪费空间。
为什么链表长度8转树，6退化？
答：避免频繁转换，6是缓冲阈值。
为什么推荐 String/Integer 做 key？
答：不可变，hashCode 一致，equals 好比较。
为什么数组长度是2的幂？
答：方便用位运算定位桶，效率高。
为什么用尾插法？
答：JDK8修复多线程死链问题。
📌 一句话总结
数组链表红黑树，扰动函数减碰撞；尾插扩容防死链，负载0.75是黄金！
#哆啦a梦 #科普 #漫画 #java #八股文
🧱 核心结构
HashMap 底层是数组 + 链表 + 红黑树。数组也叫“桶”，默认长度16。当多个 key 哈希到同一个桶，用链表串起来。链表太长（长度≥8）且数组长度≥64时，链表会转成红黑树，查询效率更高。
🔎 哈希和定位
计算 key 的哈希值时，会用“扰动函数”：把 hashCode 的高16位和低16位异或一下，减少碰撞。桶的位置用 (数组长度-1) & hash 算出来，位运算比取模快很多。
➕ Put 流程
第一次 put 会初始化数组。
定位到桶，如果桶空，直接放进去。
桶不空，就顺着链表或红黑树往下找，key 相同就覆盖，没有就新增。
新增后检查是否要树化或扩容。
🔄 扩容机制
当元素个数超过“容量×负载因子”（默认16×0.75=12），就会扩容。新数组是原来的2倍。旧数据迁移到新数组时，链表会被拆成两份：一部分留在原位置，另一部分放到“原位置+旧容量”的位置。扩容不用重新算哈希，效率高。
⚠️ 线程安全
HashMap 不是线程安全的！多线程 put 可能导致数据错乱或死循环（JDK7头插法问题，JDK8已改尾插）。高并发场景用 ConcurrentHashMap，性能更好也更安全。
💡 面试常问
为什么负载因子是0.75？
答：折中考虑，太小容易冲突，太大浪费空间。
为什么链表长度8转树，6退化？
答：避免频繁转换，6是缓冲阈值。
为什么推荐 String/Integer 做 key？
答：不可变，hashCode 一致，equals 好比较。
为什么数组长度是2的幂？
答：方便用位运算定位桶，效率高。
为什么用尾插法？
答：JDK8修复多线程死链问题。
📌 一句话总结
数组链表红黑树，扰动函数减碰撞；尾插扩容防死链，负载0.75是黄金！
#哆啦a梦 #科普 #漫画 #java #八股文
本文来自网友投稿或网络内容，如有侵犯您的权益请联系我们删除，联系邮箱：wyl860211@qq.com 。
