哈希表这玩意儿写业务代码的人天天在用但真正停下来想过它内部怎么处理冲突的人不多。我在前几年做一次线上接口性能排查时踩过一个经典坑某个统计服务在压测时 QPS 卡在 1.2 万上不去CPU 却打满了最后定位到是某个高频 Map 的 key 设计得太集中哈希值低位全是零导致大量数据挤在少数几个桶里链表越挂越长单次 get 从 O(1) 退化成近似 O(n)。那次之后我把散列冲突处理的两大流派——链地址法和开放地址法——从头到尾捋了一遍也翻了几个主流语言标准库的实现。这篇就聊这个散列冲突处理、链地址法、开放地址法这三块内容以及它们在工程里到底该怎么选、怎么调、怎么排雷。不管你是刚学数据结构的学生还是写了几年业务想补底层认知的工程师都能从里面拿到能直接用的东西。1. 散列冲突到底在解决什么问题1.1 从一次接口抖动说起先把场景摆出来。你有一个用户会话服务需要根据userId快速查到会话数据。最朴素的做法是遍历数组O(n) 查找好一点的做法是排序后二分O(log n)而哈希表的思路是我不比较我直接算。用一个哈希函数把userId映射成数组下标一步跳过去拿到结果理想情况下是 O(1)。问题在于理想情况几乎不存在。你的下标空间是有限的比如数组长度 m 16而 key 的可能取值是无限的任意字符串都可能是 userId。把无限多的 key 塞进 16 个格子里必然有多个 key 算出同一个下标。这个现象就是散列冲突hash collision。它不是实现缺陷而是鸽巢原理的必然结果——格子比鸽子少就一定有鸽子要合住。所以哈希表的所有工程难度本质上都集中在同一件事上**当两个不同的 key 争抢同一个槽位时我怎么既保证正确性又尽量不牺牲性能。**围绕这个问题业界演化出两条主线一条是把冲突的元素挂起来往外扩展空间这就是链地址法另一条是在表内部继续找下一个空位向内消化这就是开放地址法。两条路线的取舍逻辑完全不同理解了这个分水岭后面所有细节都能自己推出来。1.2 冲突为什么躲不掉哈希函数的三条硬指标在讨论冲突处理之前得先明确哈希函数本身该满足什么。很多人一上来就纠结怎么消除冲突其实方向就错了冲突消不掉只能控制它的分布。一个好的哈希函数要满足三个条件。第一是确定性同一个 key 每次算出来的结果必须完全一致否则存进去就找不回来了这是底线。第二是均匀性输出值要尽量均匀铺满整个值域不能让某些区间过度密集我在开头提到的那个坑就是均匀性没做好。第三是高效性哈希计算本身要快如果一个哈希函数要跑几毫秒那省下来的查找时间全被吃掉了得不偿失。这里有个容易被忽略的细节哈希值的均匀和映射到下标的均匀是两回事。假设你的表长是 16取下标用的是hash % 16那么只有哈希值的低 4 位参与了运算高 28 位全是废的。如果你的 key 是自增 ID低位变化有规律低 4 位的分布可能非常糟糕。JDK 里那个被讨论烂了的扰动函数h ^ (h 16)就是为了解决这个——把高 16 位异或到低 16 位上让高位信息也参与进来。你可以不背这个公式但一定要有低位可能不够乱的警觉这是排查哈希性能问题的第一直觉。提示设计 key 的时候优先选择那些分布天然分散的字段。用连续自增 ID 或时间戳做 key 时先手动算一下低位是否够乱别等线上出问题再回头改。1.3 两条路线的分水岭往外挂还是往里找链地址法的思路非常直白数组的每个格子不放单个元素而是放一个容器早期是链表后来演化出红黑树等结构哈希到同一个下标的元素全部塞进这个容器里。查找时先定位到格子再在容器里线性找。它的核心特征是元素不占用表格本身的槽位表格只负责分桶真正的存储是靠额外的节点对象完成的。开放地址法走的是另一条路所有元素都存在表格数组内部一个槽位一个元素。当hash(key)算出的位置已经被占了就按照某个探测序列往后找直到找到空位。它的核心特征是没有额外的节点对象所有数据紧凑地排在一块连续内存里。这两句话看似只是实现差异但它带来的连锁反应非常深远链地址法对负载因子不敏感装到 1.0 甚至更高性能也不会崩因为桶可以无限挂开放地址法对负载因子极其敏感一旦接近 1.0探测次数会指数级恶化必须靠扩容来救。链地址法有指针跳转缓存不友好开放地址法内存连续缓存命中率高但删除操作很麻烦。下面两章我把这两条路线各自拆开讲。2. 链地址法的设计取舍与实操要点2.1 桶数组加链表的经典结构链地址法的结构可以概括成一句话一个数组每个元素是一个链表的头指针。插入时算出下标 i把新节点挂到table[i]的链上查找时算出下标 i沿着链表逐个比对 key。比对的时候要注意光比hashCode不够因为不同 key 可能有相同的哈希值必须再比一次equals这就是为什么 Java 里重写equals必须重写hashCode两者不一致会导致存进去找不回来。指针操作的细节也有讲究。挂链有两种方式头插和尾插。头插的代码最简洁新节点直接指向原来的头然后把自己设为新头O(1) 完成尾插需要先遍历到链尾插入成本 O(n)。JDK 7 的 HashMap 用的就是头插后来 JDK 8 改成尾插原因不完全是性能而是头插在并发扩容时会形成环形链表导致 get 操作死循环把 CPU 打到 100%这个事故在早期版本里真实发生过很多次。这是一个非常典型的教训单线程下等价的两个实现在多线程下可能是生与死的区别。链表节点的定义里通常会把hash值也缓存一份避免每次比对都重新计算。这看起来只是省了一次函数调用但当链表很长、查找频繁时收益是实打实的。JDK 的HashMap.Node就是这么干的final int hash是节点的一个字段。2.2 从链表到红黑树为什么要有树化纯链表有一个致命弱点如果哈希函数被恶意构造或者 key 的分布恰好很差所有元素都挤在一个桶里那么哈希表就退化成一个链表查询复杂度从 O(1) 变成 O(n)。这不只是性能问题还是安全问题攻击者可以故意构造大量哈希值相同的 key让你的服务 CPU 打满这就是所谓的哈希碰撞攻击。JDK 8 的应对方案是树化当某个桶里的链表长度达到8并且整个表的容量达到64时就把这条链表转成红黑树查询复杂度从 O(n) 降到 O(log n)。注意这里有两个条件TREEIFY_THRESHOLD 8和MIN_TREEIFY_CAPACITY 64。第二个条件很容易被忽略——如果表本身还很小比如容量只有 16那说明冲突多是因为表太小这时候扩容比树化更划算所以先扩容再说。那为什么阈值是 8 而不是 5 或者 10JDK 源码注释里给了答案在理想的随机哈希下桶中元素个数服从泊松分布平均每个桶 0.5 个元素一个桶里达到 8 个元素的概率大约是千万分之六。也就是说在哈希函数正常工作的情况下树化几乎永远不会触发它纯粹是为极端情况准备的兜底。反过来如果树化频繁触发那说明你的哈希函数或者 key 设计有问题应该去查根因而不是指望红黑树救场。还有一个细节是退化阈值。树化阈值是 8但退化回链表的阈值是6中间留了个空隙。为什么要留空隙因为如果两个阈值都是 8那么当一个桶在 7 和 8 之间反复增删时就会不停地在链表和树之间来回转换白白消耗性能。留一个缓冲区是为了防止这种抖动。2.3 负载因子 0.75这个数字是怎么来的负载因子load factor的定义是元素数量 / 桶数组长度记作 α。它决定了什么时候扩容。JDK 的默认值是0.75初始容量 16所以初始阈值是16 × 0.75 12插入第 13 个元素时触发扩容容量翻倍到 32阈值变成 24以此类推。0.75 这个数不是拍脑袋定的它是时间和空间的一次折中。负载因子越高空间利用率越高但冲突概率越大链表越长查询越慢负载因子越低冲突越少查询越快但浪费的内存越多而且扩容更频繁扩容本身是有成本的。0.75 大致是冲突概率开始明显上升的那个拐点。你可以把它理解成一个经验值源码注释里也明确说了这个值在时间和空间成本之间提供了良好的权衡。扩容本身也是门学问。容量为什么必须是 2 的幂因为当 length 是 2 的幂时hash % length等价于hash (length - 1)位运算比取模快得多。而且扩容翻倍时元素的迁移有规律可循原来在下标 i 的元素扩容后要么还在 i要么在i oldCap取决于hash oldCap这一位是 0 还是 1。JDK 8 利用这个规律把每个桶拆成低位链和高位链两条直接挂到新表对应的位置完全不用重新计算哈希。这个优化在小表上感知不明显但在容量上百万的大表上能省掉大量的哈希计算。// 扩容时的低位/高位拆分逻辑简化自 JDK 8 HashMap NodeK,V loHead null, loTail null; // 留在原下标 NodeK,V hiHead null, hiTail null; // 移到 j oldCap NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { // 关键判断多出来的那一位是 0 if (loTail null) loHead e; else loTail.next e; loTail e; } else { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; }2.4 手写一份能跑的链地址法哈希表光看源码不动手理解永远是浮的。下面这份实现砍掉了红黑树和并发处理保留了最核心的骨干扰动函数、头插、扩容拆分、阈值判断。你可以直接拿去跑加几个断点看迁移过程比看十遍源码都管用。public class ChainedMapK, V { static class NodeK, V { final int hash; final K key; V value; NodeK, V next; Node(int hash, K key, V value, NodeK, V next) { this.hash hash; this.key key; this.value value; this.next next; } } private NodeK, V[] table; private int size; private int threshold; private static final float LOAD_FACTOR 0.75f; private static final int DEFAULT_CAPACITY 16; SuppressWarnings(unchecked) public ChainedMap() { table (NodeK, V[]) new Node[DEFAULT_CAPACITY]; threshold (int) (DEFAULT_CAPACITY * LOAD_FACTOR); // 16 * 0.75 12 } // 扰动高 16 位异或到低位让高位也参与取下标 private static int spread(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); } public V put(K key, V value) { int hash spread(key); int i hash (table.length - 1); for (NodeK, V p table[i]; p ! null; p p.next) { if (p.hash hash (p.key key || key.equals(p.key))) { V old p.value; p.value value; return old; // key 已存在覆盖 } } table[i] new Node(hash, key, value, table[i]); // 头插 if (size threshold) resize(table.length 1); return null; } public V get(K key) { int hash spread(key); for (NodeK, V p table[hash (table.length - 1)]; p ! null; p p.next) { if (p.hash hash (p.key key || key.equals(p.key))) return p.value; } return null; } private void resize(int newCap) { NodeK, V[] old table; SuppressWarnings(unchecked) NodeK, V[] nt (NodeK, V[]) new Node[newCap]; for (int j 0; j old.length; j) { NodeK, V p old[j]; if (p null) continue; old[j] null; if (p.next null) { nt[p.hash (newCap - 1)] p; // 单节点直接落位 continue; } NodeK, V loH null, loT null, hiH null, hiT null; while (p ! null) { if ((p.hash old.length) 0) { if (loT null) loH p; else loT.next p; loT p; } else { if (hiT null) hiH p; else hiT.next p; hiT p; } p p.next; } if (loT ! null) { loT.next null; nt[j] loH; } if (hiT ! null) { hiT.next null; nt[j old.length] hiH; } } table nt; threshold (int) (newCap * LOAD_FACTOR); } }写完建议做三件事验证一是用 100 万个随机字符串灌进去统计每个桶的长度分布看看是否接近泊松分布二是故意构造一批hashCode相同的 key观察单桶长度和查询耗时三是把负载因子改成 0.5 和 0.9对比内存占用和查询 P99。这三个实验做完你对负载因子是权衡这句话会有体感。注意上面的实现是非线程安全的。多线程并发 put 会丢数据并发扩容还可能读到中间态。生产环境请用ConcurrentHashMap它用的是 CAS synchronized 锁单个桶不是锁整表。3. 开放地址法的探测策略与性能边界3.1 三种探测序列线性、二次、双重散列开放地址法的核心在于下一个位置怎么找这个规则叫探测序列。有三种主流打法差别很大。线性探测最简单slot (h i) mod mi 从 0 开始递增撞了就往后挪一格。它的优点是内存访问连续CPU 缓存友好而且实现短。缺点是会产生一次集群primary clustering一旦某一段连续槽位被占满后续任何映射到这段区间的 key 都要一路往后探越探越长把这段区间越撑越大最后恶化成探测大半张表才找到空位。二次探测改成slot (h ± i²) mod m跳着走。它缓解了一次集群但会产生二次集群所有初始位置相同的 key探测序列完全一样还是会在同一段区域里互相踩。而且它有表长约束为了能覆盖整张表m 通常要求是 4k3 形式的素数或者至少保证 m 是素数且负载因子小于 0.5。双重散列是目前理论上最优的方案用第二个哈希函数算步长slot (h1 i × h2) mod m。不同 key 即使 h1 相同h2 也可能不同探测路径完全岔开能最大程度避免集群。代价是每次探测多算一次哈希计算开销上升。而且 h2 必须与表长 m 互质否则探测序列会提前循环永远覆盖不到某些槽位。常用的做法是让 m 取素数h2 取prime - (h1 mod prime)这样天然保证 h2 落在[1, prime-1]区间内且与 m 互质。探测方式探测序列优点缺点表长要求线性探测(h i) mod m缓存友好实现最简单一次集群严重长探测链无特殊要求二次探测(h ± i²) mod m缓解一次集群二次集群覆盖不全4k3 素数双重散列(h1 i·h2) mod m分布最均匀几乎无集群每次多算一次哈希h2 与 m 互质3.2 删除的难题墓碑标记到底怎么用开放地址法最反直觉的地方在删除。链地址法删除很简单把节点从链表上摘掉就行前后元素不受影响。但开放地址法不行假如你把某个槽位直接清空那么一个原本因为冲突被挪到后面的元素它的探测链就断了——查找时走到这个空位会认为到此为止元素不存在可实际上它还在后面挂着。这就是探测链断裂。标准解法是墓碑标记tombstone。删除时不置空而是标记成一个特殊状态DELETED。查找时遇到DELETED不能停要继续往后探插入时遇到DELETED可以复用这个位置但要注意如果你已经在前面见过DELETED插入应该优先放到第一个DELETED的位置而不是一路探到最后的EMPTY否则会让整条链越拉越长。墓碑的副作用是假性饱和。删除再插入反复进行后表里可能到处都是DELETED实际元素没几个但探测路径却很长因为DELETED也会被跳过去。所以开放地址法的实现必须记录已用槽位 OCCUPIED DELETED在扩容判断里用这个值而不是实际元素个数并且在扩容时顺手清理所有墓碑。这一步非常关键不做的话一个长期运行的服务会慢慢退化到插入一次要探几十个位置。提示ThreadLocal 的内存泄漏问题本质上就是墓碑机制的一个变体。ThreadLocalMap 的 key 是弱引用GC 之后 key 变成 null这个槽位就成了逻辑上的墓碑但 value 是强引用还在所以必须手动调remove()清理。3.3 负载因子上限为什么开放地址法撑不住 0.9这是开放地址法最硬的约束。在成功查找的假设下线性探测的平均探测次数约等于(1 1/(1-α)) / 2不成功查找是(1 1/(1-α)²) / 2其中 α 是负载因子。把数字代进去看负载因子 α成功查找平均探测次数不成功查找平均探测次数0.251.171.390.501.502.500.752.508.500.905.5050.500.9510.50200.50这张表一眼就能看出问题。α 从 0.75 涨到 0.9成功查找只慢了 2 倍多但不成功查找慢了 6 倍到 0.95 直接是 200 次探测。而不成功查找在实际系统里意味着判断这个 key 不存在很多业务逻辑都要走这条路比如缓存穿透判断、去重。所以开放地址法的负载因子上限通常压在0.5 到 0.75之间留足安全边际。这也解释了为什么 CPython 的 dict 把扩容阈值定在2/3ThreadLocalMap 也是2/3Java 的一些开源高性能 Map 实现比如 Netty 的IntObjectHashMap也普遍用 2/3 左右。2/3 是一个甜点既不用太频繁扩容又把探测次数控制在可接受范围内。链地址法就宽松得多0.75 只是默认值你调到 1.0 也不会崩顶多链表长点这就是它更耐操的原因。3.4 用双重散列手写一个开放地址法 Map下面这个实现用双重散列容量取 2 的幂步长强制为奇数以保证与容量互质。为了对比我特意把状态机写得清楚一些你可以对照前面的链地址法看差异。public class DoubleHashProbingMapK, V { private static final byte EMPTY 0, OCCUPIED 1, DELETED 2; private static final int DEFAULT_CAPACITY 16; private Object[] keys; private Object[] values; private byte[] states; private int size; // 真实元素个数 private int used; // OCCUPIED DELETED用于扩容判断 private int mask; public DoubleHashProbingMap() { alloc(DEFAULT_CAPACITY); } private void alloc(int cap) { keys new Object[cap]; values new Object[cap]; states new byte[cap]; mask cap - 1; size 0; used 0; } private int hash(Object key) { int h (key null) ? 0 : key.hashCode(); h ^ (h 16); return h 0x7fffffff; // 保证非负 } // 步长必须是奇数才能与 2 的幂容量互质保证探测序列覆盖全表 private int step(int hash) { return (hash 16) | 1; } private int slot(int hash, int i) { return ((hash mask) i * step(hash)) mask; } public V put(K key, V value) { if ((used 1) * 3 keys.length * 2) grow(); // 负载因子 2/3 int hash hash(key); int firstDeleted -1; for (int i 0; i mask; i) { int s slot(hash, i); if (states[s] EMPTY) { int target (firstDeleted 0) ? firstDeleted : s; if (firstDeleted 0) { used; } // 复用了墓碑占位统计加一 keys[target] key; values[target] value; states[target] OCCUPIED; size; return null; } if (states[s] DELETED) { if (firstDeleted 0) firstDeleted s; // 记住第一个墓碑后面复用 continue; } if (keys[s].equals(key)) { V old (V) values[s]; values[s] value; return old; } } grow(); // 理论上到不了这里 return put(key, value); } public V get(K key) { int hash hash(key); for (int i 0; i mask; i) { int s slot(hash, i); if (states[s] EMPTY) return null; // 空位查找终止 if (states[s] OCCUPIED keys[s].equals(key)) return (V) values[s]; } return null; } public V remove(K key) { int hash hash(key); for (int i 0; i mask; i) { int s slot(hash, i); if (states[s] EMPTY) return null; if (states[s] OCCUPIED keys[s].equals(key)) { V old (V) values[s]; values[s] null; states[s] DELETED; // 打墓碑不能置 EMPTY size--; return old; } } return null; } SuppressWarnings(unchecked) private void grow() { Object[] ok keys, ov values; byte[] os states; int newCap keys.length 1; alloc(newCap); // 顺带清空所有墓碑 for (int i 0; i ok.length; i) { if (os[i] OCCUPIED) put((K) ok[i], (V) ov[i]); } } }这份代码有几个点值得反复看。put里的firstDeleted记录第一个墓碑是为了避免明明前面有空位却一路探到最后这个细节不做删除密集的场景下性能会明显劣化。grow里直接alloc重建天然把墓碑全清了。get遇到EMPTY立即返回遇到DELETED继续探——这两个分支的差异就是墓碑机制的全部精髓。4. 两种方案怎么选工程视角的对比4.1 核心差异对照表维度链地址法开放地址法存储方式桶数组 额外节点对象全部存在表内无额外节点负载因子上限可超过 1.0不敏感0.5~0.75敏感内存开销每个节点有指针开销无指针但有墓碑浪费缓存友好性差指针跳转好内存连续删除操作简单摘链即可复杂必须打墓碑极端情况哈希被攻击时退化为链表高负载时探测次数爆炸典型实现JDK HashMap、Go map、Redis dictCPython dict、ThreadLocalMap、Netty IntObjectHashMap4.2 内存布局决定下限为什么小表用开放地址法更香有一个规律非常明显当元素是小整数或短字符串、单条记录很小时开放地址法几乎全面胜出。原因在于缓存局部性。链地址法每访问一个元素要跳一次指针现代 CPU 一次内存访问几百个周期而一次缓存未命中就可能吃掉上百个周期跳几次之后 O(1) 的优势就被抹掉了。开放地址法所有数据在一块连续内存里一次加载能带进来一整条缓存行通常 64 字节后面几次探测大概率命中的都是同一个缓存行。反过来当 value 本身很大比如每条记录几百字节或者需要存储复杂对象时链地址法的优势就出来了。因为桶里只放引用实际数据在堆上指针跳转的成本相对于数据本身的处理成本占比下降缓存的重要性被稀释。Go 的 map 选择链地址法准确说是桶 溢出桶结构每个桶固定存 8 个 kv是因为它要支持任意类型的 value还要控制扩容时的迁移成本。而 CPython 的 dict 用开放地址法是因为 Python 的 dict 大量用于属性查找、关键字参数传递这些小而密的场景紧凑的内存放在这里收益极高。4.3 扩容策略翻倍、渐进还是等量扩容策略也是一个容易被忽略但影响很大的点。链地址法一般直接翻倍因为迁移逻辑简单利用hash oldCap拆链就行。开放地址法扩容也是翻倍居多因为容量得保持 2 的幂配合位运算取模或者素数配合双重散列。但 Redis 给出了第三种答案渐进式 rehash。Redis 的 dict 同时维护两张哈希表 ht[0] 和 ht[1]扩容时不一次性搬完而是维护一个rehashidx游标每次增删改查时顺带迁移一小批桶把一次性的 O(n) 阻塞摊薄到多次操作里。这个设计对 Redis 这种单线程、要求低延迟的服务是刚需因为一次性 rehash 一个百万级 key 的表可能阻塞几百毫秒直接打爆 P99 延迟。代价是实现复杂度大幅上升代码里到处都要处理两张表同时存在的状态。Go 的 map 也有类似思想它的扩容分为增量扩容装载因子超过 6.5容量翻倍和等量扩容溢出桶太多但元素不多容量不变只做整理两种迁移同样是渐进式的通过oldbuckets指针和nevacuate进度来标记。如果你在做自己的哈希表实现数据量不大时直接一次性 rehash 就行但一旦单表元素超过十万级渐进式就值得考虑了。5. 常见问题与排查技巧实录5.1 哈希碰撞攻击从原理到防御前面提过哈希碰撞攻击这里展开讲。攻击原理很简单攻击者构造大量哈希值相同的 key全部塞进一个桶让链地址法退化成链表单次查询从 O(1) 变成 O(n)。如果每请求有几千个这样的 key服务端 CPU 会在极短时间内被打满。2011 年前后多个主流语言和框架都爆过这类漏洞包括 PHP、Java、Python 的 Web 框架。防御手段有几种。第一种是随机化哈希种子让攻击者无法离线算出一批碰撞 key因为每次进程启动的种子不同。Python 从 3.3 开始默认开启PYTHONHASHSEED随机化字符串哈希每次运行都不一样而 Java 的String.hashCode()是固定的这也是 Java 更容易被针对的原因之一。第二种是引入密钥化的哈希函数比如 SipHash攻击者不知道密钥就算不出碰撞。Rust 的 HashMap 默认用 SipHash 系列代价是比普通哈希慢一些。第三种就是树化JDK 8 用的这招把最坏情况从 O(n) 压到 O(log n)。排查这类问题看现象基本就能定位CPU 突然打满、某个接口 RT 暴涨、GC 次数没明显变化这时候用jstack抓几次线程栈如果发现大量线程卡在HashMap.get或者HashMap.put的调用栈上而且栈里能看到同一个 Map 的方法基本就实锤了。进一步可以用 async-profiler 或者 arthas 的profiler做火焰图火焰集中在某个哈希方法上就找到根因了。注意如果你的服务接收外部不可信输入并直接用作 Map 的 key务必限制请求体大小和单个请求的 key 数量。这是最廉价也最有效的第一道防线。5.2 开发中常见的坑与速查表现象可能原因排查思路解决方式get 拿不到刚 put 的值重写了 equals 没重写 hashCode检查两个方法是否成对实现用 IDE 自动生成或 Lombok单次查询耗时忽长忽短哈希分布不均个别桶超长打印桶长度分布直方图改进哈希函数或换 keyCPU 高但 GC 正常哈希碰撞攻击或 key 过度集中jstack 看栈 火焰图限制输入、随机化种子、树化内存持续上涨不释放ThreadLocal 未 remove墓碑堆积dump 堆看 ThreadLocalMap显式调用 remove()多线程下数据丢失用了非线程安全的 HashMap检查并发写入路径换 ConcurrentHashMap扩容时接口卡顿一次性 rehash 大表观察卡顿是否周期性出现渐进式 rehash 或预估容量其中预留初始容量这个点我想单独说。很多人创建 Map 时用默认构造器然后一口气灌 10 万条数据中间会触发多次扩容每次都是全量 rehash。如果提前用new HashMap(200000)之类的方式指定容量能省掉十几次扩容。注意这里的容量要按预计元素数 / 0.75 1来估直接传元素个数可能导致最后一次扩容这个细节 JDK 源码里也处理了tableSizeFor会把容量向上取到 2 的幂。5.3 实测下来的几条经验第一条别迷信 O(1)。哈希表的 O(1) 是摊还意义上的单次操作最坏是 O(n)。如果你在做延迟敏感的服务比如要求 P99 在 10ms 以内要关注的是最坏情况而不是平均值。这就是为什么金融交易系统里有些关键路径宁可手写跳表或者有序数组也不用哈希表。第二条开放地址法的性能对删除比例极其敏感。我曾在一个去重服务里用开放地址法业务模式是插入一批、删除一批、再插入跑了一周之后 QPS 掉了 40%。排查下来就是墓碑堆积实际元素只有 3 万但used计数到了 8 万探测路径拉得极长。后来改成定期重建表 提高 GC 墓碑的频率问题就解决了。这个坑任何文档都不会告诉你。第三条容量选素数还是 2 的幂取决于你用哪种取模方式。如果你的哈希函数质量足够好2 的幂 位运算是更快的选择但前提是扰动函数要做好否则低位不均匀的问题会被放大。如果你的哈希函数质量一般或者用的是简单的乘法散列那选素数 取模更稳因为素数能让分布更均匀。Java 选了前者Python 的 dict 选的是后者表长总是 2 的幂但不是靠取模而是靠自定义的探测序列绕开了这个问题。第四条测试哈希表一定要造坏数据。随机数据测不出问题因为随机数据的分布天然均匀。你要专门构造一批哈希值低位相同的 key一批连续整数一批长度相近的短字符串用这些数据压测才能暴露真实的性能上限。这也是我开头那次事故的直接教训——当时压测用的是随机 UUID怎么压都没事一上线换成业务 ID 就崩了。5.4 一个可以复用的哈希质量自检脚本最后送一个我经常用的自检小工具。思路很简单往表里灌 N 个真实的 key统计每个桶的负载情况算一下方差和最大桶长。如果最大桶长超过平均值的 5 倍或者空桶比例低于 30%基本可以判定哈希分布有问题。public static void inspect(Object[] keys, int tableSize) { int[] buckets new int[tableSize]; for (Object k : keys) { int h (k null) ? 0 : k.hashCode(); h ^ (h 16); // 与 JDK 保持一致的扰动 buckets[h (tableSize - 1)]; } int empty 0, max 0; double sum 0; for (int c : buckets) { if (c 0) empty; max Math.max(max, c); sum c; } double avg sum / tableSize; double var 0; for (int c : buckets) var (c - avg) * (c - avg); var / tableSize; System.out.printf(空桶比例%.2f%% 平均%.2f 最长%.2d 标准差%.2f%n, empty * 100.0 / tableSize, avg, max, Math.sqrt(var)); }理想情况下随机 key 灌进 2 的幂大小的表空桶比例应该接近e^(-α)α 是负载因子当 α 0.75 时空桶比例约 47%。如果你实测出来空桶只有 10% 几而最长桶长是平均值的十几倍那说明哈希函数或者 key 的分布有明确问题别犹豫先改 key 设计再谈别的优化。我个人在带团队时的一贯建议是哈希表是基础设施用之前先想清楚三件事——key 是什么、key 的分布怎么样、这块表会不会成为热点。这三件事想明白了链地址法和开放地址法选哪个其实是自然就有了答案。小对象、高密度、可预测的负载选开放地址法享受缓存和内存的双重收益通用场景、value 复杂、负载波动大选链地址法图一个稳健和低心智负担。至于那些把两种方案混着用、根据负载动态切换的实现等你把上面这些细节都摸透了再去看它们的源码会发现每一处设计都能找到对应的理由那种看懂了的感觉比背多少个公式都值。
