" />
文章

HashMap 的扩容、树化与红黑树选型：去哪儿面试题复盘

Posted recently Updated recently
By Administrator
16~21 min read

HashMap 的扩容、树化与红黑树选型：去哪儿面试题复盘

面试指北 · 去哪儿

题意

这道题表面在问“HashMap 的大小怎么变化、红黑树怎么回事”，实际面试官通常想确认几件事：

  1. 你是否清楚 JDK 1.7 与 JDK 1.8 中 HashMap 底层结构的变化；
  2. 是否理解扩容（resize / rehash）的触发条件、容量变化和元素重新分布；
  3. 是否知道链表什么时候转红黑树、红黑树什么时候退回链表；
  4. 是否能解释“为什么偏偏选红黑树”，而不是 B 树、B+ 树、普通二叉树或 AVL 树；
  5. 是否知道 HashMap 在多线程下仍然不安全，以及 ConcurrentHashMap 的大致演进。

所以回答时不要只背“数组 + 链表 + 红黑树”，而要把“结构、阈值、扩容、选型”串起来。

结论

HashMap 在 JDK 1.8 中采用“数组 + 链表/红黑树”的结构。默认初始容量是 16，默认负载因子是 0.75，扩容阈值 threshold = capacity * loadFactor，默认情况下就是 16 × 0.75 = 12。当元素数量超过阈值时触发扩容，容量通常翻倍，并把原有元素重新分布到新数组中。

单个桶里的链表过长时，会进入树化判断。树化阈值 TREEIFY_THRESHOLD 默认是 8，但并不是“链表一到 8 就无脑转红黑树”：还要看数组容量是否达到 MIN_TREEIFY_CAPACITY = 64，容量不足时优先扩容。红黑树节点数减少到 6 及以下时，会退化为链表，6 和 8 之间留出缓冲，避免频繁转换。

选择红黑树，是因为它在内存场景下能提供稳定的 O(log n) 最坏查询/插入复杂度，同时插入删除的旋转次数比 AVL 树少，实现成熟、综合成本低。B 树、B+ 树更适合磁盘和数据库索引场景，普通二叉树又可能退化成链表，因此不是 HashMap 的首选。

要点展开

1. JDK 1.7 与 JDK 1.8 的结构差异

JDK 1.7 及之前，HashMap 主要是“数组 + 链表”。每个数组位置称为一个桶（bucket），哈希冲突的元素以链表形式挂在同一个桶下面。查询时先定位桶，再顺着链表比较 key。

JDK 1.8 及之后，结构变成“数组 + 链表/红黑树”。大多数情况下仍然是链表；当某个桶冲突严重、链表过长时，才把该桶下的链表转成红黑树。注意，红黑树不是把整个 HashMap 变成树，而是只针对冲突严重的单个桶做优化。

这样设计的好处是：常规情况下链表足够简单，插入和遍历开销小；极端冲突情况下红黑树兜底，把最坏情况从 O(n) 拉回到 O(log n)。

2. 扩容机制：容量、阈值和 rehash

HashMap 有两个关键参数：

  • 容量 capacity：数组长度，默认 16，并且通常保持为 2 的幂；
  • 负载因子 loadFactor：默认 0.75，表示数组有多“满”时开始扩容。

扩容阈值是：

threshold = capacity * loadFactor

默认容量 16、负载因子 0.75 时，阈值为 16 × 0.75 = 12。当 size 超过阈值时触发扩容，例如容量为 16 时，插入第 13 个元素会触发扩容，容量通常变为 32。

扩容主要做两件事：

  1. 新建一个更大容量的数组，通常是原容量的 2 倍；
  2. 把旧数组中的元素重新分布到新数组中，这个过程常被称为 rehash。

JDK 1.8 在 rehash 时做了优化：因为容量是 2 的幂，扩容后元素的新位置只有两种可能——留在原索引，或者移动到“原索引 + 旧容量”。源码中通过 (e.hash & oldCap) == 0 把链表拆成低位链和高位链，分别挂到新数组的两个位置。这样比 JDK 1.7 中重新计算哈希和索引更高效，也能保持链表节点的相对顺序。

负载因子 0.75 是空间和时间的折中：太小会频繁扩容、浪费空间；太大则哈希冲突变多，链表变长，查询效率下降。

3. 树化与退化：不是“超过 8 就立刻变树”

HashMap 中和树化相关的阈值主要有：

  • TREEIFY_THRESHOLD = 8：链表长度达到树化阈值时，进入 treeifyBin 判断；
  • MIN_TREEIFY_CAPACITY = 64：数组容量达到 64 才允许真正树化，否则优先扩容；
  • UNTREEIFY_THRESHOLD = 6：树中节点数减少到 6 及以下时，退化为链表。

因此更准确的说法是：链表过长时会尝试树化，但如果当前数组容量还比较小，HashMap 会认为冲突严重可能是因为“桶太少”，于是先扩容，而不是马上建树。扩容后元素被分散，冲突可能自然缓解。

为什么阈值是 8 和 6？这背后有概率和工程折中的考虑。在负载因子 0.75 的情况下，哈希分布理想时，一个桶中链表长度达到 8 的概率非常低，红黑树主要是极端冲突下的兜底方案。6 和 8 之间留出缓冲区，是为了避免元素数量在临界值附近反复“树化—退化”，造成不必要的结构转换开销。

4. 为什么引入红黑树

链表查询需要从头到尾比较，时间复杂度是 O(n)。当某个桶冲突非常严重时，链表会显著拖慢查询和插入。红黑树是一种自平衡二叉查找树，通过左旋、右旋和变色维持近似平衡，保证树高在 O(log n) 级别，因此最坏情况下的查找、插入、删除可以稳定在 O(log n)。

红黑树有几个适合 HashMap 的特点：

  • 它不要求像 AVL 树那样严格平衡，插入删除时旋转次数相对少；
  • 查询、插入、删除的复杂度稳定；
  • JDK 中已有成熟实现和平衡逻辑，TreeMap 等结构也基于红黑树，维护成本低；
  • 在内存随机访问场景下，红黑树的节点规模和操作开销比较可控。

所以红黑树不是为了“绝对最快”，而是为了在常规链表和极端冲突之间取得一个工程上合适的平衡。

5. 多线程下的 HashMap 问题

HashMap 不是线程安全的。多线程同时读写可能出现：

  • 数据覆盖或丢失；
  • size 不准确；
  • 扩容时结构错乱；
  • JDK 1.7 中扩容采用头插法，极端并发下可能形成环形链表，导致查询死循环；
  • JDK 1.8 改为尾插法后，环形链表问题基本得到缓解，但 HashMap 仍然不是并发安全的，依然可能出现数据不一致。

需要并发安全时，应使用 ConcurrentHashMap。JDK 1.7 的 ConcurrentHashMap 使用 Segment 分段锁，默认分成多个段，不同段之间可以并发操作；JDK 1.8 取消了 Segment 分段锁的设计，改为 CAS + synchronized 锁住桶的头节点，并在冲突严重时使用链表/红黑树。面试中如果被追问，可以沿着“分段锁 -> CAS + synchronized + 红黑树”这条线展开。

6. 为什么不用 B 树、B+ 树或普通二叉树

这个问题要从使用场景出发回答。

B 树、B+ 树的典型场景是磁盘存储和数据库索引。 它们通过多路分叉降低树高，让一次磁盘 I/O 能加载一个页或块，减少寻道次数。B+ 树还把数据放在叶子节点，叶子之间用链表连接，非常适合范围查询。但 HashMap 主要工作在内存中，定位桶依靠数组随机访问，不需要为了磁盘页去设计多叉结构。B 树/B+ 树节点更大、分裂合并逻辑更复杂，在内存小节点场景下不一定划算。

普通二叉查找树的问题是可能退化。 如果插入的 key 哈希分布不均匀，普通 BST 可能退化成一条链表，最坏复杂度回到 O(n)，那就失去了优化意义。

AVL 树平衡更严格，查询略快，但插入删除旋转更多。 HashMap 不仅查询，还要频繁插入、删除和扩容，红黑树“近似平衡”的策略综合开销更低。

红黑树则是折中方案。 它保证 O(log n) 级别的高度，插入删除的调整成本可控，JDK 中实现成熟，适合作为链表过长时的兜底结构。

至于跳表等结构，它们在有序并发容器中可能有优势，但 HashMap 不要求有序，也不以范围查询为目标，引入跳表反而增加实现复杂度。

7. 面试口述版

可以这样组织回答：

JDK 1.8 的 HashMap 是数组 + 链表/红黑树。默认容量 16，负载因子 0.75，阈值是 capacity * loadFactor，默认就是 12。元素数量超过阈值时扩容，容量通常翻倍，JDK 1.8 通过高低位拆分来重新分布元素，避免全部重新计算索引。

当某个桶的链表过长时会触发树化判断，树化阈值是 8，但还要满足数组容量至少 64；容量不够时优先扩容。红黑树节点减少到 6 及以下时会退回链表，6 和 8 之间留缓冲，避免频繁转换。

引入红黑树是为了把极端冲突下的链表查询从 O(n) 优化到 O(log n)。没有选 B 树、B+ 树，是因为它们更适合磁盘页和数据库索引场景；普通二叉树可能退化成链表；AVL 树旋转更频繁。红黑树在内存场景下综合成本比较合适。

另外 HashMap 不是线程安全的，JDK 1.7 并发扩容可能出现环形链表，JDK 1.8 虽然改了尾插法，但仍可能数据不一致，并发场景应该用 ConcurrentHashMap。

易错点与对比

易错点 更准确的理解
链表长度一超过 8 就立刻转红黑树 还要看数组容量是否达到 64；容量不足时先扩容
红黑树节点少了就马上退化 退化阈值是 6，节点数小于等于 6 时退化，和 8 之间留缓冲
扩容阈值等于容量 阈值是 capacity * loadFactor，默认容量 16 时阈值是 12
HashMap 容量一开始就分配 16 JDK 1.8 通常是第一次 put 时懒初始化，默认目标容量是 16
红黑树让整个 HashMap 变成树 只是单个冲突严重的桶从链表转成红黑树
JDK 1.8 的 HashMap 没有死循环问题就线程安全了 仍然不安全，可能数据覆盖、丢失、size 不准
B+ 树查询更强，所以 HashMap 也该用 B+ 树优势在磁盘 I/O 和范围查询，HashMap 是内存键值查找，不要求有序
普通二叉树也能 O(log n) 普通 BST 可能退化成链表，最坏是 O(n)

再对比几种结构：

  • 链表：实现简单，冲突少时够用，冲突多时退化为 O(n)；
  • 普通二叉搜索树：理想情况 O(log n)，但可能退化成链表；
  • AVL 树：平衡严格，查询快，插入删除旋转多；
  • 红黑树：近似平衡，查询、插入、删除综合表现均衡；
  • B 树/B+ 树：多路平衡，适合磁盘页、数据库索引和范围查询；
  • 跳表：适合有序并发结构，但 HashMap 不需要有序。

小结

HashMap 的“大小变化”核心是容量、负载因子、阈值和扩容 rehash；“红黑树”核心是桶内冲突严重时的兜底优化。两者连起来看，就是 HashMap 在常规情况下保持数组 + 链表的简单高效，在极端冲突下用红黑树保证最坏复杂度，同时通过 8 和 6 两个阈值避免结构频繁转换。面试时把“结构演进、扩容条件、树化条件、红黑树选型、多线程安全”这五点讲清楚，基本就能覆盖大多数追问。

面试指北
License:  CC BY 4.0