写了不少年Java，HashMap的源码翻过好几遍，也面过不少人。问一句“HashMap是什么”，几乎都能答上来“数组加链表，红黑树优化”。但再往下问一句：“你往HashMap里put一个key-value，这一个键值对到底是怎么存进去的？”能答完整的人，明显少一截。大多数人的认知停在“算个hash，放数组里”，再往下就说不清了。

这篇文章就把一次put过程从头到尾拆开。不是背结论，而是跟着JDK源码的逻辑走一遍“一个key-value键值对保存的完整过程”，顺便把为什么这样设计、哪些地方容易踩坑讲清楚。适合正在准备面试的开发者，也适合用HashMap写了几年业务代码、却从来没打开过源码的人。

1. 一次put()调用，JDK到底在忙些什么

1.1 先看整条时间线

以JDK 8为例，调用一次map.put(key, value)，底层走的是putVal方法。整个过程可以压缩成下面这条链路：

1. 对key调用内部的hash()方法，做一次扰动计算；
2. 用(n - 1) & hash算出桶下标，n是当前数组长度；
3. 如果数组还没初始化（table为null或长度为0），先触发resize()扩容方法来建数组；
4. 检查算出来的下标位置上有没有节点：没有，直接new一个Node放进去；
5. 有节点，说明发生了哈希冲突，进入冲突处理流程；
6. 冲突处理完，插入新节点之后，判断是否需要扩容；
7. 更新size和modCount，返回旧值或null。

这七步，就是一个key-value从内存落到HashMap里的全部动作。别急着背，每一步背后都有选择和理由，下面按顺序拆。

1.2 为什么会是“数组+链表+红黑树”三件套

先解释底层结构，不然后面的流程看不懂。

HashMap的底层主体是一个Node<K,V>[] table数组，每个数组下标对应一个“桶”。理想的哈希表是每个桶只有一个元素，这样查询时一步就能定位到目标，时间复杂度O(1)。但不同key算出来的下标可能撞到一起，这就是哈希冲突。解决冲突，HashMap选的是“链地址法”：同一个桶下面挂一条链表，新来的冲突节点链到链表上。

链表本身有个问题，节点多了之后，查找链表是线性遍历，复杂度O(n)。极端情况下，所有key都哈希到同一个桶，HashMap直接退化成一条大链表，性能雪崩。早期版本确实出现过这种被恶意构造输入打垮的场景。JDK 8的解法是引入红黑树：当链表长度膨胀到一定程度，就把链表转成红黑树。红黑树是自平衡二叉查找树，增删查都是O(log n)，性能比链表稳定得多。

所以“数组+链表+红黑树”，本质是三个层面的兜底：数组保证理想情况下的O(1)，链表解决冲突，红黑树防止冲突恶化。理解了这一层，再去看put过程，整个逻辑就通了。

2. 从key到桶下标：hash()扰动与(n-1)&hash

2.1 hash()里那行“异或”写的到底是什么

很多人以为map.put直接拿key.hashCode()去算下标，其实不是。JDK 8里的hash方法长这样：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

关键就是最后那个异或：key.hashCode()的结果是32位int，把它右移16位，再和原来的hashCode异或。这一操作俗称“扰动函数”。目的是让hashCode的高16位信息也能参与到低位计算里来。

为什么需要扰动？因为HashMap算下标用的是(n - 1) & hash，数组长度n是2的幂，n - 1的二进制全是低位1。比如默认容量16，n - 1 = 15，二进制是0000 0000 0000 0000 0000 0000 0000 1111。hash跟15做与运算时，只有最低4位起作用，高位信息几乎是白算的，全都丢了。

假设一个对象的hashCode是0x12345678，不扰动时，hash的低4位是1000，算出来的下标是8。扰动之后，先取高16位0x1234，和原值异或得到一个新值，这个新值的低4位变了，算出来的下标也变了。相当于把table容量不够时“用不到”的高位信息，通过异或揉进低位，让分布更均匀。

JDK 7的扰动函数更复杂，做了四次位移和异或。JDK 8简化成一次，原因很简单：树化之后，链表碰撞严重的情况有红黑树兜底，不需要再用更复杂的扰动拉低分布偏差。一次异或性价比最高，计算速度快，效果也够用。

2.2 (n-1)&hash为什么能代替取模

拿到扰动后的hash，怎么确定桶下标？HashMap用的是i = (n - 1) & hash，而不是常见的hash % n。

这两种方式在n是2的幂时完全等价。举个例子，n=16，hash=18，18 % 16 = 2，18 & 15的结果也是2。原因在于，n是2的幂时，n - 1的低位全是1，和hash做与运算，本质上就是取hash的低log2(n)位，这和取模的效果一模一样。

那为什么不用取模？位运算直接操作二进制，CPU一条指令就出结果，取模则要走除法或求余运算，慢得多。HashMap是高频数据结构，每次put和get都要算下标，这个微小的性能差距被放大之后就很可观。

这也是HashMap要求容量必须是2的幂的原因。你构造HashMap时传一个不是2的幂的初始容量，它内部也会通过tableSizeFor方法把它调整成大于等于传入值的最小2的幂。选2的幂不只是为了位运算快，还有一个更重要的原因，扩容时能优雅地判断节点去留，这个到第5章讲扩容再看。

3. 桶还不存在：首次put触发的初始化与默认参数

3.1 懒加载：table为null时才resize

第一次往HashMap里put键值对时，底层数组其实是空的。不像某些集合在构造时就把数组建好，HashMap用的是懒加载策略：构造时可以只存参数，不占用内存；真正的Node数组，在你第一次put时才创建。

看putVal开头的代码：

if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;

table为null或长度为0，说明数组还没建，直接调用resize()。这个方法一会儿负责初始化数组，一会儿负责扩容，是HashMap里最核心的方法之一。

懒加载的好处很明显：只new一个HashMap但不放数据的话，几乎不占堆内存。尤其在高并发场景下，很多容器会预先创建一堆HashMap备用，如果没有懒加载，一堆空数组白占内存，浪费得很。

3.2 第一次resize里发生了什么

进入resize()时，因为oldTab是null，oldCap和oldThr都是0，会走这段逻辑：

else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); }

DEFAULT_INITIAL_CAPACITY是16，DEFAULT_LOAD_FACTOR是0.75，所以第一次resize会创建一个长度为16的Node数组，同时把新的扩容阈值newThr设为16 * 0.75 = 12。

这个12不是数组长度，是“扩容阈值”。意思很简单：HashMap里存的键值对数量达到12个之后，下一次再插入就可能触发扩容。为什么不等到数组装满了16个再扩？因为数组永远不会让你装满。哈希冲突是必然存在的，如果真等到16个全占满，链表已经长到没法看了，查询性能早就崩了。所以要留出一部分空桶来降低冲突概率。

如果你是用有参构造创建的HashMap，比如new HashMap<>(32)，情况略有不同。构造方法会先把容量调整成2的幂，存到threshold字段里。第一次resize时会走else if (oldThr > 0)分支，用这个值作为newCap，再根据容量算出新的threshold。理解这个细节后，调试自定义初始容量的HashMap时就不会一头雾水。

3.3 负载因子0.75这个数字有什么讲究

负载因子是HashMap最常被问到的参数之一。threshold = capacity * loadFactor，它决定了HashMap什么时候扩容。

为什么默认值是0.75而不是0.5或者1？这是时间成本和空间成本的一个折中。负载因子调低到0.5，碰撞少、查询快，但相同数量的数据占用的内存接近翻倍，扩容也更频繁。负载因子调到1，空间利用率接近100%，但冲突概率明显上升，链表变长，查询性能下降。0.75这个值，是JDK作者在大量场景下平衡出来的一个经验值，对绝大多数应用来说，够用且安全。

源码注释里还给过一个更数学的解释：在负载因子0.75和默认容量16的情况下，单个桶内链表长度达到8的概率用泊松分布算出来大约是千万分之六。也就是说，正常情况下链表根本长不到树化的长度。一旦真的长到那个程度，说明hash分布出了大问题，这时候要么转红黑树，要么通过扩容把链表重新打散，这个逻辑在第4章会细讲。

4. 冲突之后：链表遍历、尾插、树化与覆盖规则

4.1 索引处的桶为空：直接new Node

算好下标之后，putVal会检查这个位置：

if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);

如果数组的这个下标位置是空的，说明没有冲突，直接创建一个Node节点放进去。Node节点内部存四样东西：hash值、key、value、指向下一个节点的next引用。

这是put过程里最理想的情况，一次定位、一次写入，时间复杂度O(1)。日常业务中大部分put都走这条路径，所以HashMap的平均性能才能维持在O(1)。

4.2 桶不为空：先判断是不是树

如果下标位置已经有节点，说明桶被占了，进入冲突处理。首先要看这个桶现在是链表结构还是红黑树结构：

else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

p是数组下标处的第一个节点。instanceof TreeNode判断的是这个节点是不是红黑树节点。如果是，说明这个桶之前已经经历过树化，此时直接走红黑树的插入逻辑putTreeVal，按红黑树的规则找位置插入，并返回可能存在的旧值。

4.3 链表上的“找key”逻辑与equals/hashCode联动

如果桶还是链表结构，就进入for循环遍历链表。这段遍历有一个关键判断：

if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;

翻译过来：遍历链表上的每个节点，先比hash值，再比较key是否相等。==比较的是引用，equals比较的是内容。两个条件都要满足，才认为“找到了同一个key”。

这里藏着HashMap最基本的一条规矩：重写equals方法时，必须重写hashCode方法。因为HashMap是“先比hash，再比equals”来确认key是否相同的。如果两个逻辑上相等的对象，hashCode返回不同的值，那它们在HashMap里会被分到不同的桶，equals判断根本轮不到执行。反之，就算hashCode相同，equals不相等，也只是冲突，可以共存。这也是为什么hashCode相同的两个不同对象能安稳地存在同一个桶里，不影响正确性，只会影响查询效率。

链表遍历过程中还有个细节：如果一直找到链表末尾都没发现相同key，说明这是个新key，直接尾插：

if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); ... break; }

注意JDK 8用的是“尾插法”，新节点挂在链表尾部。JDK 7用的是“头插法”，新节点插在头部。这个区别，到第5章讲扩容死循环时还要再提。

4.4 树化的双重条件：8和64缺一不可

链表尾插完之后，有一段特别容易被误读的逻辑：

if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);

TREEIFY_THRESHOLD是8，binCount是链表遍历时的计数器。这段代码的意思，大致就是“这个桶的链表长度膨胀到一定程度，尝试转红黑树”。但很多人不知道，treeifyBin方法进去之后还有个二次判断：

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // 真正转红黑树的逻辑 }

MIN_TREEIFY_CAPACITY是64。也就是说，链表长度达到8时，并不会立刻转树，而是先看整个数组的长度。如果数组容量还不到64，先扩容，而不是树化。

为什么会有64这个门槛？红黑树的节点比普通链表节点大得多，转换本身有成本。如果数组容量很小却发生了严重碰撞，大概率不是一个key的问题，而是整个数组太小、冲突整体偏高。这时候扩容能把所有桶的链表重新打散，成本比单独把某个桶转树低得多，效果也好得多。

这个双重条件，面试时能说出来，基本就能证明你是真看过源码而不是背了概念。

4.5 put同一个key：旧值怎么被覆盖

刚才的遍历和插入逻辑里，一旦找到了已经存在的相同key，就会跳出循环，此时e指向链表里那个旧节点，然后执行：

if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }

默认情况下，新value直接覆盖旧value，然后把旧value返回。这就是put()方法返回值由来：第一次put一个key时返回null；再次put同一个key，返回上一次存的value。

有两处细节容易被忽略。

一是onlyIfAbsent，这是putIfAbsent方法传入的标志。如果为true，只有在当前value为null时才覆盖。可以把它理解成“有值就不动，没值才写入”。

二是afterNodeAccess(e)，这个方法是空实现，专门留给LinkedHashMap重写的。LinkedHashMap靠它来维护访问顺序。这也是HashMap面向扩展的设计方式，基类留钩子，子类实现自己的逻辑。

5. 一个键值对放完之后：记账、计数与扩容预兆

5.1 modCount在记什么

键值对真正落进桶里之后，putVal还要做两件“记账”的事。先看这段：

++modCount; if (++size > threshold) resize();

modCount是“结构修改次数”，记录的是HashMap被结构性修改了多少次。新增节点、删除节点、扩容、链表转树，都是结构性修改。但注意，用put覆盖一个已存在key的value不算结构性修改，只是替换旧值，节点的增删没变。

modCount主要给迭代器用。如果在迭代HashMap的过程中，有其他线程put或remove改变了结构，modCount就会变，迭代器下一次检查时会发现不一致，直接抛出ConcurrentModificationException。这是fail-fast机制的体现，目的是尽早暴露并发修改问题，而不是让程序带病运行。

5.2 threshold：触发扩容的那根线

size表示当前HashMap里实际存了多少个键值对。每插入一个，size加1，然后和threshold比较。threshold是容量乘以负载因子得到的值。

用默认参数举例：容量16，threshold=12。当size从12变成13时，13 > 12成立，触发扩容。注意是“大于”才扩，等于12的时候还在容忍范围内。

很多人会在这里产生一个疑惑：我明明还有4个空桶，为什么就扩容了？因为空桶是留给冲突缓冲的。负载因子0.75就是为了保留这25%的余量。如果业务数据量刚好卡在threshold附近，HashMap会频繁扩容，这时候就有必要在初始化时把容量调大一点，第6章会专门说这个坑。

5.3 扩容后每个节点怎么移动：e.hash & oldCap

真正扩容时，resize()会把数组长度翻倍（仍然是2的幂），然后把旧数组里的每个节点重新安置到新数组里。

JDK 7的做法是重新计算每个节点的hash并重新取模，JDK 8做了一个很聪明的优化：直接用e.hash & oldCap判断节点去留，不需要重算下标。

原理是：扩容时数组长度从oldCap变成2 * oldCap，n - 1这个掩码会多出一个高位1，而这个高位恰好就是oldCap。判断一个节点在新数组里是留在原位还是搬到原位加oldCap，只需要看hash的这个对应高位是0还是1。e.hash & oldCap结果非0，说明这个高位是1，新下标等于原下标加oldCap；结果是0，说明高位是0，留在原位。

举个例子，旧容量16，某个key的hash是18，旧下标是18 & 15 = 2。扩容后容量32，新下标是18 & 31 = 18，恰好是2 + 16。如果用18 & 16算，结果是16，非0，结论同样是“搬到2 + 16”。整个过程只做一次位运算，比重新取模快得多，而且一条链表会被拆成两条，分布在两个桶里，原先拥挤的链表自然变短。

JDK 8在迁移时还通过loHead、loTail、hiHead、hiTail这组指针把链表节点分成高低两条链，保持了节点相对顺序。这个顺序保证在JDK 8里非常重要，因为尾插法依赖链表的稳定性。

5.4 老版本死循环问题与并发场景的结论

聊到这里，绕不开那个著名的历史坑：JDK 7在多线程并发put时，扩容过程中可能产生环形链表，一个线程在get时遍历到环上，CPU直接飙满，进程看起来就是“死循环”。

问题根源在JDK 7用的是头插法。扩容迁移链表时，每处理一个节点就把它头插到新链上，导致链表方向反转。多个线程同时迁移同一条链表时，互相覆盖引用，就可能把链表的next指针弄成环。JDK 8改成尾插法，迁移时维持原链表顺序，环形链表的问题在结构上被解决了。

但要泼一盆冷水：JDK 8的HashMap依然不是线程安全的。并发put时，两个线程同时命中同一个空桶，各自new Node往同一个位置写，后写的会覆盖先写的，数据丢失；两个线程同时触发resize，扩容竞争同样会丢数据。所以说，“JDK 8解决了死循环，所以并发可以用HashMap了”这个说法是错的。并发场景老老实实用ConcurrentHashMap，HashMap的设计定位从来就不是线程安全。

6. 把源码走通之后，我实际踩过的坑

6.1 自定义key的hashCode翻车

把对象作为key时，最容易出问题的就是hashCode。

我以前在某个模拟项目里，用内部定义的“订单对象”做key，图省事没重写hashCode，只重写了equals。代码跑起来发现，new了两个内容完全相同的订单对象，第一次put进去，第二次get却返回null。查了半天才反应过来：两个对象默认的hashCode是基于内存地址生成的，根本不相同，HashMap把它们算到了不同的桶，equals根本没有执行的机会。

正确的做法是，重写equals的同时，一定重写hashCode，而且hashCode的计算字段要和equals比较的字段保持一致。比如订单对象用订单号判断相等，hashCode也应该基于订单号生成。这样逻辑上相等的对象，hashCode才可能相等，先hash再equals的判断链路才能走通。

6.2 容量设成1000还是扩容了

另一个常见的坑是初始化容量设得“刚刚好”。

业务估算要放1000个键值对，很自然地写下new HashMap<>(1000)，觉得不会扩容。但实际跑起来，超过768个数据就扩容了一次，debug一看threshold，傻眼了。

原因在前面讲过：有参构造传入1000，tableSizeFor(1000)会把容量调整到1024，这是2的幂。然后threshold =1024 * 0.75 = 768。也就是说，HashMap认为768个键值对已经是“该扩容”的临界点了，因为数组的75%已经被占用，再装下去冲突会明显变高。

如果业务明确知道要放1000个数据，又想避免扩容，初始化容量至少得按预计数据量 / 负载因子来传，也就是1000 / 0.75约等于1334，保守一点直接new HashMap<>(1334)甚至1500。还有一个更常见的做法，直接用new HashMap<>(1000)然后接受一次扩容，毕竟一次扩容的代价通常远小于预分配内存的浪费。具体取舍看场景，但理解threshold的计算逻辑，至少不会让扩容时机成为“未解之谜”。

6.3 迭代顺序、null key与一些使用习惯

最后说几个日常使用中容易忽略的点。

HashMap的遍历顺序是不稳定的。不要依赖keySet()或entrySet()的顺序，它跟数组长度、hash分布、插入顺序都有关系，扩容之后顺序还可能变。需要稳定顺序时，用LinkedHashMap；需要排序时，用TreeMap。

HashMap允许key为null，底层会把null的hash当成0来算，所以null key最终落在数组下标0那个桶里。HashTable不允许null key，这也是两者行为上一个明显的差异。虽然Java的新代码里基本不会写Hashtable，但面试题里这个对比还是常客。

还有一个容易被业务忽视的问题：HashMap里的键值对不会被自动清理。如果你拿Map当缓存，存了过期数据却只是不断覆盖和新增，它会一直占着内存，甚至引发内存泄漏风险。自己实现缓存时，要么定期清理，要么直接上带过期策略的缓存组件，别指望HashMap自己“智能回收”。

把源码走通一遍之后再回头看，HashMap其实没什么神秘的地方。一次put的完整过程，无非是算下标、处理冲突、必要时扩容这三件事。但就是这三件事，把哈希表、链表、红黑树、位运算这些基础概念串在了一起。真正动手逐行读过之后，后面再去看ConcurrentHashMap的源码，你会发现很多设计思路都是相通的。