面经策

假设有一个 1G 大的 HashMap，此时用户请求过来刚好触发它的扩容，会怎样？让你改造下 HashMap 的实现该怎样优化？ ​

  • 标签：后端、场景题

🏛 业务架构师 ​

1G 大 HashMap 触发扩容，后果是一次全量 rehash：所有 entry 重新定位，期间 CPU 尖刺、内存翻倍、请求长尾恶化——因为扩容和请求处理竞争同一个资源，大促高并发时撞上扩容就是一次"莫名的"接口抖动，这类问题压测难复现、线上偶发，排查代价极高。

问题拆解

  • JDK 8 虽然优化成高低位链拆分（不用重算 hash），但仍要遍历全部桶
  • 扩容期间新旧两份数组并存，1G 表瞬间多出 1G 内存压力，可能诱发 Full GC
  • 单线程完成迁移（协助迁移只在 put 时触发），大量"冷桶"迁移由一个请求买单

优化方向

方案一：预估容量，一次到位（业务上最划算）

java
// 10万数据: 100000 / 0.75 + 1，内部会圆整为2的幂
Map<K, V> map = new HashMap<>(133334);

能预估量级的场景（批量初始化、静态词库）直接消除扩容，零成本收益，这是我 review 代码时的常规要求。

方案二：渐进式 rehash（Redis 的思路） 扩容时不一次性迁移，而是新写走新表、读写时顺带迁移一小批桶 + 定时任务兜底迁移，把集中成本摊薄成每次操作的微小增量——适合改造为长期运行的基础组件。

方案三：分片 Map 把一个大 Map 按 key hash 拆成 N 个子 Map（类似 ConcurrentHashMap 的 Segment 思想），扩容只发生在单个分片，爆炸半径缩小 N 倍。

架构师收尾：真实业务里我会先问"为什么会有 1G 的单机 HashMap？"——大概率是把该放 Redis/外置存储的数据放进了进程内存，数据规模越界时，正确的动作是换存储模型而不是修补数据结构。

🏗 系统架构师 ​

会发生什么：JDK7 的 HashMap 扩容是头插法，并发下会成环导致 CPU 100%（死循环）；JDK8 改成尾插法解决了成环，但依然是"先扩 new 数组、再逐桶迁移"。触发扩容的那个请求要一次性完成全量 rehash——1G 的 HashMap 意味着百万级 entry，这次请求会卡顿几百毫秒到秒级，对 P99 是灾难；并发下还会丢数据。而且 1G 的对象要么年轻代放不下直接进老年代，加剧 Full GC 停顿。

改造思路（渐进式扩容 / 延迟 rehash）：

核心是把"一次全量迁移"摊薄到每次操作里，参考 Redis 的 dict 双表设计：

text
扩容时：分配 newTable，保留 oldTable，迁移指针 rehashidx=0
每次 get/put：顺带迁移 oldTable 的一个桶，rehashidx++
get：先查 newTable，miss 再查 oldTable
全部桶迁完后：丢弃 oldTable

工程上的配套手段：

  • 预扩容：如果能预估容量，初始化就指定 initialCapacity = 预期entry数 / 0.75 + 1，把扩容扼杀在摇篮里，这是我实战里最推荐的做法
  • 并发场景直接换 ConcurrentHashMap：JDK8 的 CHM 是 per-bin 迁移 + ForwardingNode（读到迁移中桶就转去新表），多线程协助扩容，这本质就是官方实现的渐进式改造
  • 超大缓存场景我其实不会用进程内 HashMap 扛，1G 数据放本地堆意味着 GC 压力和多节点不一致，换 Caffeine（堆外/受控权重）或 Redis 集群更合理

回答的关键是点出"停顿在单次操作上不可接受"，然后给出摊销迁移 + 协助扩容的思想。

💻 全栈开发专家 ​

1G 的 HashMap 触发扩容会发生什么：一次性分配 2G 新数组 + 全量 rehash 迁移，这一瞬间（1）内存翻倍可能直接 OOM，（2）迁移期间所有访问该 Map 的线程被卡住，接口大面积超时。

优化方向

  1. 预估容量，避免运行中扩容：
java
int cap = (int) (expected / 0.75f) + 1;
Map<K, V> map = new HashMap<>(cap); // 直接给足，tableSizeFor 内部取 2 的幂

像本地缓存这种可预估规模的场景，初始化给够是最低成本的手段。

  1. 拆分小 Map（分片）：把 1G 大 Map 按 key hash 拆成 N 个小 Map（分段思想），扩容的代价被摊薄到单个分片，毛刺从"秒级"降到"毫秒级"。Guava 的 Striped 或 ConcurrentHashMap 的思想都是这个方向。

  2. 渐进式 rehash（改造实现）：学 Redis——扩容时新表旧表并存，每次读写顺带迁移一个桶，后台定时任务分批搬完，把一次大停顿拆成无数小步。

  3. 多线程协助扩容：ConcurrentHashMap 的做法——发现正在扩容就帮着一起迁移（transfer 分段领取），人多力量大。

工程上的真话 真到 1G 数据量，我会直接放弃堆内 HashMap：换堆外（Chronicle Map）、Redis 或 Caffeine（带淘汰，不会无限涨），HashMap 扩容问题本质是"无界 + 集中式"的设计问题，改结构比改实现更治本。