1. 先看清HashMap的底层结构：数组、链表、红黑树是怎么拼在一起的
HashMap大概是Java容器里被面试官问得最多、被线上故障坑得最惨的一个类。我最早认真读它的源码，正因为某个跨平台系统的压测频繁出现CPU100%，抓完线程栈发现所有线程都卡在HashMap的get方法上。那会儿才意识到，只背“键值对数组加链表”这种结论远远不够。这篇文章基于JDK8的HashMap源码，把它的底层结构、hash散列、put/get流程、resize扩容以及几个最容易踩的生产环境问题一次性讲透。
1.1 核心字段：table、size、threshold、loadFactor分别是什么
打开HashMap的源码，第一眼看到的是这一组静态常量：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16 static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64;真正存数据的地方是transient Node<K,V>[] table，这是一个Node节点数组。Node节点内部有四个字段：hash、key、value、next。next指向同一个桶里的下一个节点，所以数组的每一个位置，都是一个链表头；当链表太长时，又会整体转换成红黑树。
table数组的长度默认是16，但不是在new HashMap()时立刻创建的。源码里table的初始化是懒加载，第一次put的时候才通过resize()把数组建出来。这么做的原因很简单：很多Map创建之后根本不会放数据，没必要为每个实例都提前分配一块连续内存。
loadFactor默认0.75，threshold = capacity * loadFactor。threshold不是容量上限，而是触发扩容的“水位线”。比如说容量是16，threshold就是12，当size一旦超过12，下一次put就会触发扩容到32。0.75这个值本质上是在时间和空间之间取的平衡：太小浪费内存，太大容易让冲突变多，链表和红黑树更早出现，读写性能下降。
1.2 JDK8为什么要引入红黑树，阈值8和6又是怎么定的
在JDK7及以前，HashMap的每一个桶都只有链表。如果很多key的hash撞到同一个桶，get就变成遍历一个很长的链表，最坏情况O(n)。对在线服务来说，一个接口里如果频繁get，这种退化的链表遍历足以让CPU使用率直接拉满。
JDK8的改进是：当单个桶里的节点数达到TREEIFY_THRESHOLD（8），并且table数组长度不小于MIN_TREEIFY_CAPACITY（64），这个桶就从链表转换成红黑树。树化后，查找复杂度从O(n)降为O(log n)。红黑树的优点不只是平衡，更重要的是插入和删除不需要像AVL树那样频繁调整，整体更适合HashMap这种频繁读写的数据结构。
这里有两个细节容易被忽略。第一，不是链表长度一到8就立刻树化，数组长度小于64时，resize()会优先把数组扩大一倍，让数据分散开，而不是马上转树。第二，扩容拆分红黑树时，如果某个桶里的节点数量降到UNTREEIFY_THRESHOLD（6）以下，会从树退回到链表。8和6之间留了2的缓冲，避免节点数量在边界附近震荡时反复树化和退化，这个设计很像操作系统里“高水位”“低水位”的思路。
2. hash散列与桶下标计算：真正决定性能的不是put，而是位运算
很多人以为HashMap算桶下标用的是key.hashCode() % size，其实不对。JDK8里面两步走：先扰动哈希码，再用位运算取模。
2.1 高16位异或低16位，到底防的是什么
先看hash方法：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }key为null时hash为0，所以HashMap允许一个null键。不为null时，把key的hashCode赋值给h，再把h右移16位，和原来的h做异或。这一步叫扰动函数。
为什么不直接用hashCode？因为table数组长度默认是16，计算下标用的掩码(n-1)只有低4位是1，数组长度再大，参与下标计算的通常也只是低位。而hashCode是一个32位整数，如果对象本身的hashCode分布不好，低位很容易出现大量重复，高位的信息就白白浪费了。把高16位异或到低16位，相当于让高位也参与后续的取模，从而让散列结果更均匀。这一步代价极小，但对碰撞率的影响非常明显。
2.2 为什么长度必须是2的幂，以及tableSizeFor做了什么
桶下标计算是：
tab[i = (n - 1) & hash]这里用的是按位与，等效于hash % n，但前提是n必须是2的幂。所以HashMap的容量永远要求是2的幂。你new HashMap(19)的时候，它不会真的用19当初始容量，而是通过tableSizeFor方法把它变成大于等于19的最小的2的幂，也就是32。
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }这段代码把cap减1后从最高位的1开始，通过连续右移和或运算，把后面所有低位全部填成1，最后加1，得到2的幂。
用(n-1) & hash而不是取模，主要有两个原因：一是在绝大多数CPU上位运算比取模指令快；二是当n是2的幂时，相当于只取hash的低log2(n)位作为下标，这为后面扩容时“无需rehash”的分流方案打下了基础。这一点在讲resize时再展开。
3. put流程逐行走一遍：从懒初始化到链表树化的完整分支判断
put的入口是put(K key, V value)，真正干活的putVal方法。理解putVal，基本就理解了大半个HashMap。
3.1 new HashMap()为什么没有立刻分配数组
确认一下懒加载的代码路径：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 桶里已经有节点，进入冲突处理分支 } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }第一次put时，table为null，直接进入resize()去创建默认容量16的数组。这一步也解释了为什么很多人new HashMap()后看内存占用几乎没区别，真正的数据容器是在首次写入时才建出来的。
3.2 putVal的冲突处理：覆盖、追加、树化分别走哪条路
桶下标i算出来后，如果该位置为null，直接创建一个新节点放进去，这是最理想情况。有冲突时，先判断第一个节点p是否和当前key相同：
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;这里先比hash，再比引用，最后才用equals。因为hash相等的两个key不一定相等，但hash不等的一定不相等，先比hash可以快速过滤掉绝大多数无关节点。如果p是TreeNode，说明这个桶已经树化，改走putTreeVal。否则，遍历链表，在链表尾追加新节点，同时用binCount统计当前节点数。遍历过程中如果找到相同key，就跳出循环准备替换value。
真正替换value的代码是这样的：
if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }这意味着put发现有相同key时，不会新建节点，而是复用旧节点、覆盖value。很多人忽略的“Map里面放null值”也是在这里体现的：只有当onlyIfAbsent为true且旧值不为null时才不覆盖。
链表追加完成之后，还有这一段：
if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);binCount从0开始计数，binCount到了7就说明链表里有8个节点，于是尝试树化。但treeifyBin内部会先检查tab.length是否小于MIN_TREEIFY_CAPACITY，如果小于64，就会先扩容而非转树。这是HashMap里“先扩大桶数量，再尝试转红黑树”的优先级体现。
3.3 树化阈值8和最小容量64，为什么缺一不可
假设哈希函数设计得非常糟糕，大量key都映射到同一个桶，链表会越来越长，查询退化成线性扫描。这时如果数组容量还很小，正确做法是扩大数组，让数据往更多桶里分散，而不是为这一个桶建一棵树。所以64这个下限保证了树化之前，底层容器已经有一定规模。反过来，如果桶内节点达到8，但数组容量已经很大，说明这一小片区域碰撞极端严重，这时候转红黑树才有意义。
红黑树本身每个节点TreeNode比普通Node多维护parent、left、right、prev四个引用，内存开销明显更大。所以HashMap只在“冲突极端严重”的条件下才树化，普通场景下用链表就已经很便宜了。
4. resize扩容过程拆解：为什么JDK8不需要重新计算每个桶的下标
扩容是HashMap源码里最容易被讲错的一段。JDK7的扩容需要把每个节点重新计算hash、重新放入新数组；JDK8把这件事变成了“要么原地不动，要么整体挪动oldCap的距离”。
4.1 新容量和新阈值怎么算
resize的开头是一系列容量和阈值计算：
if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; }正常情况下，新容量是旧容量的两倍，新阈值也是旧阈值的两倍。当oldCap到了1<<30这个上限后，HashMap不再扩容，而是把threshold抬高到Integer.MAX_VALUE，意思是“能塞多少塞多少，别想再扩了”。容量翻倍而不是扩大10%，是为了保证长度继续保持2的幂，这一步是后面位运算分流的基础。
4.2 (e.hash & oldCap) == 0 的分流逻辑
扩容时遍历每一个桶，如果桶里只有一个节点，直接重新计算下标放到新数组。如果桶里是链表，就把链表拆成两条：
if ((e.hash & oldCap) == 0) { // 留在原索引 loTail.next = e; } else { // 挪到原索引 + oldCap hiTail.next = e; }为什么用e.hash & oldCap就能判断？因为扩容时新掩码比旧掩码多了一个高位。比如容量从16变成32，下标掩码从1111变成11111，多了第5位。如果一个节点的hash在第5位上是0，那么它在32长度下的下标与16长度时完全一样；如果第5位是1，新下标就是旧下标加16。oldCap恰好就是那个新增位的权重，所以e.hash & oldCap为0则不动，为1则加oldCap。
这个方案比JDK7的“逐节点rehash”聪明得多：不需要重算hash，不需要再次取模，本质上只是把一个桶里的链表按新增的某一位拆成高低两半。这也是HashMap从“每次resize都要全量重算”到“扩容成本大幅降低”的key优化。
4.3 并发下resize的经典问题：JDK8到底还死不死循环
JDK7的死亡循环，是头插法在并发扩容时造成链表成环，之后get一个不存在的key就可能无限循环。JDK8改成了尾插法，并且使用高低位拆分，从代码结构上确实不会再因为扩容形成环形链表，所以“JDK8修复了并发死循环”这个说法在字面上成立。
但千万别理解成JDK8的HashMap并发安全了。两个线程同时put，各自读到同一个table引用，各自扩容，最后后完成的人直接把前一个人扩容后的数组覆盖掉，丢数据是必然的。size计数也不是原子的，多线程put后size可能偏小，导致永远不会触发扩容。所以结论仍然是：并发场景下老老实实用ConcurrentHashMap，用HashMap做并发缓存，结果往往不是报错，而是数据悄悄丢失，这种问题最难排查。
5. get/containsKey的查找路径与hashCode、equals的三大契约坑
5.1 getNode怎么用最短路径找到目标节点
get方法的实际逻辑集中在getNode：
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }查找顺序很清楚：先看table是否为空，再看桶里第一个节点，接着区分当前桶是红黑树还是链表，然后沿着对应结构找。整个查找过程里，最短路径是“数组不为空且第一个节点就是目标”，最坏情况是在红黑树里走O(log n)。containsKey与get的差别只在于有没有返回value，查找逻辑完全一样。
这里有个实用技巧：get前不需要自己判空containsKey，直接get返回null就可以认为不存在。但要注意，如果业务允许value为null，那么get返回null并不能区分“key不存在”和“value是null”。如果业务上把null当合法值，最好用containsKey做明确判断，或者干脆约定Map里不放null。
5.2 hashCode重写了equals不重写，或者反过来，会发生什么
HashMap判断两个key是否相同，用的是(p.hash == hash) && ((k = p.key) == key || (key != null && key.equals(k)))。这个条件同时依赖hashCode和equals。如果类只重写equals不重写hashCode，两个内容相同的对象在用equals比较时相等，但它们的hashCode很可能继承自Object的地址值，完全不相同，于是被分到不同桶，get时到不了那个桶，结果就是“明明存过，却取不出来”。
反方向也一样：只重写hashCode不重写equals，两个对象即使hashCode相同，也在同一个桶里，但equals不相等，最终还是会判断为不同key。
所以实际开发中有一条铁律：重写equals，必须同步重写hashCode。如果用的是IDE自动生成，通常没问题，但如果你手写了equals而忽略了hashCode，线上偶发的“查不到数据”十有八九就是这个原因。
5.3 可变对象作key：放进Map之后就别再改字段
HashMap的桶下标在put时就已经根据当时的hashCode算好了。如果某个对象作为key放进Map之后，它的hashCode相关的字段被修改，再去get时算出来的下标已经和之前不一样，自然找不到。即使仍能落到同一个桶，equals也可能因为字段变化而返回false。
更隐蔽的情况是，对同一个对象修改前后分别调get，前一次能取到，后一次取不到，排障时很容易误以为是并发问题。解决办法很简单：放进HashMap的key，要么用String、Integer这种不可变类型，要么保证对象不可变；如果必须用自定义对象，至少别在put之后修改参与hashCode计算的字段。
6. 线上HashMap问题排查清单：从CPU飙高到查不到数据的常见原因
看完源码，再看实际业务里的问题，大多都能从上面这些机制里找到答案。
6.1 症状一：线程卡在get上，CPU飙高
如果线程栈显示大量线程卡在HashMap.get/put，多半是扩容或者链表遍历出了问题。先确认这个Map是否被多个线程共享，如果是，直接换ConcurrentHashMap，然后压测验证。如果单线程下也慢，重点查key的hashCode分布，比如某个对象重写了hashCode，但实现里把所有内容都一样地返回同一个固定值，那所有key都会挤在一个桶里，形成超长链表；用测试工具统计各桶深度，能立刻看出问题。
6.2 症状二：put进去之后get不到
按顺序排查：key类有没有重写hashCode和equals，两个方法是否一致；key对象在put之后有没有被修改；有没有多个线程同时操作导致数据被覆盖。还有一个容易被忽略的细节：如果自定义key的hashCode依赖随机字段，比如UUID，每次new对象hashCode不同，那同一逻辑对象每次get时算出的桶都不一样，也会产生“找不到”的假象。
6.3 从源码反推参数调优
已知未来大概要放expectedSize个元素，初始容量可以直接设置成expectedSize / 0.75f + 1。比如预估1000个元素，1000 / 0.75 + 1约等于1334，HashMap会通过tableSizeFor自动调整到2048。这么做的目的是减少扩容次数。无参构造默认16容量，当数据量超过threshold时连续扩容，每次扩容都要复制和重排所有节点，浪费很明显。
如果某个Map的key多但value更新频繁，可以设置较低的负载因子，比如0.6，来降低冲突率。代价是内存占用变高，table数组里会有更多空桶。相反，如果内存紧张且能接受偶尔的链表扫描，可以用0.8甚至0.9。注意loadFactor必须在构造时传入，HashMap没有提供运行时修改loadFactor的公开方法。
6.4 最后几点个人体会
读HashMap源码，最值得学的不是“八股答案”，而是那套“用空间换时间、用位运算替代取模、用阈值做结构切换”的思路。后来我排查过的很多非HashMap性能问题，最终都会回到“数据分布是否均匀”这个根本问题上。
我的习惯是，每个项目都写一个小的Map诊断工具，打印出总节点数、最大桶深度、空桶比例。实测下来，只要最大桶深度超过5，就该检查key的hashCode了；如果超过20，基本上可以认定是人为的设计缺陷。这个工具的统计逻辑可以直接从源码里抄：遍历table数组，对每个非null桶走一遍链表或树，统计深度分布。
如果你刚接触源码，建议从putVal和resize这两段入手，先把主干逻辑画成普通的文字分支导读，再补HashMap的并发问题。把这几个核心流程吃透之后，再去看getNode、removeNode、replaceAll这些方法，会发现它们都在讲同一套规则。源码读通的那一刻，很多以前只能靠背的结论，都会开始变得理所当然。
