【反八股 01】HashMap 的设计参数是怎么来的

八股会问你：HashMap 的底层结构是什么？扩容因子是多少？

反八股问三个问题：为什么这么设计？代价是什么？什么时候会翻车？

一、八股怎么教 HashMap

1. 数组 + 链表（JDK 8 后链表长度 ≥ 8 转红黑树） 2. 默认容量 16，负载因子 0.75，扩容阈值 12 3. 扩容时容量翻倍，重新 hash 4. 线程不安全，用 ConcurrentHashMap

这是正确的，但八股没有回答的问题是：

• 为什么负载因子是 0.75 而不是 0.5 或 0.8？
• 链表转红黑树的阈值为什么是 8？
• HashMap 占堆 30% 就该上 Redis，这个说法对吗？
• 初始容量设不设，到底有多大影响？

二、为什么负载因子是 0.75

0.75 是时间和空间的折中点，不是随便选的。

负载因子越小（如 0.5）： → 数组更早扩容，链表更短，查询更快 → 但浪费大量内存（一半的桶是空的） 负载因子越大（如 1.0）： → 内存利用率高，桶基本塞满才扩容 → 但链表很长，查询退化到 O(n) 0.75 的数学依据： 泊松分布下，负载因子 0.75 时 桶中元素个数超过 8 的概率 < 0.00000006 → 红黑树几乎不会被触发（极端碰撞场景除外）

代价：0.75 意味着永远有约 25% 的内存浪费。如果你的场景是"内存极度紧张但查询不频繁"，可以调到 0.9。但大多数时候不要动它。

边界：负载因子调到多少都没法解决 hash 碰撞攻击的问题——如果攻击者故意构造 hashCode 相同的 key，所有元素挤在一个桶里，查询直接退化到 O(n)。这是 DoS 攻击的经典手法。

三、为什么链表转红黑树的阈值是 8

这个数字背后是统计学推导，不是经验值。

理想 hash 函数下，元素落入每个桶的数量服从泊松分布： 桶中元素数量 概率 0 0.6065 1 0.3033 2 0.0758 3 0.0126 4 0.0016 5 0.0002 6 0.00002 7 0.000002 8 0.00000006 ← 阈值在这里 超过 8 个元素落入同一个桶的概率是千万分之一。 如果真出现了，说明 hash 函数有问题或者遭到了碰撞攻击。 此时转红黑树 O(log n) 兜底，防止性能雪崩。

代价：红黑树节点（TreeNode）占用的内存是普通节点（Node）的 2 倍（多了 parent/left/right/prev/boolean 六个字段）。如果正常场景下也转树，内存会暴涨。

边界：退化阈值是 6（不是 8），中间留了 2 的缓冲区，避免频繁在链表和红黑树之间切换。如果 hashCode 实现不好导致频繁树化，应该修 hashCode，而不是调阈值。

四、HashMap 占堆多少该上 Redis？

网上常说"占堆 30% 就该换 Redis"。这个说法缺乏数据支撑。我们跑了 20 组实测数据来验证。

实验设计

变量： JVM 堆大小：512m / 1g HashMap 占堆比例：10% / 20% / 30% / 40% / 50% 操作模式：纯读 / 混合（67% 读 + 33% 写） 关键修正：启动后台线程持续分配临时对象，模拟生产 GC 压力 环境：Dragonwell 17 / G1GC / 每组 300 万次查询

结果：p99 延迟（微秒）

512m 堆：

Redis 同机房 p99 ≈ 1000 微秒。HashMap 占堆 50% 时 p99 只有 2~4 微秒，差了 250 倍。

"30% 就该换"为什么不对

GC 停顿确实存在（1~2ms/次），但只影响正在执行的那一个操作。 300 万次操作中大约 100 次 GC = 0.003% 受影响。 要影响到 p99（1% 阈值），需要 30000 次 GC，这不现实。

什么时候真的该上 Redis

判断标准不是延迟，是"数据要不要跨进程共享"： 单进程用 → HashMap，占堆 50% 也没问题 多进程共享 → Redis，别犹豫 数据比内存大 → Redis / 数据库 延迟不是换的理由——G1GC 下 HashMap 的 p99 比 Redis 快 250 倍，换过去反而更慢。

五、初始容量设不设有区别吗

实测数据（100 万条数据，负载因子 0.75）：

不设初始容量（default 16）： put 100 万条 → 扩容 17 次（16→32→64→...→1048576） 总耗时：~120ms 每次 resize 要重新计算所有 key 的位置 + 复制数据 设初始容量为 1333334（1000000 / 0.75 + 1）： put 100 万条 → 0 次扩容 总耗时：~80ms 提速 33% 内存差异：几乎一样（最终都是同样的数组大小）

代价：初始容量设太大同样有问题。100 条数据设new HashMap<>(1000000)，一开始就占 4MB 数组空间。更常见的错误是不评估实际业务数据量，直接套公式算出一个巨大的数字——比如业务实际只会有 500 条数据，却按 20 万算出 262,144 的初始容量，白白浪费内存。

边界：数据量小于 1000 时差别不大（resize 只有一两次，耗时 < 1ms）。数据量超过 10 万时，不设初始容量会明显感觉到 resize 的开销。

实战建议：公式不是万能药，关键是先搞清楚你的业务到底有多少数据：

// 第一步：评估业务数据量// - 这个 Map 的数据来源是什么？数据库查出来的？接口返回的？配置文件？// - 数据量上限是多少？是 100 条还是 10 万条？// - 数据量是固定的还是随时间增长的？// 第二步：确认数据量后，按公式计算intexpectedSize=500;// ← 这个数字来自业务评估，不是拍脑袋Map<String,String>map=newHashMap<>((int)(expectedSize/0.75)+1);// 常见误区：// ❌ 不管业务多大，一律 new HashMap<>(262144) — 浪费内存// ❌ 从配置文件读 10 条数据，初始容量给 100000 — 浪费内存// ✅ 确认数据源最多返回 500 条，初始容量给 668 — 合理// ✅ 不确定数据量，用默认 16 — 也能用，就是多几次 resize// 或者用 Guava（更直观）Map<String,String>map=Maps.newHashMapWithExpectedSize(500);

六、容量为什么是 2 的幂：位运算与扰动函数

位运算替代取模

HashMap 计算元素桶下标时，需要把 hash 值映射到数组索引：index = hash % length。取模是除法运算，CPU 需要约 20~40 个时钟周期。而hash & (length - 1)是一次位与运算，只需 1 个周期——快 20~40 倍。

但& (length - 1)等价于% length仅当 length 是 2 的幂：

length = 16（二进制 10000） length - 1 = 15（二进制 01111） hash & 15 → 结果范围 0~15，等价于 hash % 16

如果 length 不是 2 的幂呢？

length = 15（二进制 1111） length - 1 = 14（二进制 1110） hash & 14 → 结果只能是 0,2,4,6,8,10,12,14（8 个偶数） 奇数位置永远为空 → 一半桶浪费 → 碰撞率翻倍

代价：2 的幂意味着容量只能是 2, 4, 8, 16, 32… 不能精细控制。new HashMap<>(100)实际容量被向上取到 128（最近的 2 的幂），浪费 28%。

扩容翻倍（16→32→64→…）保持 2 的幂不变，位运算始终有效——这就是扩容"翻倍"而不是"加固定值"的原因。

为什么默认是 16 而不是 8 或 32

容量太小（如 2 或 4）： length - 1 = 1 或 3（二进制 01 或 011） 只有 1~2 位参与路由 → hash 值高位全被忽略 → 碰撞极高 容量太大（如 1024）： 默认只有 12 个元素（16 × 0.75）就占 8KB 数组 → 浪费内存 16 是折中：4 位参与路由（足够分散），空数组占 128 字节（可忽略）

扰动函数：hash ^ (hash >>> 16)

即使容量是 2 的幂，容量小时参与路由的位数太少：

容量 16 时，length - 1 = 0b0000...01111 hash & 0b0000...01111 → 只有低 4 位起作用，高 28 位被掩盖 假设两个 key： key1.hashCode() = 0b10101010_10101010_10101010_1101 key2.hashCode() = 0b01010101_01010101_01010101_1101 低 4 位完全相同 → 路由到同一个桶 → 碰撞 但它们的高位差异很大

JDK 的解决方案——扰动函数：

// HashMap.hash() 源码（JDK 8）staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}

原理：把 hash 的高 16 位异或到低 16 位，让高位特征参与路由 原始 hash: 10101010 10101010 10101010 11010000 右移 16 位: 00000000 00000000 10101010 10101010 异或结果: 10101010 10101010 00000000 01111010 ↑ 高位特征混入了低位 再 & (length-1) 时，高 16 位和低 16 位的特征都在了

代价：一次右移 + 一次异或，几乎零成本。这不是完美的散列（只混合了一次），但用最低的代价显著降低了碰撞概率。

边界：容量超过 2^16 = 65536 时，扰动函数的效果递减——低位本身已经足够参与路由。但 HashMap 很少超过这个大小，超过 65536 个元素通常该考虑数据库或 Redis 了。

七、线程不安全到底会怎样

八股说"HashMap 线程不安全"，但很少有人解释具体会出什么事。

并发 put 的三个问题： 1. 数据丢失 线程 A 和线程 B 同时 put 到同一个桶 A 写入 node1 → B 写入 node2 覆盖了 node1 → node1 的数据丢了 2. resize 死循环（JDK 7） 并发扩容时，头插法导致链表成环 后续 get 遍历链表进入死循环 → CPU 100% JDK 8 改成尾插法解决了这个问题 3. size 不准确 size++ 不是原子操作，两个线程同时 +1 实际只加了 1

JDK 8 没有死循环了，但数据丢失和 size 不准确仍然存在。

解决方案的取舍：

ConcurrentHashMap 的代价：每个 put/get 多了 CAS 操作，单线程性能比 HashMap 低约 10-15%。只有在真正并发写入时才值得用。

八、总结：HashMap 的设计哲学

HashMap 的每个参数背后都有推导依据：

负载因子 0.75 → 时间和空间的统计最优解 树化阈值 8 → 泊松分布下千万分之一概率的兜底 初始容量 16 → 2 的幂，4 位参与路由，折中分散与内存 扩容翻倍 → 保持 2 的幂，hash & (length-1) 始终有效 扰动函数 → hash ^ (hash >>> 16)，零成本混合高低位 尾插法（JDK 8） → 解决并发 resize 死循环

记住这三个问题框架：

为什么这么设计？ → 统计学/性能/工程折中 代价是什么？ → 内存浪费/单线程开销/并发风险 什么时候会翻车？ → 碰撞攻击/内存不足/多线程写入

本文数据来自 JVM 实验和源码分析，完整测试代码见language-basics/模块。