写HashMap写了快十年，从JDK 1.6一路用到现在的JDK 17，每次面试候选人我都会从HashMap切入，因为它真的太能反映一个人的Java基本功了。数组、链表、红黑树、哈希、位运算、扩容、并发安全、Fail-Fast机制，这些知识点在全景图里几乎是绕不开的硬骨头，而HashMap这个数据结构把它们全串在了一起。很多刚入行的朋友一提HashMap就是背八股，源码也看过，但一问到"为什么加载因子是0.75""为什么数组长度一定要是2的幂""JDK 1.8为什么从头插改成尾插"，就支支吾吾了。
这篇博文我打算换个讲法：不按说明书式的顺序把源码贴一遍，而是从"HashMap到底在解决什么问题"出发，把设计思路、核心机制、并发隐患、高频面试题和实际开发中的坑串起来，讲清楚每个关键决策背后的"为什么"。无论你是刚学Java的新手，还是准备跳槽刷面试题的选手，或者工作中被线上OOM和HashMap分配不均折磨过的老哥，这篇都能给你一点参考。
1. 先聊清楚：HashMap到底解决什么问题
1.1 从数组和链表说起
Java集合框架里，最基础的两个数据结构就是数组和链表。数组在内存里是一段连续空间，通过下标访问的时间复杂度是O(1)，这点依靠硬件寻址几乎不消耗额外计算；但它的短板也很明显——插入和删除需要整体搬移元素，最坏情况下是O(n)，而且创建时就得指定大小，动态扩容要复制整个数组。
链表则刚好反过来，节点之间通过引用相连，插入和删除只需要改前后的指针，代价是O(1)；但查询某个元素时必须从头节点一个一个往后找，平均时间复杂度是O(n)，数据量一大性能就崩。
HashMap的核心设计目标，就是想用"哈希"这个手段把两者优势结合起来：用哈希函数把key映射到一个数组下标，实现"查找接近O(1)"的效果，同时用链表或红黑树来处理不同key映射到同一个下标的情况。用生活里的例子类比，数组就像酒店前台的一张长桌子，上面固定摆了几十本登记册；哈希函数就是告诉你"拿房号除以册数取余数，去第几本册子查"；如果两个人分到了同一本册子，那就翻册子里的小纸片，一张一张比对房号名字。这个"翻纸片"的行为就是链表查找。
1.2 整体设计：数组、链表、红黑树怎么配合
HashMap 1.8版本的底层结构是一维数组加链表加红黑树。数组的每个格子叫桶（bucket），默认大小是16。key进入HashMap后，先通过扰动函数计算出一个hash值，再根据hash值定位到具体桶位置。桶里如果只有一条数据，查询就是O(1)；如果发生过哈希冲突，桶里存的是一个链表，查询需要沿着链表逐一遍历，时间复杂度变差。
当链表长度达到8，并且当前数组容量大于等于64时，链表会转换成红黑树。为什么是8而不是其他数字？源码注释里给出了一个基于泊松分布的计算：在随机哈希的情况下，一个桶里链表长度达到8的概率大约是千万分之六，这个概率已经低到可以当成"不可能发生"的事件。也就是说转红黑树其实是一种极端情况下的兜底策略，防止恶意构造哈希或糟糕的hashCode把HashMap退化成一个纯链表。红黑树是自平衡二叉查找树，插入、删除、查找的时间复杂度都是O(log n)，即使真出现大量冲突，性能也不会彻底崩掉。但红黑树节点占用的空间大约是普通链表节点的两倍，所以当红黑树节点数少于6时，又会退化成链表，避免不必要的空间浪费。这里阈值的"8"和"6"之间留了缓冲，防止在边界上频繁转换，这个设计在实际工程里也经常被借鉴。
2. 核心机制拆解：hash、put、扩容、get的源码逻辑
2.1 hash值的计算：为什么右移16位再异或
HashMap在计算key的哈希时，并不是直接用key.hashCode()的结果，而是做了一次扰动处理。1.8版本的代码长这样：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }这里把hashCode的高16位和低16位做了一个异或运算。为什么要多此一举？关键在于HashMap定位桶时用的是(n - 1) & hash这个操作，其中n是数组长度。如果数组长度是16，那么n - 1的二进制是0000 0000 0000 1111，与hash做按位与，实际上只有低4位参与了运算，高28位就被浪费了。这意味着如果两个key的hashCode在高位完全不同、但低位恰好一样，它们就会落到同一个桶里，冲突率会明显上升。
右移16位再异或，本质上是把高16位的信息"混入"低16位，让高位影响低位，减少碰撞。这也是为什么这个方法叫"扰动函数"。我自己在写业务代码时，自定义对象的hashCode方法也会注意这一点，别只把关键字段的低位特征映射进去，尽量让hash值在高位也有区分度，否则一旦HashMap扩容或者数据量变大，碰撞概率会急剧上升。
2.2 put流程全解析：从hash到插入的每一步
HashMap的put方法在1.8版本中，整体流程可以拆成以下几个关键步骤：
- 判断table是否为null或者长度为0，是则先执行resize()初始化，默认容量16。
- 根据hash值计算索引
i = (n - 1) & hash，取出tab[i]。 - 如果tab[i]为null，说明桶是空的，直接newNode插入。
- 如果tab[i]不为null，先判断key是否equals，相等则直接替换value。
- 否则判断tab[i]是否为TreeNode，是则走红黑树的插入逻辑。
- 否则就是普通链表，遍历链表，如果找到相同key就替换，如果在链表末尾还没找到，就在尾部追加新节点。
- 追加完成后判断链表长度是否超过树化阈值8，如果超过并且数组容量>=64，调用treeifyBin把链表转成红黑树。
- 插入完成后，判断++size是否超过threshold，超过则扩容。
这里有个容易忽略的细节：hash冲突时先比较的是引用 **==，再比较的是equals。源码里是if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))。先看hash值是不是一样，这个O(1)就能判断，如果hash都不一致，基本可以排除同一个key（虽然理论上hash一致时还要equals确认）。这种短路式的判断方式，在链表比较长的场景下可以省掉很多equals调用，因为hash值不同的对象根本不可能equals相等（前提是hashCode实现遵守约定）。
2.3 扩容机制：为什么要设计成2次幂
扩容是HashMap里最耗性能的操作之一。当元素个数超过threshold = capacity * loadFactor时，数组会扩大为原来的2倍，然后所有元素都要重新计算桶位置，这个过程叫rehash。
为什么容量一定要是2的幂？核心原因是定位操作(n - 1) & hash只有在n是2的幂时，才能做到和hash % n等价但性能更高。而且，当n翻倍时，某个元素在新数组中的位置只有两种情况：保持原索引，或者原索引+oldCap。为什么会这样？看一个例子：假设oldCap是16，hash是某个值，那么hash & (16 - 1)取的是hash的低4位；扩容后n变成32，hash & (32 - 1)取的是hash的低5位。多出来的那一位，如果hash的第5位是0，位置不变；是1，位置就变成原索引+16。所以1.8里resize过程不需要重新计算每个元素的hash值，只需要看原来hash值的第5位是0还是1，这个判断用(e.hash & oldCap) == 0一次位运算就搞定了，效率非常高。
1.7版本的扩容需要从头到尾重新计算hash并重新插入，性能差而且容易出并发问题。1.8优化成基于旧hash的高位判断，堪称一次教科书级别的位运算优化。
2.4 get和remove：HashMap如何高效取数据和删数据
get的逻辑相对简单：计算hash，定位桶，如果第一个节点就是目标key，直接返回；否则判断是不是树节点，是就走红黑树查找，不是就遍历链表。这段源码看起来没有太多坑，但有一点值得注意：HashMap允许key为null，null的hash值固定为0，所以null key永远放在table[0]这个桶里。
remove的核心是removeNode方法，逻辑比get多一步——找到节点后要处理链表的删改。如果删除的是链表中间节点，只需把前一个节点的next指向被删节点的next；如果是红黑树节点，则走红黑树的删除逻辑并伴随自平衡操作。日常开发里，我自己很少直接用迭代器边遍历边删除，容易抛出ConcurrentModificationException，更推荐用map.entrySet().removeIf(...)这种基于迭代器封装的删除接口，从底层看它正确维护了modCount，不会触发Fail-Fast机制。
3. 并发场景下的HashMap：为什么它不安全，以及如何应对
3.1 线程不安全的根源：丢更新、扩缩容竞态
HashMap在多线程环境下会出问题的原因有很多，最直观的是数据覆盖。两个线程同时put key，同时定位到同一个空桶，然后各自newNode并赋给tab[i]，最终只有一个节点的引用被保留，另一个线程的数据悄无声息地丢了。这还不是最可怕的，最严重的是扩容和并发put交叉执行时，链表结构可能被破坏，进而导致get访问到不存在的节点，甚至直接死循环。
有人会问，加个HashTable不就完事了？HashTable把所有方法都加了synchronized，锁的是整个table，任何读写操作串行执行，并发性能非常差。而HashMap本身不保证线程安全，所以它更适合单线程场景下的高效读写。如果明确有并发需求，应该考虑ConcurrentHashMap，而不是给HashMap方法级加锁。
3.2 经典事故：JDK 1.7头插法引发的死循环
再提一个Java面试和社区里被讲烂的案例：JDK 1.7的HashMap在并发扩容时，可能出现链表环状结构，导致get操作在遍历链表时永不终止，CPU飙满。根因是1.7扩容时采用头插法转移链表节点，转移过程中链表顺序会反转。
举个例子，原本链表的顺序是A -> B -> C，线程1和线程2同时扩容。当线程1执行完某个步骤后被挂起，线程2完成了完整的rehash，链表顺序变成了C -> B -> A。线程1恢复后，在新链表基础上继续转移，因为头插法的原因，A.next指向B，但B.next已经被线程2改成了A，于是形成了A -> B -> A循环。之后任何一次get走到这个链表，就会在里面转圈。
1.8版本改成尾插法，新节点追加到链表尾部，扩容时保持原有链表的相对顺序，从根源上避免了循环链表的形成。这也是很多人被问到"为什么1.7到1.8的头插改尾插"时给出的标准答案。但注意，1.8的HashMap在并发下仍存在数据丢失、size统计不准等问题，它依然不是线程安全的。
3.3 并发替代方案怎么选
并发环境下我一般直接上ConcurrentHashMap。1.8的ConcurrentHashMap抛弃了1.7的Segment分段锁设计，改用CAS + synchronized，锁粒度细化到单个桶。put时，如果桶为空，通过CAS直接把节点放入，不抢占锁；如果桶非空，对桶中的头节点加synchronized，保证同一桶内操作串行，但不同桶之间互不阻塞，并发度大幅提升。
如果只是需要弱一致性的缓存场景，也可以考虑Collections.synchronizedMap包一层，但效率低，一般只在读多写少的简单场景里过渡用。总之，记住一句话：没有并发需求用HashMap，有并发需求看场景选ConcurrentHashMap，别拿HashTable，也别自己手工加全局锁模仿那个效果。
4. 实际开发中经常踩的坑：HashMap使用习惯纠正
4.1 初始容量和扩容开销的账
很多人在写代码时习惯直接new HashMap<>()，也不管可能存多少数据，等元素多了触发扩容，才发现性能不对。扩容是一个重操作，要创建新数组，还要把原有元素全部rehash。如果业务场景里HashMap会存上万条数据，建议创建时直接指定容量。
但指定容量也有讲究。比如你确定会存1000条，直接new HashMap<>(1000)，够吗？不够。因为HashMap在元素数量达到capacity * 0.75时就会扩容，容量1000的map，存到750条时就触发了扩容，实际扩容后的容量变成2000左右。你预期的1000容量其实被浪费了一半。更合理的是new HashMap<>(1000 / 0.75F + 1)，也就是大约1334向上取2的幂，最后实际容量是2048，这样存1000条数据时不会触发中间扩容。这个公式网上传得很广，但很多人不知道背后的原因，这里补一句解释：HashMap构造时并不会马上分配大数组，它会在第一次put时根据initialCapacity计算threshold，threshold = capacity * loadFactor，只有元素数量超过threshold才扩容。
4.2 自定义对象作为Key时，equals和hashCode的约定
面试里常问"为什么重写equals必须重写hashCode"。放到HashMap场景里理解最直观：HashMap先通过hashCode定位桶，再用equals验证是否同一key。如果两个对象equals相等但hashCode不同，它们会被定位到不同桶，HashMap会认为它们是两个不同key，产生重复存储；反过来，如果hashCode一样但equals不等，它们会落在同一桶里，链表变长，性能下降。
所以在设计自定义Key类时，我会遵守三条准则：
- 为什么字段参与equals，就参与hashCode，且hashCode计算要包含这些字段。
- 如果对象创建后key的字段会变化，不要拿来当HashMap的key。因为哈希值变了，原桶位置对不上了，get的时候必然找不到。这块最好的实践是使用不可变对象，比如String、Integer，或者把自定义类设计成不可变。
4.3 遍历方式的性能差异和删除陷阱
HashMap的遍历方式有好几种：keySet()然后get、entrySet()、forEach（JDK 1.8的BiConsumer）。keySet()只拿到key的Set，如果你想同时拿value，还需要再get一次，这意味着又做了一遍哈希定位，二次开销。而entrySet()一次遍历拿到所有键值对，性能最好。
删除元素时，如果直接在for-each循环里调用map.remove(key)，会触发ConcurrentModificationException，因为remove操作把modCount改了，但迭代器不知情。解决办法是用迭代器的remove，或者用1.8新增的map.entrySet().removeIf(entry -> ...)，后者代码更简洁。这条规则同样适用于List，我就见过不止一个同事在线上因为for-each里remove抛异常。
4.4 不同Map的选型：别只会HashMap
| 实现类 | 是否有序 | 线程安全 | 底层结构 | 典型场景 |
|---|---|---|---|---|
| HashMap | 无序 | 否 | 数组+链表+红黑树 | 大多数默认场景 |
| LinkedHashMap | 按插入顺序或访问顺序 | 否 | HashMap基础上加双向链表 | 实现LRU缓存 |
| TreeMap | 按key的自然顺序或比较器排序 | 否 | 红黑树 | 需要排序、范围查找 |
| HashTable | 无序 | 是 | 数组+链表（全表锁） | 已经不推荐使用 |
| ConcurrentHashMap | 无序 | 是 | 数组+链表+红黑树（CAS+synchronized） | 并发读写的首选 |
这里单独说下LinkedHashMap。它继承了HashMap，但在每个节点上额外维护了前后指针，形成一个双向链表，所以它天然支持按插入顺序遍历。更妙的是它有个removeEldestEntry方法，重写这个方法就能实现一个最简单的LRU缓存，这个技巧在面试中经常被考察。
4.5 从HashMap看JVM层的内存和类加载异常
热搜词里有一条Uncaught exception java.lang.NoClassDefFoundError: java/applet/Applet，虽然这个异常本身和HashMap没直接关系，但值得说明一点：HashMap是JDK自带的类，如果运行环境里出现NoClassDefFoundError，通常是类路径配置错误、JDK模块化裁剪导致某些类不存在，或者Agent/Lombok等字节码工具干扰了类加载。遇到这种问题，第一步不是去看HashMap源码，而是检查JDK版本和启动参数，再用-verbose:class看具体是哪个类加载失败。
另一个和HashMap相关的JVM问题是内存占用。假设你往HashMap里存了几十万个复杂对象，并且key的hashCode分布极度不均，导致红黑树特别多，节点对象本身会占用大量内存，再加上数组扩容后的未使用桶位也占据空间，堆内存压力就上来了。实际排查OOM时，除了用jmap dump堆外，也要留意是不是HashMap的加载因子被调得过高或过低，导致扩容过度或者链表过长。
5. 面试高频考点：HashMap八股速成与延伸思考
5.1 JDK 1.7和1.8的对比总结
面试官最喜欢问的一句话就是"聊一下HashMap底层"。但真正的加分点在于你能说出版本演进。
| 对比项 | JDK 1.7 | JDK 1.8 |
|---|---|---|
| 数据结构 | 数组+链表 | 数组+链表+红黑树 |
| 树化阈值 | 无 | 链表长度>=8且数组长度>=64 |
| 哈希扰动 | 4次位运算+5次异或 | 1次异或（右移16位） |
| 链表插入方式 | 头插法 | 尾插法 |
| 扩容后重哈希 | 重新计算hash | 通过(e.hash & oldCap)判断新位置 |
| 并发问题 | 扩容时可能形成循环链表 | 仍不安全，但不会因扩容死循环 |
另外，1.8源码中引入红黑树后，把原来1.7里为了哈希分布而做的复杂扰动函数简化了，因为即使hash分布稍微差一点，冲突也可以用红黑树兜底，这一取舍很多资料没细说，面试时提出来会显得你真的读过源码。
5.2 高频追问与回答思路
我整理了面试中关于HashMap的几组连续追问，并给出简要回答思路，建议你把它当成一个思维导图来记忆：
问：HashMap的哈希函数为什么用异或而不是直接取模？
答：数组长度是2的幂，(n - 1) & hash和取模等价，但位运算更快；而hash值先和高位异或后，可以让高位的特征也参与低位定位，降低碰撞概率。
问：为什么加载因子是0.75而不是0.5或1.0？
答：这是空间和时间的一个折中。太大会导致哈希冲突增多，链表过长；太小会导致频繁扩容，浪费空间。0.75是JDK官方在大量测试后给出的默认值，兼顾两者。
问：链表什么时候会转红黑树？
答：链表长度达到8，并且数组容量达到64。如果数组长度小于64，即使链表超过8，也只会扩容而不是树化，因为扩容之后链表位置重新分布，问题可能自然解决。
问：为什么不直接用红黑树替代链表？
答：链表节点占用的内存更小，插入性能更好；红黑树节点更占内存，维护平衡有额外开销。哈希碰撞在正常情况下的概率很低，没有必要常态使用红黑树。
问：HashMap扩容时，数据是怎么迁移的？
答：遍历旧表的每个桶，对桶内元素按是否(e.hash & oldCap) == 0拆分成两部分，一部分留在原索引位置，一部分移到原索引 + oldCap，依次尾插到对应链表。
这些回答其实不需要死记硬背，只要能理解底层原理，每个人都可以用自己的话复述出来。怕的就是只背结论不问原因，面试官一旦深挖就露馅。
5.3 一道简单的实操验证题
如果你也想验证自己对HashMap的理解，可以试试这个练习：写一个类，重写hashCode方法，让它永远返回同一个值（比如1），然后用这个类的对象作为key，向HashMap循环put一万条数据，观察它的性能和数据分布。再改成用String作为key，对比两者的put耗时。我当年做这个实验时感受非常直观——一个糟糕的hashCode可以让HashMap的性能直线下滑，这就是为什么工程上要求hashCode尽量分散。
6. 最后再分享一点实际开发中的体会
做了这么多年Java，我越来越觉得HashMap是所有集合框架里最值得反复研读的一个类。它不只是一个会用就行的数据结构，更像一本浓缩的Java入门教材——位运算、hash设计、链表操作、树化退化、扩容策略、Fail-Fast机制，每一个概念都能在里面找到落点。如果你能把HashMap的源码逻辑完整讲清楚，基础题这一关基本就稳了。
实际开发过程中，我给自己定了一条规矩：凡是能预估数据量的场景，初始化时就指定容量；凡是自定义对象要做key，先确认hashCode和equals是否规范且对象不可变；凡是有并发入手的可能，直接用ConcurrentHashMap，绝不贪图一时方便。这些小习惯看起来不起眼，但等到线上真出了性能事故再去排查，代价往往是几个小时的脑细胞和一堆日志。
如果这篇文章里的某个点帮你解决了一个bug，或者让你在下次面试时多了一句"因为数组长度是2的幂，所以可以用(n - 1) & hash代替取模"，那就值了。HashMap还有很多可以深挖的细节，比如扰动函数的具体位运算、红黑树的左旋右旋过程、TreeNode的split逻辑，感兴趣的话后续可以再单独写一篇深入源码的文章，到时候我们继续聊。
