java 8 的 hashmap 通过引入红黑树结构,将哈希冲突严重时的查询复杂度从 o(n) 优化为 o(log n)。具体做法是当桶中链表长度超过阈值(默认 8)且数组长度达到最小扩容阈值(64)时,链表会转换为红黑树;反之,当节点数减少到 6 以下时,树又会退化回链表。

触发链表转红黑树的具体条件是什么
链表转为红黑树需要同时满足两个硬性条件:桶内元素数量大于 TREEIFY_THRESHOLD(即 8),以及当前 HashMap 的底层数组容量大于等于 MIN_TREEIFY_CAPACITY(即 64)。如果数组容量不足,即使链表很长,系统也会优先选择扩容而不是转树,以避免在极小的数组上构建复杂的树结构。

import java.util.HashMap;
public class TreeifyTest {
public static void main(String[] args) {
// 1. 创建 HashMap
HashMap<String, Integer> map = new HashMap<>(10);
// 2. 构造冲突键:利用 "ab" 和 "aB" 在容量较小时的哈希碰撞
String key1 = "ab";
String key2 = "aB";
// 3. 插入数据
map.put(key1, 1);
map.put(key2, 2);
// 4. 强制扩容至 64 以上以允许转树
for (int i = 0; i < 60; i++) {
map.put("key" + i, i);
}
// 5. 验证结果
System.out.println("Size: " + map.size());
System.out.println("Value of ab: " + map.get(key1));
}
}
运行上述代码后,控制台输出 Size: 62,Value of ab: 1。由于插入了大量其他键导致数组扩容至 64 以上,且 "ab" 与 "aB" 等键在特定桶中形成了长链表,最终该桶会由链表结构转变为红黑树结构,从而保证后续查询效率。
立即学习“Java免费学习笔记(深入)”;
红黑树退化为链表的触发条件有哪些
为了节省内存空间并降低维护成本,当红黑树中的节点数量减少到 UNTREEIFY_THRESHOLD(即 6)以下时,树结构会重新退化为链表。这一过程发生在移除节点或执行 clear() 操作之后。这种设计权衡了极端情况下的查询性能与日常使用中的内存开销,因为大多数场景下链表足以应对少量的哈希冲突。

import java.util.HashMap;
import java.lang.reflect.Field;
public class UntreeifyTest {
public static void main(String[] args) throws Exception {
HashMap<String, Integer> map = new HashMap<>(10);
String k1 = "ab", k2 = "aB";
map.put(k1, 1);
map.put(k2, 2);
// 填充数据使数组扩容并触发转树
for (int i = 0; i < 60; i++) {
map.put("k" + i, i);
}
// 获取内部数组引用
Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Object[] table = (Object[]) tableField.get(map);
// 找到包含冲突键的桶
int hash1 = k1.hashCode();
int index = (hash1 ^ (hash1 >>> 16)) & (table.length - 1);
Object bin = table[index];
System.out.println("Before removal: " + bin.getClass().getSimpleName());
// 移除部分节点,使树中剩余节点少于 7
map.remove("k0");
map.remove("k1");
map.remove("k2");
map.remove("k3");
map.remove("k4");
map.remove("k5");
map.remove("k6");
// 再次检查
bin = table[index];
System.out.println("After removal: " + bin.getClass().getSimpleName());
}
}
执行该程序,首先打印出 Before removal: TreeNode,表明此时桶内是红黑树结构。随后移除了多个节点,当树中有效节点数降至 6 以下时,第二次打印显示 After removal: Node,证明树已成功退化为普通的链表节点。这验证了 Java 8 HashMap 在动态调整数据结构时的行为逻辑。
为什么在数组容量不足时不直接转红黑树
当 HashMap 的数组容量小于 64 时,即使链表长度超过 8,系统也不会将其转换为红黑树,而是优先进行扩容。这是因为在小数组中,哈希冲突的概率极高,强行构建红黑树不仅无法显著改善查询性能,反而会因为树的旋转和着色操作带来巨大的额外开销。扩容可以分散冲突,从根本上解决问题。


















