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 <p>运行上述代码后,控制台输出 Size: 62,Value of ab: 1。由于插入了大量其他键导致数组扩容至 64 以上,且 "ab" 与 "aB" 等键在特定桶中形成了长链表,最终该桶会由链表结构转变为红黑树结构,从而保证后续查询效率。</p>
<h2>红黑树退化为链表的触发条件有哪些</h2>
<p>为了节省内存空间并降低维护成本,当红黑树中的节点数量减少到 UNTREEIFY_THRESHOLD(即 6)以下时,树结构会重新退化为链表。这一过程发生在移除节点或执行 clear() 操作之后。这种设计权衡了极端情况下的查询性能与日常使用中的内存开销,因为大多数场景下链表足以应对少量的哈希冲突。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill13407" title="Java基础版"><img
src="https://img.php.cn/upload/skill/001/246/273/6adaf20d79f23518.jpg" alt="Java基础版" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill13407" title="Java基础版" class="overflowclass">Java基础版</a>
<p class="overflowclass">编写健壮 Java 代码的基础能力,覆盖空指针防护、相等性判断与基础异常处理。</p>
</div>
<a rel="nofollow" href="/xiazai/skill13407" title="Java基础版" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p><img src="https://img.php.cn/upload/article/001/242/473/179506219388825.png?x-oss-process=image/resize,p_40" alt="Java HashMap 怎么用红黑树优化查询"></p>
<pre class="brush:php;toolbar:false;">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 >> 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());
}
}</string>
执行该程序,首先打印出 Before removal: TreeNode,表明此时桶内是红黑树结构。随后移除了多个节点,当树中有效节点数降至 6 以下时,第二次打印显示 After removal: Node,证明树已成功退化为普通的链表节点。这验证了 Java 8 HashMap 在动态调整数据结构时的行为逻辑。
为什么在数组容量不足时不直接转红黑树
当 HashMap 的数组容量小于 64 时,即使链表长度超过 8,系统也不会将其转换为红黑树,而是优先进行扩容。这是因为在小数组中,哈希冲突的概率极高,强行构建红黑树不仅无法显著改善查询性能,反而会因为树的旋转和着色操作带来巨大的额外开销。扩容可以分散冲突,从根本上解决问题。
Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南










