写了不少年JavaHashMap的源码翻过好几遍也面过不少人。问一句“HashMap是什么”几乎都能答上来“数组加链表红黑树优化”。但再往下问一句“你往HashMap里put一个key-value这一个键值对到底是怎么存进去的”能答完整的人明显少一截。大多数人的认知停在“算个hash放数组里”再往下就说不清了。这篇文章就把一次put过程从头到尾拆开。不是背结论而是跟着JDK源码的逻辑走一遍“一个key-value键值对保存的完整过程”顺便把为什么这样设计、哪些地方容易踩坑讲清楚。适合正在准备面试的开发者也适合用HashMap写了几年业务代码、却从来没打开过源码的人。1. 一次put()调用JDK到底在忙些什么1.1 先看整条时间线以JDK 8为例调用一次map.put(key, value)底层走的是putVal方法。整个过程可以压缩成下面这条链路对key调用内部的hash()方法做一次扰动计算用(n - 1) hash算出桶下标n是当前数组长度如果数组还没初始化table为null或长度为0先触发resize()扩容方法来建数组检查算出来的下标位置上有没有节点没有直接new一个Node放进去有节点说明发生了哈希冲突进入冲突处理流程冲突处理完插入新节点之后判断是否需要扩容更新size和modCount返回旧值或null。这七步就是一个key-value从内存落到HashMap里的全部动作。别急着背每一步背后都有选择和理由下面按顺序拆。1.2 为什么会是“数组链表红黑树”三件套先解释底层结构不然后面的流程看不懂。HashMap的底层主体是一个NodeK,V[] table数组每个数组下标对应一个“桶”。理想的哈希表是每个桶只有一个元素这样查询时一步就能定位到目标时间复杂度O(1)。但不同key算出来的下标可能撞到一起这就是哈希冲突。解决冲突HashMap选的是“链地址法”同一个桶下面挂一条链表新来的冲突节点链到链表上。链表本身有个问题节点多了之后查找链表是线性遍历复杂度O(n)。极端情况下所有key都哈希到同一个桶HashMap直接退化成一条大链表性能雪崩。早期版本确实出现过这种被恶意构造输入打垮的场景。JDK 8的解法是引入红黑树当链表长度膨胀到一定程度就把链表转成红黑树。红黑树是自平衡二叉查找树增删查都是O(log n)性能比链表稳定得多。所以“数组链表红黑树”本质是三个层面的兜底数组保证理想情况下的O(1)链表解决冲突红黑树防止冲突恶化。理解了这一层再去看put过程整个逻辑就通了。2. 从key到桶下标hash()扰动与(n-1)hash2.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。比如默认容量16n - 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的幂时完全等价。举个例子n16hash1818 % 16 218 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是nulloldCap和oldThr都是0会走这段逻辑else { newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); }DEFAULT_INITIAL_CAPACITY是16DEFAULT_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 ((TreeNodeK,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是8binCount是链表遍历时的计数器。这段代码的意思大致就是“这个桶的链表长度膨胀到一定程度尝试转红黑树”。但很多人不知道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是容量乘以负载因子得到的值。用默认参数举例容量16threshold12。当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 * oldCapn - 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了”这个说法是错的。并发场景老老实实用ConcurrentHashMapHashMap的设计定位从来就不是线程安全。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傻眼了。原因在前面讲过有参构造传入1000tableSizeFor(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的源码你会发现很多设计思路都是相通的。
