1. 从一个反直觉的面试题说起为什么容量总是2的幂很多人第一次看HashMap源码时心里都会冒出一个疑问为什么初始容量非得是16扩容还得翻倍老老实实用10或者100这种整数不行吗我当年也被这个问题卡过后来把putVal方法翻来覆去读了几遍才明白这背后藏着一个非常精巧的设计——用位运算替代取模运算。先看一段核心代码这是HashMap定位数组下标的关键一步// n是数组长度hash是经过扰动后的哈希值 if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null);注意这里用的是(n - 1) hash而不是hash % n。这两者在n是2的幂时结果完全等价但位运算的速度比取模快得多。举个例子n16时n-115二进制是0000 1111任何hash值和它做与运算结果都只会落在0到15之间正好是数组的合法下标范围。那如果n不是2的幂呢假设n10n-19二进制是0000 1001。你会发现与运算的结果永远不可能出现0000 0010、0000 0100、0000 0110这些值也就是说数组里有一部分位置永远被浪费了而且哈希冲突的概率会显著上升。这就是为什么HashMap死磕2的幂——不是为了好看是为了让哈希分布尽可能均匀同时把性能压榨到极致。理解了这一点后面看扩容机制、看哈希扰动函数很多设计就顺理成章了。这也是我建议所有想深入HashMap的人第一件事就是把tableSizeFor方法和(n - 1) hash这个表达式吃透它是整个数据结构的地基。1.1 哈希扰动函数到底在防什么光有2的幂还不够如果直接用key的hashCode去和n-1做与运算高位信息就全丢了。比如两个key的hashCode分别是0000 0000 0000 0000 0000 0000 0000 0001和0000 0001 0000 0000 0000 0000 0000 0001在n16的情况下它们和15做与运算的结果都是1直接撞车。HashMap的解决办法是加一层扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把hashCode的高16位右移后和低16位做异或相当于让高位信息也参与到低位运算中。这样即使数组长度很小高位的变化也能影响到最终的索引结果冲突概率大幅降低。这个操作的成本极低就一次移位加一次异或但效果立竿见影。我实测过一个极端场景用连续整数作为key往HashMap里塞100万条数据如果不做扰动链表的平均长度会明显偏高加上扰动之后分布均匀得多。这也是为什么JDK8之后虽然引入了红黑树但扰动函数依然保留——它从源头上减少了冲突比事后补救更划算。1.2 负载因子0.75是怎么拍出来的负载因子loadFactor默认0.75这个数字不是随便写的。它本质上是空间利用率和查询效率之间的一个折中。如果负载因子太高比如1.0数组几乎被填满才扩容空间是省了但哈希冲突会急剧增加链表变长查询从O(1)退化到O(n)。如果负载因子太低比如0.5冲突是少了但一半空间空着内存浪费严重而且扩容更频繁rehash的开销也上去了。0.75对应的是泊松分布下的一个较优解。源码注释里其实提到过在理想哈希下一个桶中出现8个元素的概率已经低到千万分之几这也是为什么链表转红黑树的阈值定在8。而0.75正好能让桶中元素数量维持在一个较低水平同时不至于浪费太多空间。注意负载因子可以在构造HashMap时自定义但除非你有非常明确的理由否则不建议乱改。我见过有人为了省内存把负载因子调到0.9结果查询性能掉了将近30%得不偿失。2. put方法的完整链路一次插入到底经历了什么很多人背面试题时能说出“先算hash再找桶空了就放不空就遍历”但真到看源码时面对那一大坨putVal方法还是会晕。我把它拆成几个阶段你跟着走一遍就清楚了。2.1 数组初始化懒加载的时机很讲究HashMap的数组并不是在构造方法里创建的而是第一次put时才初始化。这个设计叫懒加载目的是避免创建了HashMap却一直不用白白占着内存。if ((tab table) null || (tab resize()).length 0) n (tab resize()).length;第一次put时table为null直接调用resize()完成初始化。resize()方法身兼两职初始化数组和扩容内部通过判断oldCap是否为0来区分。这种“一个方法干两件事”的写法在源码里很常见读的时候要留意分支条件。2.2 桶为空直接落位算出索引i之后如果tab[i] null说明这个桶还没人占直接new一个Node放进去if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null);这一步没什么好说的但要注意Node的构造参数里带了hash值。为什么要存hash因为后续查找、扩容时都需要反复比较hash存下来避免重复计算典型的空间换时间。2.3 桶不为空三种情况分头处理这是putVal方法里最核心的一段逻辑我把它整理成表格看起来更直观情况判断条件处理方式首节点就是目标hash相同且key相等直接覆盖value桶是红黑树p instanceof TreeNode调用putTreeVal插入树节点桶是链表以上都不是遍历链表尾部插入或覆盖首节点判断这里有个细节先比hash再比或equals。先比hash是因为整数比较极快能过滤掉绝大多数不相等的key再用判断引用相等最后才用equals。这个顺序是性能优化的经典套路值得借鉴到自己的代码里。链表遍历时JDK8用的是尾插法而JDK7是头插法。这个改动很关键——头插法在并发扩容时可能形成环形链表导致死循环。虽然HashMap本身不是线程安全的但尾插法至少降低了出问题的概率。遍历过程中如果发现key已存在就覆盖value并返回旧值如果走到尾部还没找到就new一个节点挂在后面然后判断链表长度是否达到8达到就转红黑树。2.4 扩容触发size超过阈值之后每次插入成功后会执行if (size threshold) resize();threshold capacity * loadFactor。比如容量16、负载因子0.75阈值就是12。插入第13个元素时触发扩容。注意这里是先插入再判断也就是说第13个元素是先放进去了然后才扩容扩容后size13threshold变成24。这个顺序有讲究如果先判断再插入那么容量满的时候还得先扩容再插入多一次判断先插入再判断逻辑更顺而且扩容时能把新元素一起迁移效率更高。3. 扩容机制resize里的门道比想象中多扩容是HashMap里最复杂的部分也是面试高频考点。JDK8对扩容做了大幅优化核心思路是利用2的幂特性把元素分成“原位置”和“原位置旧容量”两组避免了JDK7里重新计算hash的繁琐过程。3.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; }规则很清晰容量翻倍阈值也翻倍。但如果旧容量已经达到最大容量130就不再扩容直接把阈值设为Integer.MAX_VALUE相当于放弃扩容。这是防止容量溢出做的保护。还有一种情况是构造时指定了初始容量此时threshold被临时用来存容量值第一次put时再通过tableSizeFor方法把它转成2的幂。这个设计有点绕但目的是延迟初始化避免构造时就分配数组。3.2 元素迁移高低位链表的拆分逻辑这是JDK8扩容最精彩的部分。遍历旧数组的每个桶如果是单个节点直接重新计算索引放过去如果是链表或红黑树就拆成两条链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);关键判断是(e.hash oldCap) 0。为什么用oldCap而不是newCap-1因为容量是2的幂oldCap的二进制只有一位是1比如16是0001 0000。hash和它做与运算结果要么是0要么是16。是0的留在原索引是16的移到“原索引16”的位置。这个判断等价于看hash在扩容新增的那一位上是0还是1比重新计算hash (newCap-1)快得多。我第一次看懂这段时真心觉得设计者把位运算玩出花了。3.3 红黑树的拆分TreeNode也逃不过红黑树的迁移逻辑和链表类似也是按(e.hash oldCap)拆成两棵。但多了一步拆分后如果节点数小于等于6会把红黑树退化成链表。这个6和转树的8之间留了缓冲避免在边界反复横跳——如果阈值都是8那么7个节点转树、8个节点退链频繁转换会浪费性能。实操心得如果你在调试时发现某个桶一会儿是树一会儿是链别慌这是正常的动态调整。只有当桶内元素稳定在8以上时树结构才会长期保持。4. get与remove查找和删除的对称设计put看懂了get和remove基本就是反过来走一遍但有几个细节值得单独拎出来说。4.1 get方法的查找顺序final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,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 ((TreeNodeK,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; }查找顺序是先看首节点命中就返回否则判断是树还是链分别走树的查找或链表的遍历。这里同样遵循“先比hash再比引用最后比equals”的原则。有个容易忽略的点key为null时hash为0所以null key总是落在索引0的桶里。这也是为什么HashMap允许一个null key——它被特殊处理了不会抛NPE。4.2 remove的节点删除逻辑removeNode方法比get多了一步删除操作。链表删除时如果是首节点直接tab[i] node.next如果是中间节点需要维护前驱指针if (node p) tab[index] node.next; else p.next node.next;红黑树的删除就复杂多了涉及树的平衡调整源码里调用了removeTreeNode方法。这部分如果展开讲能写一整篇这里你只需要知道红黑树的删除会触发旋转和变色保证树的高度维持在O(log n)。删除后还会判断是否需要把树退化成链表条件和扩容时一样节点数小于等于6就退化。5. 遍历与迭代器为什么不能在for-each里删元素用过HashMap的人多半踩过这个坑在for-each循环里调用map.remove()结果抛ConcurrentModificationException。这个异常来自迭代器的fail-fast机制。5.1 modCount与expectedModCount的博弈HashMap里有个modCount字段每次结构性修改put、remove都会加1。迭代器创建时会记录当前的modCount为expectedModCount每次next()时检查两者是否相等不等就抛异常。if (modCount ! expectedModCount) throw new ConcurrentModificationException();这个机制的目的是尽早发现并发修改而不是等到遍历出错了才报。但它不是线程安全的保证只是尽力而为的检测。那怎么正确地在遍历中删除用迭代器自己的remove方法IteratorMap.EntryString, Integer it map.entrySet().iterator(); while (it.hasNext()) { Map.EntryString, Integer entry it.next(); if (entry.getValue() 100) { it.remove(); } }迭代器的remove方法会在删除后同步更新expectedModCount所以不会触发异常。5.2 三种遍历方式的性能差异遍历方式适用场景性能特点keySet()只需要key每次get都要重新查找最慢values()只需要value直接遍历值较快entrySet()需要key和value一次遍历拿到两者最快我做过一个简单的基准测试遍历10万条数据entrySet比keySet快了将近一倍。原因很简单keySet遍历时每次都要调用get(key)去查找value相当于遍历了两遍。所以除非你确实只要key否则一律用entrySet。6. 线程安全问题HashMap不是并发容器这一点必须单独强调。HashMap的所有方法都没有加锁多线程同时put可能导致数据丢失、size不准甚至在某些极端情况下出现死循环JDK7的头插法扩容。6.1 并发put可能丢数据假设两个线程同时put都算出同一个桶为空于是都执行tab[i] newNode(...)。后执行的会覆盖先执行的先插入的数据就丢了。这不是概率问题是必然会发生的事情。6.2 替代方案怎么选方案特点适用场景Collections.synchronizedMap全表锁性能差并发低图省事ConcurrentHashMap分段锁/CAS性能好高并发首选手动加锁灵活但容易出错特殊需求ConcurrentHashMap在JDK8之后改成了CASsynchronized锁单个桶并发度大幅提升。如果你的场景确实需要并发直接用ConcurrentHashMap别在HashMap上自己加锁坑太多。注意即使只是读多写少只要有一个线程在写其他线程在读就必须用并发容器。因为扩容时数组引用会变读线程可能读到旧数组或null导致数据不一致。7. 几个容易被忽略的源码细节最后分享几个我在读源码时觉得有意思、但容易被跳过的点。7.1 tableSizeFor的位运算技巧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的最小2的幂。原理是把最高位1后面的所有位都填成1最后加1就得到2的幂。比如cap10n91001经过一系列移位或运算变成111115加1得16。这个技巧在很多需要对齐的场景都能用值得记住。7.2 为什么Node的hash字段是final的Node类里final int hash一旦创建就不能改。因为hash值决定了节点在数组中的位置如果允许修改整个结构就乱了。key也是final的同理。这体现了HashMap设计上对不可变性的依赖——key最好用不可变对象比如String、Integer否则改了key的字段会导致再也找不到这个entry。7.3 序列化时的特殊处理HashMap实现了Serializable但table数组被标记为transient不直接序列化。它自定义了writeObject和readObject方法只序列化键值对反序列化时重新构建数组。这样做是为了节省空间——数组里大量null没必要存而且反序列化后重新计算hash分布更均匀。我在实际项目中遇到过序列化HashMap后反序列化发现桶的顺序变了一开始以为是bug后来才明白这是正常行为。如果你依赖遍历顺序千万别用HashMap用LinkedHashMap。7.4 初始容量给多少合适如果你能预估数据量创建HashMap时直接指定初始容量避免反复扩容。计算公式是初始容量 预期元素数 / 0.75 1。比如预计存100个元素100/0.75≈133取134或直接给128再让它扩一次也行。但注意tableSizeFor会自动向上取2的幂所以给100最终也是128。我见过有人为了“保险”直接给10000结果只存了10个元素白白浪费内存。容量给太大扩容是省了但数组本身占的空间也不小权衡一下。读HashMap源码这件事第一遍晕第二遍有点感觉第三遍才能体会到那些位运算和边界条件背后的良苦用心。我自己的习惯是每读一段就问自己“如果让我设计我会怎么做”然后对比源码往往能发现自己的思路要么有性能问题要么有边界漏洞。这种对比式阅读比单纯背诵结论有效得多。