1. 项目概述HashMap 与扰动 hash 究竟是什么我做了十来年 Java 开发面试过的人少说也有几百个。每次问到 HashMap大部分人都能背出“数组加链表、红黑树、负载因子 0.75”这几句话但你再追问一句“为什么 hash 方法要右移 16 位再异或”十个人里有八个会卡住。说实话这不能全怪应聘者——网上讲 HashMap 的文章太多了但绝大多数都把“扰动 hash”当成一个结论直接扔给你从来不讲清楚它到底在解决什么问题、是怎么被设计出来的。HashMap 底层原理说白了就三件事数据存哪里、怎么找位置、位置冲突了怎么办。扰动 hash 则是这一切的地基——如果 hash 算得不够散后面数组扩容、链表转红黑树这些设计全都白搭。这篇博文我不想再重复那些烂大街的源码逐行注释我想换一个讲法先告诉你 HashMap 设计者当年在头疼什么问题再带你一步一步推导出扰动 hash 为什么偏偏是“右移 16 位异或”最后把 put、get、扩容的完整链路串起来。这篇内容的定位是给有一定 Java 基础、准备面试或者想真正吃透集合框架的读者。不管你是刚学完语法想进阶还是已经工作几年想补课只要跟着我把这条线走完再有人问你 HashMap你不仅能答出来还能讲明白“为什么”。2. 底层存储设计思路为什么是数组加链表2.1 从“找东西”这个场景说起把 HashMap 想成一个超大的储物柜柜子有一排排抽屉每个抽屉有自己的编号。你要存东西的时候先根据钥匙算出一个抽屉号把东西放进去取的时候再根据同一把钥匙算出同一个抽屉号直接去那个抽屉里拿。如果两个不同的钥匙算出了同一个抽屉号就叫“哈希冲突”这时候就不能硬塞了得在同一个抽屉里把多个东西按顺序排好这就是链表。这个设计妙在哪数组的随机访问是 O(1)链表解决冲突又能无限扩容。两者一拼理想情况下 HashMap 的所有操作都是常数时间。但这里有个关键点数组的容量是有限的到底给多少个抽屉才合适抽屉太少冲突严重链表越来越长性能退化到 O(n)抽屉太多内存大片浪费。HashMap 的答案是用“负载因子”来平衡——默认 0.75意思是数组用到 75% 就翻倍扩容既不过度浪费空间也不让冲突失控。我见过不少刚入门的朋友有个误解觉得链表就是用来存 hash 一样的数据的。实际上链表里存的是“hash 取模后落到同一个桶”的数据这些数据的原始 hash 值并不一样只是桶号碰巧相同。理解这一点后面看扩容时的链表拆分逻辑才不迷糊。2.2 JDK 1.8 的改进红黑树是补救措施而非设计目标JDK 1.8 之前HashMap 的桶里只有链表。一旦发生严重的 hash 碰撞比如恶意构造一堆 hash 相同的数据往里塞链表会变得巨长HashMap 直接退化成一个链表put 和 get 都变成 O(n)这是典型的拒绝服务攻击手段。为了防住这种攻击1.8 引入了红黑树当链表长度超过 8 且数组容量达到 64 时链表转成红黑树把最坏情况的时间复杂度从 O(n) 降到 O(log n)。注意我强调“数组容量达到 64”这是新手很容易忽略的细节。源码里有一段条件判断如果链表长度超过 8 但数组容量还不到 64不会转树而是先扩容。什么逻辑转红黑树的代价很高——节点要变色、旋转比普通链表节点重得多。数组容量小的时候大概率是因为容量不够导致冲突集中这时候扩个容把数据分散到新桶里冲突自然就缓解了没必要急着树化。这就像房间太小东西放不下你硬塞抽屉不如直接换个更大的房间来得实在。树化阈值 8 和反树化阈值 6 之间故意留了空档这也是有讲究的。如果树化后链表长度降到 6 以下就转回链表而 put 和 get 的频繁操作会让长度在 6 和 8 之间反复横跳导致频繁转换白白消耗性能。留出 2 的缓冲区间是为了避免抖动。3. 扰动 hash 深度拆解一个右移 16 位的精妙设计3.1 hash 计算过程的完整推导现在我们来到这篇文章的核心。HashMap 计算桶位置的完整链路是这样的static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); } // 计算桶索引 index (n - 1) hash第一步调用 key 的 hashCode() 方法得到一个 int。这个 int 是 32 位的二进制数取值范围理论上有 40 多亿个但 HashMap 的数组初始容量只有 16扩容一次翻倍哪怕扩到几万和 int 的取值范围比起来还是九牛一毛。第二步就是扰动函数把 hashCode 右移 16 位再和自己做异或。右移 16 位相当于把高 16 位挪到了低 16 位的位置上异或操作则把原始 hashCode 的高位信息和低位信息混在一起。这样处理后低 16 位就同时包含了原始 hash 的高位和低位特征。第三步用 (n - 1) hash 计算桶下标。n 是数组长度由于 HashMap 的容量始终是 2 的幂n - 1 的二进制就是全 1。比如 n 16n - 1 15二进制是 0000 1111和任何 hash 值做按位与等于直接取 hash 的低 4 位。第三步才是问题所在——如果你不扰动直接用原始 hashCode 做按位与那么数组长度是 16 时只有 hash 的低 4 位参与了运算高 28 位全部浪费。如果两个对象的 hashCode 在高位不同、低位相同它们会算出同一个桶号hash 冲突的概率非常高。3.2 从二进制视角看扰动前后的差异光说理论不够直观我手推一个例子。假设数组长度 n 16n - 1 15即二进制 0000 1111。有两个对象 A 和 B它们的 hashCode 分别是A 的 hashCode: 1010 1100 0110 1001 0001 1100 1011 0101 B 的 hashCode: 0110 1001 0011 1010 0101 0011 0011 0101这两个 hashCode 的低 4 位都是 0101如果你不扰动直接用 hashCode 15A 和 B 都会被分到桶 5冲突了。现在看扰动后的效果。A 的 hashCode 右移 16 位得到 0000 0000 0000 0000 1010 1100 0110 1001异或后就变成了1010 1100 0110 1001 0001 1100 1011 0101 ^ 0000 0000 0000 0000 1010 1100 0110 1001 1010 1100 0110 1001 1011 0000 1101 1100B 同理右移 16 位得到 0000 0000 0000 0000 0110 1001 0011 1010异或后是0110 1001 0011 1010 0101 0011 0011 0101 ^ 0000 0000 0000 0000 0110 1001 0011 1010 0110 1001 0011 1010 0011 1010 0000 1111现在再看低位A 的低 4 位变成 1100桶号 12B 的低 4 位变成 1111桶号 15。原本冲突的两个人扰动后被分配到了不同的桶。这个例子的本质是A 和 B 的原始 hash 在高 16 位上有差异扰动操作把这段差异“传导”到了低 16 位而低 16 位正是参与桶号计算的区域。这就是“扰动”二字的含义——人为制造变化把高位的随机性扩散到低位让最终的桶分布更均匀。3.3 为什么偏偏是异或为什么是 16 位你可能会问扰动操作有很多种写法为什么偏偏是异或偏偏是 16 位先说异或。按位与偏向 0按位或偏向 1只有异或是真正的 50% 概率出 0、50% 概率出 1能把两个输入的信息以最“平均”的方式融合。比如我们想让输入的第 1 位影响输出第 17 位用异或既不会有信息丢失也不会引入偏差。如果用与运算只要其中一个位是 0结果永远为 0这会压制另一个输入的信息或运算同理一个位是 1 就覆盖另一个。异或没有这个问题它的输出能充分保留两个输入的随机性。再说 16 位。高 16 位右移 16 位和低 16 位异或本质上是让高 16 位的每一位和低 16 位的对应位互相混合。为什么不是 8 位、24 位因为 int 是 32 位的最终参与桶号计算的是低 n 位n 是数组容量的对数最坏情况下扩容到非常大时 n 可能接近 30。把高 16 位混合进来相当于保证了“无论数组多大原始 hash 的所有位都有机会影响到桶号计算”。从概率角度看有一个经典的数学结论可以说明扰动函数的威力假设原始 hashCode 是按照均匀分布随机生成的字符串的 hashCode 计算中低位容易出现聚集现象——比如字符串“Aa”和“BB”这两个 hash 差异只在高位。如果不扰动当数组长度较小时这两个对象几乎必然冲突。扰动后高位的差异被引入低位冲突概率显著下降。Java 的哈希分布在实际数据中往往不是理想的随机分布尤其像 Integer 这种 hashCode 就是自身值的类型如果 key 是连续的 1、2、3...16不扰动的话它们会整整齐齐地排满一条链扰动后虽然这几个值仍然会均匀散开因为)它们的低位本身不同但如果你遇到的是像“16、32、48、64”这种步进为 16 的数字序列不扰动的后果就完全暴露了16 的二进制是 0001 000032 是 0010 000048 是 0011 0000……它们的低 4 位全是 0直接 15 全落到桶 0链表爆炸。扰动后16 右移 16 位的值和自身异或结果不再是原来的 16低 4 位不再是 0冲突自然化解了。我当年在项目里就遇到过用 Integer 做 key、并且数据规律性极强的场景加了扰动和不加扰动HashMap 的查询效率差距是肉眼可见的。4. put 流程全解析从定位到插入的完整路径4.1 一次 put 操作到底做了什么把扰动函数讲清楚了put 的完整流程就顺理成章了。这里我画不出实物流程图但你跟着文字顺序走一遍逻辑非常清晰第一步判断哈希表是否为 null 或者长度为 0。首次 put 时会先调用 resize() 初始化一个默认容量为 16 的数组。第二步调用 hash(key) 计算扰动后的哈希值。第三步用 (n - 1) hash 计算桶索引找到桶位置后分三种情况处理如果桶是空的直接 new 一个 Node 放进去完事。如果桶不为空先比较桶里第一个节点的 hash 和 key。如果都相等说明是更新操作直接把老值覆盖掉。如果第一个节点不匹配判断它是链表节点还是红黑树节点。树节点走 putTreeVal 方法链表节点则从头到尾遍历逐个比较。如果找到了相同 key覆盖并返回旧值如果遍历到末尾也没找到把新节点追加到链表尾部。此时再检查链表长度是否超过 8超过则调用 treeifyBin 尝试转红黑树。最后修改次数 modCount 加 1容量加 1如果超过阈值数组容量乘以负载因子触发 resize() 扩容。这里有个细节必须提醒判断 key 是否相同用的是 key.equals(k)所以重写 equals 时一定要同步重写 hashCode否则就会出现“equals 相同但 hash 不同”的诡异问题——两个相等的 key 被放进不同桶get 的时候找不到。踩过一次你就知道有多痛。4.2 从 JDK 1.7 到 1.8 的改动尾插法为何更好JDK 1.8 还有一个低调但极其重要的改动链表插入从头插法改成了尾插法。1.7 时代用头插法有一个性能上的考虑——新插入的数据更可能被频繁访问放链表头部能减少遍历。但头插法在并发扩容时有个著名的问题因为 java.util.HashMap 本身就不是线程安全的多线程同时 put 触发 resize头插法会让链表在转移过程中形成环一旦成环下次 get 这个桶里的数据时就会发生死循环CPU 飙到 100% 都拉不回来。这是 1.7 的著名悲剧。1.8 改成尾插法后链表在扩容转移时只有指针调整不会反转顺序也就不会出现环形链表。但别误会这并不代表 HashMap 可以在并发环境下放心用。并发 put 仍然会丢数据、覆盖数据正确做法是用 ConcurrentHashMap。面试官问到这里你如果能说出“尾插法是为了配合扩容时的链表拆分逻辑避免死循环”会显得你真的看过源码、理解改动动机。5. 扩容机制resize 背后的数学与工程权衡5.1 为什么容量必须是 2 的幂HashMap 扩容的老规矩是新容量 旧容量 × 2。为什么死磕 2 的幂这个设计贯穿了整个 HashMap前面计算桶索引时已经体现过了——n 是 2 的幂时n - 1 的二进制是全 1 运算等价于取模但比取模快得多。CPU 做位运算只需要一个时钟周期做取模除法可能要几十个周期这个差距在高频 put/get 下会被无限放大。2 的幂的另一个好处体现在扩容时的索引重算。假设旧容量 n 是 16新容量是 32。一个 key 的扰动 hash 假设是 h它在旧数组的索引是 h 15在新数组的索引是 h 31。注意 15 和 31 的二进制差什么差在第 5 位。也就是说h 的第 5 位是 0索引不变第 5 位是 1新索引 旧索引 16。JDK 1.8 的源码正是利用这个性质优化扩容的——它没有重新计算每个节点的 hash 再取模而是直接检查节点 hash 值的第 5 位即 oldCap 对应的那一位为 0 的留在原桶为 1 的移到“原索引 旧容量”的新桶。这一手极大地提高了扩容效率。5.2 扩容时链表拆分的底层逻辑具体到代码层面扩容时每个桶的链表会被拆成两条新链表低位链表loHead和原索引位链表hiHead。这里我贴一下 1.8 里的核心套路但做了简化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; } e next; } while (e ! null); if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; }看懂这段代码的关键就一行(e.hash oldCap) 0。oldCap 是旧容量也就是 16、32 这种值二进制是 10000、100000恰好就是 n 的最高位。这个与运算检测的就是 hash 在“新增位”上的值。为 0 说明扩容后索引不变挂到 loHead 上为 1 说明新索引要加 oldCap挂到 hiHead 上。记住这里重用的是“扰动后的 hash”不是原始 hashCode。这也是扰动 hash 贯穿始终的体现——如果 hash 在初始计算时没混合高位扩容时这一位的随机性就会差一些链表拆分后两个新桶的元素数量可能严重失衡。5.3 负载因子 0.75 是怎么来的负载因子是容量与性能的杠杆。太大比如 1.0数组利用率高但冲突概率大链表变长、查询变慢太小比如 0.5冲突少、查询快但浪费一半内存扩容频繁整体吞吐量反而下降。0.75 是一个在时间和空间成本上取得平衡的经验值。有一种解释是0.75 是泊松分布下的一个临界参数。当负载因子为 0.75 时桶中出现链表长度达到 8 的概率大约是千万分之六这个概率低到在常规业务中可以忽略不计因此红黑树理论上很少被真正触发它主要是为了防御极端攻击而设的保险措施。这个数学背景我当年也是看了源码注释反复推算才彻底理解面试能主动讲出这一点通常会让人眼前一亮。6. HashMap 排序实战把理论落到代码上热词里提到“hashmap 排序”也是面试里的常客。这里分享两个最实用的实现我平时在项目中碰到需要按 key 或 value 排序的场景基本都是这两种写法。6.1 按 key 排序的推荐写法最推荐的方式是构造一个 TreeMap直接把 HashMap 丢进去因为 TreeMap 天然按 key 的自然顺序排序import java.util.*; public class HashMapSortByKey { public static void main(String[] args) { MapString, Integer map new HashMap(); map.put(banana, 5); map.put(apple, 3); map.put(cherry, 8); map.put(date, 1); // 直接放入 TreeMap按 key 升序 MapString, Integer sortedMap new TreeMap(map); System.out.println(按 key 排序结果 sortedMap); // 如果需要自定义排序规则比如按 key 长度 MapString, Integer customSortedMap new TreeMap(Comparator.comparingInt(String::length)); customSortedMap.putAll(map); System.out.println(按 key 长度排序结果 customSortedMap); } }TreeMap 底层是红黑树插入时就会按照比较器调整顺序省去了手写排序的麻烦。注意自定义比较器时如果两个 key 长度相同TreeMap 会认为它们是同一个 key后面的值覆盖前面的值这是新手最容易掉的坑。解决办法是在比较器里加一个二级比较ComparatorString comparator Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder());6.2 按 value 排序的实现思路HashMap 本身不支持按 value 排序需要把 Entry 拿出来放到 List 里再用 Collections.sort 或者 Stream 的 sorted 操作。Java 8 之后的写法最简单import java.util.*; import java.util.stream.*; public class HashMapSortByValue { public static void main(String[] args) { MapString, Integer map new HashMap(); map.put(banana, 5); map.put(apple, 3); map.put(cherry, 8); map.put(date, 1); // 按 value 升序 ListMap.EntryString, Integer list new ArrayList(map.entrySet()); list.sort(Map.Entry.comparingByValue()); System.out.println(按 value 升序 list); // 按 value 降序 ListMap.EntryString, Integer descList new ArrayList(map.entrySet()); descList.sort((e1, e2) - e2.getValue().compareTo(e1.getValue())); System.out.println(按 value 降序 descList); // 使用 Stream 的写法更简洁 MapString, Integer result map.entrySet().stream() .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())) .collect(Collectors.toMap( Map.Entry::getKey, Map.Entry::getValue, (oldVal, newVal) - oldVal, LinkedHashMap::new )); System.out.println(Stream 按 value 降序 result); } }Stream 版本里最后用了 LinkedHashMap::new很多第一次写的人会漏掉这一步直接 Collectors.toMap 得到的新 map 是默认的 HashMap顺序根本不保证排序等于白做。用 LinkedHashMap 才能保留插入顺序。这是一个极其容易踩的隐藏 bug我在代码 review 里见过不止三次。7. 常见问题与排查技巧实录HashMap 相关的坑我在实际项目中踩过的、面试中问过的整理成了一张速查表希望对你有用。问题现象根本原因解决方案重写 equals 后 get 不到数据没有同步重写 hashCodeequals 相同但 hash 不同equals 和 hashCode 必须同时重写自定义对象作为 key 时出现逻辑错误对象是可变的hashCode 在放入 HashMap 后发生变化优先使用不可变对象作为 key如 String、Integer高并发下 put 丢数据HashMap 非线程安全并发写入互相覆盖换用 ConcurrentHashMap容量设得很大但仍频繁扩容误解了初始容量的语义只设了容量没考虑负载因子估算数据量initialCapacity 预期数据量 / 0.75 1转红黑树后偶发退化链表长度在 6 到 8 之间震荡这是设计内的防抖机制属正常现象使用 Stream 排序后顺序仍然不对收集时用了默认 HashMap未使用 LinkedHashMap在 Collectors.toMap 中指定 LinkedHashMap::new我在实际工作中还发现一个技巧当你预估 HashMap 要存放大量数据时别用默认容量。比如预估要放 1 万个数据直接 new HashMap(10000) 其实会在元素数超过 7500 时触发一次扩容而真正的操作是 new HashMap(10000 / 0.75 1)也就是 13434 左右保证全程不扩容。很多人忽略这个点存储大数据集时白白多了一次 O(n) 的扩容开销。还有一个排查效率问题的经验——如果生产环境出现 HashMap 查询变慢很可能不是代码逻辑问题而是 key 的 hashCode 分布出了问题。你可以在本地写个小脚本生成实际数据跑一遍把每个桶的元素数量打印出来看看有没有某个桶元素数量异常多。如果确实有检查 key 对象的 hashCode 实现十有八九是某个字段取值范围太窄导致 hash 集中在少数几个值上。这种问题靠调大初始容量解决不了得从源头调整 hashCode 的散列逻辑。最后说一下项目实战里 HashMap 的选型建议。单线程环境用 HashMap读多写少可以用 LinkedHashMap 保留插入顺序需要线程安全就用 ConcurrentHashMap。HashTable 已经是历史遗留物了它的所有方法都加了 synchronized 锁性能远不如 ConcurrentHashMap能不用就别用。排序需求用 TreeMap 或者 Stream 排序千万别自己手写一个结构去维护顺序完全没必要。我在实际使用中最大的体会是HashMap 这个类最精彩的不是某个单独的数据结构而是数组、链表、红黑树、扰动函数、扩容优化这些设计彼此咬合、环环相扣。你单看扰动函数觉得不过是一行位运算但放到整个 put 流程里它直接影响冲突率你还得结合扩容时的(e.hash oldCap)判断才能明白扰动后的 hash 在扩容时也起到了均衡分布的作用。所谓底层原理就是这样一层一层勾连起来的搞清楚一条线索其他部分也就都通了。