面经策

让你设计一个 HashMap ，怎么设计？ ​

  • 标签：后端、系统设计、场景题

🏛 业务架构师 ​

设计 HashMap 的核心是在冲突、时间和空间三者间做权衡，我按存储结构、哈希、扩容三块讲，最后给出业务视角。

存储结构：数组 + 链表 + 红黑树

  • 主干是 Node 数组（桶），hash 冲突时形成链表
  • 链表长度到 8 且数组长度 ≥ 64 时转红黑树，查询从 O(n) 降到 O(log n)，退化为 6 时转回——防哈希碰撞攻击（恶意构造 key 把容器打成 O(n)）

哈希设计

java
h = key.hashCode() ^ (h >>> 16) // 高低位异或扰动
index = (n - 1) & h              // 位运算取模，要求容量是2的幂

扰动函数让高位信息参与低位运算，减少小数组容量下的冲突聚集。

扩容机制

  • 负载因子 0.75（空间与再哈希成本的平衡点）、容量翻倍增长
  • JDK 8 优化：扩容时节点要么留原位、要么移动"旧容量"的偏移量，无需重算 hash

关键操作语义：put 覆盖旧值返回旧值；并发下 fail-fast；null key 存 index 0。

业务架构师视角的收尾

  • 这题考的是权衡意识，但生产中我的一条原则：能预估量级就传初始容量，new HashMap<>(expectedSize / 0.75 + 1) 一次到位，避免扩容抖动——高频路径上这是零成本收益。
  • 选型即架构：需要 LRU 用 LinkedHashMap，并发用 ConcurrentHashMap，有序遍历用 TreeMap。理解数据结构是为了在对的业务场景选对的容器，而不是重造它。

🏗 系统架构师 ​

设计 HashMap 我会按"哈希函数、冲突处理、扩容机制、极端场景防御"四块讲，每个决策都讲清权衡。

哈希函数 key 的 hashCode 高低位做扰动（h ^ (h >>> 16)），让高位信息参与低位桶选择——因为桶下标只取低位，不扰动的话分布差的 key 会大量碰撞。

冲突处理：链地址 + 红黑树 桶内链表，头插改尾插（1.8，避免扩容成环）。链表长度超 8 且数组 ≥ 64 时转红黑树，把最坏查找从 O(n) 降到 O(log n)；删除到 6 时退化回链表（留 2 的滞后防抖动）。阈值选 8 是泊松分布下链长到 8 的概率约千万分之六，正常 hash 下根本到不了，树化本质是对哈希攻击和异常分布的防御。

扩容机制 负载因子 0.75（空间与查询的平衡点）：元素数 > 容量 × 0.75 时容量翻倍。关键优化：容量是 2 的幂，所以 rehash 时每个节点要么留原桶、要么移动到"原下标 + 旧容量"的新桶——不需要重算 hash，只需看新增那一位是 0 还是 1，把 O(n log n) 的重哈希降到 O(n)，且可以拆成高低位两条链一次迁移。

线程安全与工程化 明确不保证线程安全，并发场景给出 ConcurrentHashMap（CAS + 桶级 synchronized）。再加工程细节：初始容量建议 pre-size（expectedSize / 0.75 + 1）避免中途扩容；反序列化不可信数据时的 DoS 风险要限树化上限。

这套回答的逻辑是：每个魔数（8、6、0.75、2 的幂）背后都有一个可推导的原因，能讲出推导过程才算真懂。

💻 全栈开发专家 ​

我按 JDK8 HashMap 的成熟结构来设计：数组 + 链表 + 红黑树。

核心设计点

  • 哈希扰动：(h = key.hashCode()) ^ (h >>> 16)，让高位也参与运算，减少低位相似 key 的碰撞（比如 Float 的哈希集中在低位）。
  • 容量为 2 的幂：这样取模退化为 hash & (cap-1) 位运算；扩容翻倍后，元素要么留在原桶、要么移动 2^n 的偏移，判断 hash & oldCap 一位即可，迁移 O(1) 定位。
  • 链表长度 >= 8 且数组 >= 64 才树化，节点 < 6 退回链表；树化阈值 8 源于泊松分布，正常负载因子下链表到 8 的概率约千万分之六。
  • 负载因子 0.75：空间与查询成本的折中，超过就 2 倍扩容 rehash。

put 流程（伪代码）

java
int i = hash & (cap - 1);
if (table[i] == null) table[i] = newNode(hash, key, value);
else // 比较 hash 与 equals：命中替换；链尾追加（尾插，JDK7 头插并发扩容会成环）；
     // 链长 >= 8 树化
if (++size > threshold) resize(); // 2 倍扩容 + 迁移

踩过的坑

  • JDK7 头插法在并发扩容时链表成环导致 CPU 100%，JDK8 改尾插仍不保证线程安全，并发场景必须 ConcurrentHashMap。
  • 大数据量要预估容量 new HashMap<>((int)(n / 0.75f) + 1)，避免反复扩容。