做Java的同学基本都绕不开HashMap。尤其是JDK 1.8这是我心目中HashMap历史上改动最大、也最值得研究的一次版本迭代。很多面试题里问的底层实现原理、红黑树、扩容机制指的其实都是1.8版本。网上讲HashMap的文章一大把但大多数只是把源码贴一遍告诉你它这么写了至于为什么这么写解决了1.7的什么问题实际开发时要怎么避坑反而讲得少。这篇文章我就换个角度从JDK 1.8核心优化的维度把HashMap的关键改动拆开揉碎同时把面试里那些高频问题和实战中容易踩的坑一并梳理清楚。不管你是刚接触源码的初学者还是工作几年想查漏补缺的老手这篇都值得你花十几分钟认真读完。1. 从1.7到1.8HashMap核心改动全景1.1 一句话概括这次升级JDK 1.8的HashMap表面上看只是改了数据结构实际上围绕三个核心点做了重构底层存储从数组链表升级为数组链表红黑树哈希函数的扰动算法重写从多次异或简化为一次高16位右移异或扩容时不再逐个rehash重算下标而是通过位运算把原链表拆成高低位两条链。这三件事最终解决的是同一个问题让HashMap在哈希碰撞严重的极端场景下性能不至于从O(1)一路衰落到O(n)。我用表格把1.7和1.8的差异先摆出来后面逐一展开对比项JDK 1.7JDK 1.8底层结构数组 链表数组 链表 红黑树哈希函数4次位运算扰动1次高16位右移异或链表插入方式头插法尾插法扩容迁移遍历链表重新indexFor判断 hasholdCap拆高低位两条链树化无链表长度8且数组容量64时触发并发问题扩容死循环CPU飙高死循环消除但数据覆盖仍存在1.2 这些改动背后的核心痛点先说哈希碰撞。HashMap底层是数组加链表理想情况下每个桶只有一个元素get和put都是O(1)。但如果很多key算出来的下标恰好落在同一个桶里链表越来越长查询就要沿着链表逐个比对复杂度退化成O(n)。JDK 1.7时代如果刻意构造一些hashCode低位相同的key甚至可以把HashMap拖到性能极低这就是常说的哈希碰撞攻击。所以1.8引入红黑树就是为了兜底这种极端情况让单个桶里无论塞了多少元素查询复杂度最多也只是O(log n)。再说扩容死循环。JDK 1.7扩容用的是头插法新链表顺序会反过来。单线程下这没什么问题但多线程并发put触发扩容时两个线程同时操作一条链表很容易让节点的next指针互相引用形成环形链表。一旦环形成下次get一个不存在的key时链表遍历就永远走不完CPU直接飙到100%。这个问题的根源不在头插法本身而在于并发迁移时没有加锁保护但1.8改用尾插法之后配合高低位拆分从实现层面规避了环形链表的产生。最后是哈希函数。1.7的hash函数做了四次位运算扰动代码看着很复杂。1.8把扰动简化成一次异或是因为红黑树和新的扩容机制已经扛住了碰撞的底线过度扰动性价比不高。一次右移16位异或就把hashCode的高16位信息混合到了低16位对HashMap这种只用低位寻址的结构来说效果足够好还省了不必要的CPU开销。2. 哈希函数与寻址逻辑一次put操作的关键路径2.1 hash方法源码逐行解读JDK 1.8的hash函数长这样static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }就一行核心运算。key为null时返回0这也解释了为什么HashMap允许一个null key而且它一定会落在下标为0的桶里。key不为null时先拿到hashCode然后把hashCode右移16位再和自己做异或。很多初学者不明白为什么要右移16位再异或。关键在于hashCode是32位的int而HashMap计算桶下标时只会用到低位。假设数组容量是16那么n-1的二进制是1111任何hash值和它做与运算结果完全由hash值的低4位决定高28位的信息全被丢掉了。这样一来如果两个key的hashCode低位相同、高位不同它们就会撞到同一个桶散列分布就很差。右移16位再异或等于把高16位的信息折叠到低16位让低位不再只依赖原始hashCode的低位随机性大大增强。这就是常说的扰动函数。2.2 为什么用异或而不是与运算或或运算这个细节容易被忽略但面试偶尔会问到。异或的特点是两个bit不同为1相同为0结果中0和1的分布是均匀的。如果换成与运算结果偏向0换成或运算结果偏向1。哈希扰动追求的是让每一位尽可能均匀分布所以异或是数学上最优的选择。至于为什么只扰动一次而不是像1.7那样扰动四次我的理解是1.8已经把碰撞兜底交给了红黑树最坏情况下O(log n)可以接受那么扰动函数本身就可以做减法把CPU花在更有意义的事情上。而且右移16位正好是32位int的一半一次操作就能让高16位和低16位充分混合再多做几次边际收益很低。2.3 位运算寻址替代取模运算搞清楚hash值之后HashMap用它确定桶下标的核心代码是这句tab[i (n - 1) hash]其中n是数组容量必须是2的幂。当n是2的幂时n-1的二进制低位全是1比如n16时n-115二进制是1111此时 (n-1) hash 等价于 hash % 16但位运算比取模快得多。取模运算在CPU层面是除法位运算只需要几个时钟周期在高频put场景下差距不可忽视。这也是HashMap要求容量必须为2的幂的根本原因。一方面为了用位运算替代取模另一方面是为了扩容时的高低位拆分后面会详细讲。2.4 手动算一遍hello的存储位置光看原理不过瘾我手算一次完整的寻址过程。先算hello的hashCode按String的算法得到99162322转成十六进制是0x05E918D2补全32位二进制是0000 0101 1110 1001 0001 1000 1101 0010高16位是0x05E9低16位是0x18D2。右移16位后与自身异或h: 0000 0101 1110 1001 0001 1000 1101 0010 h 16: 0000 0000 0000 0000 0000 0101 1110 1001 异或结果: 0000 0101 1110 1001 0001 1101 0011 1011结果等于0x05E91D3B。假设HashMap数组容量是16n-115那么桶下标 15 0x1D3B 0x0B 11。如果不用扰动直接用原始hashCode的低16位0x18D2去算15 0x18D2 0x02 2。你看同样一个key扰动前后落到的桶完全不一样这就是高低位混合在实际中的效果。扰动之后参与下标计算的低位包含了更多维度的信息key在数组中的分布更均匀。3. 链表与红黑树的切换JDK 1.8最有争议的优化3.1 树化的完整触发条件先看putVal里链表追加节点后的关键代码for (int binCount 0; ; binCount) { if ((e p.next) null) { p.next newNode(hash, key, value, null); if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } ... }binCount从0开始计数当binCount大于等于7时也就是链表已经有8个节点时调用treeifyBin尝试树化。但树化不是必然发生treeifyBin方法开头还有一道关卡if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) resize();数组容量小于64时先扩容不树化。只有链表长度达到8并且数组容量达到64链表才会真的转换成红黑树。这个前置校验很容易被面试问到它的逻辑是如果数组容量还很小说明整体哈希分布可能存在问题此时扩容是更优解扩容能让碰撞快速摊平。只有容量已经不小、某个桶仍然长出长链表才说明key的hash分布真的不理想这时候树化才有价值。3.2 树化阈值为什么恰好是8这个数字不是拍脑袋定的JDK源码注释里给过一段泊松分布的概率数据。在负载因子0.75的理想随机哈希条件下单个桶内链表长度的概率分布大概是链表长度出现概率00.6065306610.3032653320.0758163330.0126360640.0015795250.0001579560.0000131670.0000009480.00000006也就是说一个桶里链表长度达到8的概率不到千万分之一。在正常的使用场景下链表长度几乎不可能长到8一旦出现基本可以断定是key的hashCode分布出了问题比如恶意构造的碰撞key。这时候用红黑树去兜底把查询从O(n)优化到O(log n)代价是值得的。3.3 为什么选择红黑树而不是平衡二叉树同为二叉查找树的变种AVL树比红黑树平衡得更严格理想情况下查询确实更快但插入和删除时需要更多次的左旋和右旋来维持平衡。HashMap不是只读结构的缓存put操作同样频繁如果选AVL树树平衡的维护成本会显著拖累写入性能。红黑树的做法是从根到叶子的最长路径不超过最短路径的两倍这是一种近似平衡查询复杂度仍然是O(log n)但插入和删除的旋转次数远少于AVL综合读写性能更优。还有人问过为什么不直接用跳表。跳表的实现相对简单查询也是O(log n)但每个节点平均要维护多层指针内存占用比红黑树高不少。HashMap对内存敏感红黑树在相同数据规模下占用的额外空间更小所以红黑树是工程上的最优解。3.4 退化阈值为什么是6链表长度超过8时树化但删除节点后红黑树的节点数少于6时又要退化成链表。这个阈值是6而不是7或者8是为了防止抖动。如果退化阈值也是8那么链表长度在7和8之间反复增减时系统会频繁触发树化和退化每次转换都要重新组织节点结构开销极大。把退化阈值调低到6就留出了一个缓冲区间链表长度在7左右徘徊时既不会树化也不会退化避免无谓的性能损耗。4. 扩容机制重构告别死循环迎来高低位拆分4.1 JDK 1.7扩容死循环问题深入解析先说1.7为什么扩容会死循环。核心代码是transfer方法void transfer(Entry[] newTable, boolean rehash) { int newCapacity newTable.length; for (EntryK,V e : table) { while(null ! e) { EntryK,V next e.next; // 线程挂起点 int i indexFor(e.hash, newCapacity); e.next newTable[i]; // 头插法 newTable[i] e; e next; } } }头插法的特点是新链表的顺序和原链表完全相反。假设原链表是A - B - C扩容后先处理A再处理B再处理C最终新链表变成C - B - A。并发场景下问题就来了。线程T1执行到EntryK,V next e.next这行拿到nextB之后被挂起。线程T2完成了整个扩容把原链表迁移成了新顺序。等T1恢复执行它手里的e还是A但A的next已经在T2的迁移中变了。T1继续做e.next newTable[i]把A指向了T2迁移后的链表头部结果A又重新指向了已经被T2移动过的节点形成环形引用。下次get一个不存在的key遍历到环就会死循环CPU飙到100%。4.2 JDK 1.8如何用尾插法消除死循环1.8的resize方法里对链表的处理完全重写。核心逻辑不是简单地把每个节点重新算下标而是用尾插法把原链表拆成两条链NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { if (loTail null) loHead e; else loTail.next e; loTail e; } else { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; }注意这里是尾插法每个节点追加到链表尾部两条链的相对顺序和原链表一致。即使并发场景下两个线程同时迁移节点之间的next指向不会像1.7那样被倒置自然也就不会形成环形链表。当然这并不意味着HashMap在并发下就安全了数据覆盖和丢失的问题依然存在只是最可怕的死循环从实现层面被根除了。4.3 高低位拆分的数学原理1.8扩容最巧妙的地方是不用重新算每个节点的hash值只需要判断(e.hash oldCap) 0。为什么一个与运算就能决定新位置因为oldCap是2的幂二进制里只有一位是1。比如oldCap16二进制是10000那么hash 16的结果只有两种0或者16。为0说明扩容后新增的那一位是0节点留在原下标j为16说明新增的那一位是1节点移到joldCap。我举个具体例子。扩容前容量16n-1是15也就是二进制1111。两个节点hash分别为5和215: 二进制00101 21: 二进制10101扩容前下标计算5 15 5 21 15 5所以两个节点都在下标5的桶里。扩容后容量变成32n-1是31也就是二进制111115 31 5 21 31 21 5 16用hash oldCap判断5 16 0 // 留在下标5 21 16 16 // 移到下标51621只需要一次与运算就知道节点该留还是该走而且原链表被完整拆分成两条有序链新链表不需要任何额外的哈希计算。这个设计的工程价值在于扩容时省去重新计算每个节点hash的开销同时保持了链表顺序为并发安全打下了基础。4.4 负载因子0.75的取舍扩容时机由threshold控制threshold 容量 * 负载因子。默认负载因子0.75是时间与空间的权衡。负载因子调大比如1.0数组更晚扩容节省内存但碰撞概率升高查询变慢。负载因子调小比如0.5碰撞减少查询变快但数组过早扩容浪费内存扩容也更频繁。0.75是长期工程实践得出的经验值在绝大多数场景下能兼顾两边的成本不建议轻易修改。5. 并发场景的正确姿势HashMap、Hashtable、ConcurrentHashMap怎么选5.1 HashMap在并发下的真实表现很多人以为1.8修了死循环HashMap就线程安全了这是误解。并发put时两个线程同时往数组的同一个位置写入后写的会覆盖先写的造成数据丢失。多个线程同时触发扩容时各写各的新数组最终只有一个数组生效同样丢数据。此外modCount的计数也不是原子的迭代时容易快速失败。我用一个简单例子演示数据丢失public class HashMapConcurrentTest { public static void main(String[] args) throws InterruptedException { final MapInteger, String map new HashMap(); Thread t1 new Thread(() - { for (int i 0; i 10000; i) { map.put(i, t1); } }); Thread t2 new Thread(() - { for (int i 0; i 10000; i) { map.put(i, t2); } }); t1.start(); t2.start(); t1.join(); t2.join(); System.out.println(map size map.size()); } }最后size大概率不是20000甚至可能小于10000因为两个线程写入同一个key时后者覆盖前者。多跑几次能更明显地看到计数异常。5.2 Hashtable为什么被边缘化Hashtable是JDK 1.0时代的老类所有方法都加了synchronized也就是全表锁。并发读写时只有一个线程能进入方法其他线程全部阻塞吞吐量非常低。而且它不允许null key和null value这个约束在实际业务中很不方便。它还存在一些历史包袱比如初始容量11扩容是old * 2 1底层结构始终是数组加链表。虽然功能上没大毛病但并发性能和设计思路都已经被ConcurrentHashMap全面超越。5.3 ConcurrentHashMap的现代并发方案JDK 1.8的ConcurrentHashMap抛弃了1.7的分段锁设计改用CAS加synchronized对单个桶加锁。put时先通过CAS尝试写入空桶如果桶不为空再对桶头节点加synchronized锁锁粒度从段级细化到底层桶级。并发度更高读操作无锁整体吞吐量吊打Hashtable。三者的对比一句话总结单线程用HashMap多线程读多写少可以用Collections.synchronizedMap包装多线程写入频繁必须用ConcurrentHashMap。千万不要在并发场景下裸用HashMap也不要再用Hashtable做高并发方案。维度的对比HashMapHashtableConcurrentHashMap线程安全否是全表锁是桶级锁CASnull key/value允许不允许不允许底层结构数组链表红黑树数组链表数组链表红黑树性能最高最低接近HashMap适用场景单线程遗留代码并发读写频繁6. 面试与实战中的HashMap高频考点和避坑指南6.1 面试高频问题速查下面这几个问题我面试别人的时候几乎必问建议你们也背熟HashMap的底层数据结构是什么JDK 1.7是数组加链表JDK 1.8是数组加链表加红黑树。为什么容量必须是2的幂为了用 (n-1)hash 位运算替代取模同时也是高低位拆分扩容的前提。hash函数为什么右移16位再异或为了把hashCode的高16位混合到低16位提高低位的随机性。树化条件是什么链表长度达到8并且数组容量达到64。为什么树化阈值是8泊松分布概率不到千万分之一正常情况不会触发。为什么退化阈值是6避免链表长度在阈值附近反复树化和退化造成性能抖动。JDK 1.8扩容为什么不用rehash因为通过hash oldCap判断新增位能直接把原链表拆成高低位两条链。JDK 1.7为什么会产生死循环头插法在并发迁移时反转链表顺序节点环形引用。HashMap和Hashtable的区别线程安全、null支持、初始容量、底层结构、扩容方式都有差异。并发场景用什么优先ConcurrentHashMap。6.2 用反射观察HashMap的内部结构源码看再多不如实际跑一次亲眼看看内部结构。我用反射拿到HashMap的table数组把每个桶的链表长度打出来import java.lang.reflect.Field; import java.util.HashMap; public class MapDebug { public static void main(String[] args) throws Exception { HashMapString, String map new HashMap(); for (int i 0; i 16; i) { map.put(key i, value i); } Class? clazz Class.forName(java.util.HashMap); Field tableField clazz.getDeclaredField(table); tableField.setAccessible(true); Object[] table (Object[]) tableField.get(map); System.out.println(table length table.length); for (int i 0; i table.length; i) { if (table[i] ! null) { int count 0; Object node table[i]; while (node ! null) { count; Field nextField node.getClass().getDeclaredField(next); nextField.setAccessible(true); node nextField.get(node); } System.out.println(bucket i - count nodes); } } } }在JDK 1.8环境下运行能看到默认容量16插入16个元素时已经触发了扩容table长度变成32。如果把key换成刻意构造相同低位hash的字符串还能观察到某个桶的链表长度不断增长。这种调试方式对理解HashMap内部行为很有帮助我在Linux服务器上排查问题时也经常用这个思路。6.3 初始容量预估算一个容易被忽略的性能点很多同学直接用默认无参构造创建HashMap数据量大的时候频繁扩容性能损耗非常明显。HashMap扩容要新建数组并重新分配所有节点数据量越大成本越高。比如要往HashMap里放100个键值对不指定初始容量的话数组从16开始threshold是12第13个元素插入时就触发第一次扩容翻倍到32。后面还得扩两次一直到容量256才装得下100个元素。正确姿势是先估算。JDK源码里tableSizeFor方法会把传入的初始容量转换成大于等于它的最小2的幂次所以你可以按这个公式算初始容量 (预计元素个数 / 0.75f) 1100个元素就是 100/0.75 1 ≈ 134向上取2的幂等于256。当然你直接写new HashMap(134)也可以内部会帮你转成256。有经验之后我一般会留点余量避免计算误差导致刚装满又扩容。6.4 实战中踩过的坑第一个坑是用可变对象做key。比如用ArrayList做keyput进HashMap后修改了list内容hashCode变了再get就再也找不到了。对象还躺在HashMap里但你已经失去了访问它的索引。解决方法是key尽量用String、Integer、Long这类不可变对象或者保证参与hashCode计算的字段不会被修改。第二个坑是自定义对象的hashCode质量差。我见过有人图省事hashCode直接返回一个固定值结果所有对象落在同一个桶里HashMap退化成链表查询效率直接从O(1)变成O(n)。如果业务上必须用自定义对象做keyhashCode的高位和低位都要尽量参与计算用Objects.hash()这类现成工具就行。第三个坑是迭代时删除元素。在遍历HashMap的过程中如果直接调用map.remove(key)会触发modCount变化迭代器抛出ConcurrentModificationException。正确做法是用迭代器的remove方法或者先收集要删除的key遍历结束后再统一删除。第四个坑是初始化容量的理解偏差。new HashMap(1000)并不是直接创建1000个桶而是向上取2的幂实际容量是1024。new HashMap(100)实际容量是128。如果只放100个元素没问题但如果以为容量是100而没注意到threshold是96实际放到第97个元素就会触发扩容。很多人在这上面栽过跟头。第五个坑和内存有关。HashMap的数组在扩容到很大之后即使你清空了数据容量也不会自动缩回去。如果有临时的大HashMap用完置为null让GC回收比等着它自己缩容靠谱得多。6.5 关于HashMap使用的一个建议HashMap核心优化的本质是在快速查找和极端碰撞之间找到了一个工程平衡点。1.8引入红黑树、重写扩容逻辑、简化哈希函数每一步都不是为了炫技而是针对真实场景中的痛点做取舍。日常写代码时多想想容量预估、key的不可变性、并发场景选型比死记硬背源码有价值得多。顺带提一句如果你还在用老版本的JDK真的建议至少升到1.8。JDK 1.8无论在语言特性、JVM默认参数还是集合类实现上都相比旧版本有全方位的提升HashMap只是其中一个缩影。安装配置也就几分钟的事但换来的性能和稳定性收益是长期的。这也是我这几年在团队里推广代码规范时第一个要求大家统一的环境版本。