1. 哈希表不是魔法：它到底解决了什么问题
先用一个最朴素的问题开场：为什么我们需要哈希表？
数组大家都熟，按下标访问元素的时间复杂度是 O(1)，这已经是计算机里最快的随机访问方式了。但数组有个要命的前提——下标必须是整数，而且你还得知道这个下标是多少。如果我想查一个叫"张三"的人的电话号码，数组根本不认识"张三"这四个字，它只认识 0、1、2、3……这种整数下标。那你怎么办？只能遍历整个数组一个一个比，O(n) 就出来了。
链表也是类似的困境，想找一个元素只能从头结点开始挨个走，平均 O(n)。树结构能优化到 O(logn)，比如平衡二叉树、B+树，这已经是很大的进步了，但还不是最快的。
哈希表的思路完全不一样：既然数组访问快，那我就想办法把"任意一个 key"映射成一个"数组下标"。你给我一个字符串、一个对象、一个数字，我都通过一个函数算出一个整数，然后把这个整数当成数组下标，直接把数据存进数组的这个位置。查的时候也一样，拿着 key 再算一遍下标，直接去数组那个位置拿。整个过程跟数组一样是 O(1)，但又不要求 key 必须是整数。
这个"把任意 key 算成数组下标"的函数，就是哈希函数。
一句话总结：哈希表 = 数组 + 哈希函数。数组负责 O(1) 的存取速度，哈希函数负责把五花八门的 key 转换成数组能认的整数下标。
你可能已经发现了，这里面藏着一个巨大的隐患：如果两个不同的 key 算出来的下标一样怎么办？
比如 keyA 算出来是 7，keyB 算出来也是 7，但数组下标 7 这个位置已经被 keyA 占了。这就是哈希冲突。哈希表的所有设计难点，说白了都是围绕两件事：怎么让哈希函数尽量少产生冲突，以及真产生了冲突怎么办。后面几节我会分别拆开讲。
在往下走之前，先明确哈希表支持的三个核心操作，方便后面讨论：
- put(key, value)：把 key 映射成下标，存进去。
- get(key)：把 key 映射成下标，取出来。
- remove(key)：把 key 映射成下标，删掉。
这三个操作在理想情况下都是 O(1)。注意我说的是"理想情况"，实际工程里有很多因素会让这个 O(1) 退化，如果你只记住了"哈希表查得快"而忽略了它的退化条件，后面线上出问题的时候你连排查方向都没有。
2. 哈希函数：散列质量的生死线
哈希函数决定了整个哈希表的命运。一个优秀的哈希函数，应该满足三个要求。
2.1 一致性：同一个 key 永远算出同一个值
这个没什么好说的，如果同一个 key 第一次算出来是 3，第二次算出来是 8，那整个哈希表直接崩了。它的真正含义是：两个相等的 key，必须产生相同的哈希值。这在 Java 里对应着hashCode()和equals()的约定，后面我会专门讲这个坑。
2.2 高效性：计算不能太慢
哈希函数本身是有 CPU 成本的。如果算一次哈希要执行几百条复杂指令，那就算查表是 O(1)，整体性能也可能不如一棵简单的二叉树。工程上常说"空间换时间"，哈希函数其实是"用计算换时间"。
2.3 均匀性：不同的 key 尽量分散到不同的下标
这是最核心的一条。如果哈希函数把所有 key 都算成同一个下标，那哈希表就退化成了一条链表，get 操作又变回 O(n) 了。
Java 里String的hashCode()是个非常经典的教学案例，它用的是这个公式：
hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]这里每个字符都参与计算，而且位置越靠前的字符，权重越大。为什么乘 31？两个原因：31 是奇素数，乘法运算时不容易产生信息丢失；同时 JVM 会对31 * i做优化，等价于(i << 5) - i，一次位移一次减法，非常快。你可以去看看 Java 源码里的String.hashCode()，实现就是按这个公式来的。
不过hashCode()算完并不代表能直接用，Java 的 HashMap 内部还做了一次扰动处理，源码里叫hash()：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }看到那行h ^ (h >>> 16)了吗？它的意思是：把 int 的高 16 位和低 16 位做异或，让高位的特征也混入低位。为什么要这么做？
因为 HashMap 计算数组下标时用的是(n - 1) & hash，这里的 n 是数组长度。如果长度只有 16（也就是 n-1 的二进制约束了只看低 4 位），那 hashCode 的高位信息就全被丢掉了。两个对象的 hashCode 高位不同但低位恰好相同，在这张表里就会被算到同一个下标。扰动函数让高位信息也参与低位的运算，就是为了在容量还很小的时候，让 key 也能散得更均匀。
这里的经验是：别指望每个人的 hashCode 都写得好，HashMap 在入口处帮你兜了一道底。你去看 ConcurrentHashMap 也有类似的处理，这个思想跟上位运算在哈希表领域特别常见。
反过来看，什么样的 hashCode 是灾难级的？
// 反例1：所有对象返回相同哈希值 @Override public int hashCode() { return 1; } // 反例2：直接用唯一ID取模，ID分布不均时冲突严重 @Override public int hashCode() { return id % 10; } // 反例3：组合字段时用加法，可能会导致(A,B)和(B,A)撞车 @Override public int hashCode() { return name.hashCode() + age; // 顺序敏感度差 }业务对象正确做法，是选择各个字段的哈希值，然后用质数加权组合。Java 自带Objects.hash(...)就是这么干的：
@Override public int hashCode() { return Objects.hash(name, age, email); }底层会把每个字段的哈希值和一个初始种子数（比如 31）做迭代乘法累加。质数的好处是，即使不同字段的哈希值恰好线性相关，组合后也不容易产生倍数关系的冲突。
3. 哈希冲突的四种解法，以及它们的取舍差异
不管你哈希函数写得多漂亮，只要 key 的空间大于哈希表的容量，冲突就不可避免（抽屉原理，鸽巢原理）。所以真正区分哈希表工程质量的，是它怎么处理冲突。主流方案有四类：
3.1 链地址法（拉链法）
这是最常见、也最直接的思路：数组的每个位置不放单个元素，而是放一条链表。冲突了？没问题，直接往链表尾部挂。
Java 的 HashMap、ConcurrentHashMap 都是这个方案。链地址法有几个天然的优势：
- 实现简单，增删改查逻辑很直白。
- 删除容易，链表上摘一个节点就行，不需要做"墓碑"之类的标记。
- 对负载因子容忍度高，链表稍微长一点问题不大，极端情况下还能转红黑树救场。
- 扩容迁移方便，重新计算下标后，节点按高低位拆成两条链，不用反复插入。
它的缺点也很明显：链表节点的内存不连续，CPU 缓存命中率低；而且每个节点都有额外的指针存储开销。
3.2 开放寻址法
数组的每个位置只能放一个元素。冲突了？别慌，往后找一个空位放进去。查找的时候就顺着往下找，直到找到目标或者遇到空位（说明没这个 key）。
找空位的方式有三种：
- 线性探测：冲突了就往后挪一个位置，
(hash+1) % n。实现最简单，但容易产生"聚集"问题——冲突的 key 扎堆排队，导致后续的插入和查找都要跨越很长一段距离。 - 二次探测：往后挪的步长是 1²、2²、3²……
(hash + i²) % n。步长逐渐加大，可以一定程度上缓解聚集，但要小心别跳出了还没找到空位。 - 双重散列：准备第二个哈希函数，冲突时用第二个函数算出步长，
(hash + i * hash2(key)) % n。效果最好，但也最讲究哈希函数质量。
开放寻址有个特别容易踩的坑：删除操作不能直接置空。如果直接把一个位置置为 null，那后面本来排在它后面的元素，在查找时会因为遇到 null 而被误判为"不存在"。所以工程实现里需要用一个"墓碑"标记删除位置，查询时遇到墓碑继续往后走，插入时可以覆盖墓碑。这比链地址法麻烦得多。
开放寻址对负载因子也特别敏感，内存使用率接近 0.7 时冲突会急剧恶化，所以一般会把负载因子压到 0.5 左右，空间浪费比较大。但它的好处是数据全在连续数组里，缓存命中率极高，在内存受控、数据量可预测的底层场景里反而更常用。
3.3 再哈希法
准备一组哈希函数，第一个冲突了换第二个，第二个再冲突换第三个……直到找到空位。
这个方案在通用哈希表里基本绝迹了，因为它需要维护多个哈希函数的状态，而且查找时的路径没法预判，实际工程价值有限。但它在一致性哈希、分布式负载均衡这类场景里思想还有延续——本质上是通过多次哈希来选择目标，只是目的从"存数据"变成了"选节点"。
3.4 建立公共溢出区
额外开辟一块"溢出区"，所有冲突的 key 统一放进去。适合"冲突极少但必须兜底"的场景，比如某些数据库索引结构。实现上虽然简单，但溢出区一旦变大性能就崩了。
四种方式怎么选？看场景，没有绝对最优：
| 方案 | 实现成本 | 删除 | 缓存友好度 | 负载因子容忍度 | 典型应用 |
|---|---|---|---|---|---|
| 链地址法 | 低 | 容易 | 较低 | 高（可到 0.75+） | Java HashMap、Redis |
| 线性探测 | 低 | 需墓碑 | 高 | 低（约 0.5） | ThreadLocalMap |
| 二次探测 | 中 | 需墓碑 | 中 | 低 | 早期哈希表教材实现 |
| 双重散列 | 高 | 需墓碑 | 中 | 中 | 性能敏感型哈希表 |
| 再哈希/溢出区 | 高 | 复杂 | 低 | 低 | 特定专用结构 |
4. Java HashMap 的工程化细节：红黑树、扩容与那场死循环事故
如果你只把哈希表当纯理论看，那到这里基本已经够了。但既然热搜词里出现了"java哈希表输出"，说明大量实际问题是出在 Java 的 HashMap 实现上的。这一节我按 JDK 8（确切说是 JDK 8u20 之后）的实现来讲，顺便聊聊 JDK 7 那个让无数人 CPU 跑满的历史事故。
4.1 JDK 7 到 JDK 8 的结构升级
JDK 7 及以前的 HashMap 是数组 + 单向链表的结构，新增元素时采用头插法——新节点插到链表头部。JDK 8 改为数组 + 单向链表 + 红黑树，插入时用尾插法——新节点挂到链表尾部。
为什么改尾插？后面讲死循环的时候你就明白了。
4.2 链表什么时候升级成红黑树
JDK 8 的源码里有三个关键常量：
static final int TREEIFY_THRESHOLD = 8; // 链表长度达到8，尝试转树 static final int UNTREEIFY_THRESHOLD = 6; // 红黑树节点数降到6，退化为链表 static final int MIN_TREEIFY_CAPACITY = 64; // 转树前，数组容量必须达到64转树的条件是：链表长度超过 8，且数组容量至少 64。这两个条件缺一不可，如果容量还没到 64，就算链表很长，HashMap 也会选择先扩容而不是转树。
为什么阈值偏偏是 8？因为这个数字来自泊松分布。在随机哈希（即各桶概率均匀）且负载因子为 0.75 的情况下，单个桶内链表长度达到 8 的概率大约是千万分之六，约等于"几乎不可能发生"。也就是说，正常情况下链表长度不会超过 8，转红黑树本来就是给哈希函数写得极烂的场景兜底的。
红黑树节点的内存占用大概是普通链表节点的两倍，所以树化其实是"用空间换极端情况下的时间"。树退化阈值取 6 而不是 7 ，是为了防止元素在阈值附近反复增删时，链表和树来回切换产生抖动。退一步，如果取 7，那链表长度在 7 和 8 之间震荡五次，结构就切换五次，一次转换的代价可不小。
4.3 为什么容量必须是 2 的 n 次幂
HashMap 有两个和容量相关的细节值得单独说。
第一，tableSizeFor方法保证初始容量向上取整到 2 的幂次：
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; }你传入 17，它给你 32；传入 100，给你 128。这套"右移+或"的位运算巧妙地把最高位以下的位全部填成 1，再加 1 进位，得到最近的 2 的幂。
第二，为什么非要 2 的幂？因为这样计算下标可以省掉取模运算，直接用位运算：
index = (n - 1) & hash这个式子等价于hash % n，前提就是 n 是 2 的幂。位运算比取模快得多，而哈希表几乎每个操作都要算下标，这个优化省下的 CPU 很可观。
4.4 扩容机制：为什么是 2 倍扩容
当元素个数超过容量 * 负载因子时，HashMap 触发扩容，容量直接翻倍。负载因子默认 0.75，也就是默认容量的 16 个桶，存到 12 个元素就会扩容到 32。
扩容不只是把数组换大那么简单，所有已存在元素的桶下标都要重新计算——因为(n - 1) & hash里的 n 变了，同一个 hash 算出的低位掩码长度变了，下标大概率也会变。
但 JDK 8 的扩容有个巧妙的优化。由于容量从 oldCap 变成 2 * oldCap，newCap - 1 相比 oldCap - 1 多了一个最高位为 1 的二进制位。某个节点在新数组的下标，要么是原来的下标，要么是"原下标 + oldCap"。判断依据就是(hash & oldCap) == 0：
- 结果为 0，说明新增的这一位正好是 0，下标不变。
- 结果不为 0，说明新增的这一位是 1，下标需要偏移 oldCap。
所以 JDK 8 的 rehash 不是逐个重算，而是把每个桶里的链表按hash & oldCap拆成 lo 和 hi 两条链，分别挂到新数组的原下标和新下标位置。
4.5 JDK 7 的死循环事故
这个历史问题值得每个用 HashMap 的人知道。JDK 7 的扩容采用头插法：遍历旧链表，把节点一个个摘下来，插入到新数组桶的头部。多线程并发扩容时，两个线程同时操作同一个桶的链表，就可能让链表节点形成环，也就是 A -> B -> A。
之后任何线程在这个桶上执行 get，就会在环形链表里死循环，CPU 直接爆到 100%。这个事故在当年是让无数团队吃过亏的经典案例。
JDK 8 改尾插法，避免了新链表逆序导致的环，但这只是降低了死循环的概率，并没有让 HashMap 变得线程安全。并发下依然会出现数据覆盖、丢失等问题，正确做法是使用 ConcurrentHashMap 或Collections.synchronizedMap。关于并发替代方案的对比，后面会专门讲。
5. 为什么 HashMap 遍历输出的顺序总是不稳定
现在回到热搜词里的"java哈希表输出"。这个搜索词的高频出现，说明大量开发者在实际敲代码时遇到了同一个困惑：往 HashMap 里 put 的顺序明明是 A、B、C，为什么遍历输出的时候顺序完全对不上？
这个现象的原因，正是上面讲过的所有机制叠加的结果。
5.1 桶下标与插入顺序没有必然关系
元素存到哪个桶，取决于hash(key)和当前容量。HashMap 的默认容量是 16，那么：
- keyA 的 hash 是 65，(16-1) & 65 = 1，存桶 1。
- keyB 的 hash 是 33，(16-1) & 33 = 1，也在桶 1。
- keyC 的 hash 是 130，(16-1) & 130 = 2，存桶 2。
插入顺序是 A、B、C，但桶的顺序是 1、1、2。遍历时从桶 0 开始逐个走，出来的顺序就是 A、B、C 或者 B、A、C（取决于链表内部顺序），这自然跟插入顺序对不上。等扩容到 32 之后，这些 key 的下标又全变了，输出顺序又一次大变。
所以 HashMap 的输出顺序从来就是不确定的：它依赖 key 的 hashCode、当前容量、负载因子、冲突链路长的共同作用。你要是在代码里依赖这个顺序做业务，那基本等于埋雷，哪天线上环境换了 JDK 版本或者 key 结构调整了，输出顺序一变，程序可能就出 bug 了。
5.2 需要保序时用什么
如果确实需要按某种确定的顺序遍历，别硬掰 HashMap，换数据结构更省心：
- LinkedHashMap：内部额外维护一条双向链表，记录插入顺序或访问顺序。遍历时按这条链走，输出顺序就是插入顺序。它的构造方法里有个
accessOrder参数，设为 true 可以按"最近访问"排序，这是实现 LRU 缓存的利器，像 MyBatis、Spring 的一些缓存模块底层都用了这个特性。 - TreeMap：按 key 的自然顺序或自定义 Comparator 排序，遍历输出天然有序，代价是操作复杂度从 O(1) 变成 O(logn)。
5.3 多线程下的输出异常与安全替换
HashMap 在并发环境下，不只是顺序问题，数据完整性都可能出问题。我帮你把几个常见方案的特性列个表：
| 方案 | 线程安全机制 | 读性能 | 写性能 | 适用场景 |
|---|---|---|---|---|
| HashMap | 无 | 最高 | 最高 | 单线程或确定无并发竞争 |
| Hashtable | 全方法加 synchronized 锁 | 低 | 低 | 基本不用了 |
| Collections.synchronizedMap | 包装整个 Map 加锁 | 中 | 中 | 遗留项目兼容 |
| ConcurrentHashMap | CAS + synchronized 锁桶/分段锁 | 高 | 高 | 并发读多写多的首选 |
ConcurrentHashMap 的性能接近 HashMap，并发安全系数高得多。它把整个 Map 分成很多桶，不同线程操作不同桶时可以并行，只有操作同一个桶时才需要等待，锁粒度远小于 Hashtable。
如果并发场景里你对数据还有强一致性的要求，比如先判断再写入这种复合操作，那 ConcurrentHashMap 提供的computeIfAbsent、merge这类原子方法也足够用了。
6. 真实业务里的哈希表排障：从我踩过的坑说起
前面讲完了原理和实现，最后这部分是我实际项目里遇到过的哈希表相关故障，每一个都是线上真实发生的。光知道理论容易眼高手低，遇到实际问题能定位才是真本事。
6.1 坑一：hashCode 返回常量，接口从秒回变成超时
有次排查一个接口的耗时陡增，从平均 50ms 涨到 4 秒多，用火焰图一看，热点全在哈希表的查找上。定位到最后，发现是团队里一个模型类重写了hashCode()，但实现是：
@Override public int hashCode() { // 当时为了暂时通过编译随便写的 return 1; }结果这个类被当成 key 塞进了 HashMap，所有 key 全落在同一个桶里，链表长度到了几千，每次 get 都是 O(n)。更糟的是，JDK 8 下这个链表还可能转成红黑树，虽然不至于死循环，但性能一样崩。
这个排查经验告诉你，如果线上某接口突然变慢，而且特征和"数据量没涨多少但耗时线性暴涨"吻合，先检查 key 的 hashCode 实现。
6.2 坑二：用可变对象做 key，get 返回 null
还有一次，业务方反馈数据"存进去了但查不出来"。看代码，put 的时候明明输出有值，get 的时候却是 null。
原因是他们用了某个自定义对象做 key，这个对象里有几个字段是可变的。第一次 put 的时候，对象的 hashCode 是 A；之后业务逻辑改了对象里的某个字段，再 get 的时候，hashCode 变成了 B。HashMap 拿 B 去算下标，自然去错了桶，桶里空空如也。
这个问题在原理上讲就是哈希函数的一致性被破坏了。对象存进 HashMap 之后，所有参与 hashCode 计算的字段都不能再被修改。最稳妥的做法是用不可变对象做 key，比如 String、Integer，或者自己定义一个所有字段 final 的类。如果非要用可变对象，那就在存进去之前先对字段做防御性拷贝。
6.3 坑三：重写 equals 却没重写 hashCode
很多新手会犯这个错。重写了equals()判断两个对象逻辑相等，但没动hashCode()，两个对象 equals 返回 true，hashCode 却不相等。HashMap 判断 key 是否相等时，是先比 hashCode 再比 equals 的，equals 相同而 hashCode 不同的话，这两个 key 在 HashMap 眼里就是两个完全不同的 key，会出现重复存放、查不到数据等一系列诡异问题。
反之也一样，hashCode 相同不意味着 equals 一定相同（哈希冲突本来就允许），但 equals 相同必须保证 hashCode 相同。这条约定是哈希表工作的前提。
6.4 坑四：遍历时删除元素抛 ConcurrentModificationException
这个其实不算哈希表专有的问题，只要是使用 fail-fast 迭代器的集合都有。但 HashMap 使用频率高，踩的人也多：
// 错误示范：遍历中直接删除，抛 ConcurrentModificationException for (String key : map.keySet()) { if (key.startsWith("temp")) { map.remove(key); } }正确打开方式有两种：
// 方式一：使用迭代器的 remove 方法 Iterator<String> it = map.keySet().iterator(); while (it.hasNext()) { String key = it.next(); if (key.startsWith("temp")) { it.remove(); } } // 方式二：JDK 8+ 的 removeIf map.keySet().removeIf(key -> key.startsWith("temp"));6.5 预分配初始容量
这是性能优化里最简单有效的一条。HashMap 扩容是个相对昂贵的操作，涉及新建数组和把所有元素重新分布，而且每次扩容都是翻倍。如果事先知道大概要存多少条数据，直接指定初始容量：
// 已知要存 600 条数据，负载因子 0.75，直接用 1024 的容量 Map<String, User> userMap = new HashMap<>(1024);计算方式是：预计元素数 / 0.75 + 1，向上取整到 2 的幂。600 / 0.75 = 800，向上取 1024。这样能省掉扩容次数，在大数据量场景下效果立竿见影。
还有个跟这个相关的小技巧：如果你在做数据统计、去重，并且数据量在百万级以上，考虑用 Guava 的HashMultiset或者直接上LongAdder按哈希分桶，避免单个 HashMap 的压力过于集中。
6.6 怎么验证自己的哈希分布是否均匀
最后分享一个排查用的小工具思路。假设你想确认某个类的 hashCode 分布是否合理，可以写一个临时方法，模拟 HashMap 的散列过程，统计各个桶的长度分布：
public static void checkHashDistribution(List<YourKey> keys, int capacity) { int[] bucketSize = new int[capacity]; for (YourKey key : keys) { int index = (capacity - 1) & key.hashCode(); bucketSize[index]++; } Map<Integer, Long> distribution = Arrays.stream(bucketSize) .boxed() .collect(Collectors.groupingBy(i -> i, Collectors.counting())); System.out.println("桶长度分布：" + distribution); }如果发现大量桶长度为 0，而某几个桶特别长，说明 hashCode 分布不均匀，需要重新设计。正常随机哈希下，桶长度应该接近泊松分布，大多数桶是 0 或 1，极少有超过 5 的。
7. 写在最后：哈希表性能问题的一般排查思路
综合前面这些内容，如果线上真的遇到哈希表相关的性能或正确性问题，我一般按这个顺序排查：
- 先确认数据量级。如果元素数量和初始容量严重不匹配，扩容会非常频繁，先考虑预分配容量。
- 再看 key 的哈希实现。用上面那个分布统计工具跑一遍，看看桶长度是否均匀。如果集中在少数几个桶，问题基本就定位到了。
- 确认 key 是否会中途改变哈希值。可变对象做 key 是数据查不到的常见元凶。
- 确认是否有并发操作。多线程同时 put 到同一个 HashMap，表现是数据丢失、无限循环（JDK 7 时代），这种情况直接换 ConcurrentHashMap。
- 如果怀疑链表退化和树化切换频繁，可以打印一下 bucket 的深度分布，进一步确认负载因子设置是否合理。
哈希表这个数据结构，原理上不过十行代码就能说清楚，但真正用好它，需要对散列函数、冲突策略、扩容机制和并发特性都有整体认识。希望这篇文章能帮你在遇到哈希表问题的时候，不只是"搜一下报错然后复制粘贴"，而是真正能判断问题出在哪个环节。
