Java Academy · 课时

树化与性能

Q: 「树化与性能」这节课中我会学到什么？

了解 Java 8+ 如何处理冲突 你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

了解 Java 8+ 如何处理冲突

树化与性能 是 CoddyKit 上的免费 Java Academy 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Java Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Java Academy 课程共包含 4 节课。

冲突问题

在 Java 8 之前，包含大量冲突的桶会变成长链表。该桶中的查找性能会下降到 O(n)。

攻击者可以利用这一点，通过精心构造的键发起拒绝服务攻击，让所有键都哈希到同一个桶。

public class Main {
    public static void main(String[] args) {
        // All these strings can be made to collide in one bucket
        System.out.println("FB".hashCode() == "Ea".hashCode());
    }
}

Java 8 的树化

Java 8 增加了树化功能。当单个桶包含太多条目时，链表会转换为平衡的红黑树。

此时，该桶中的查找复杂度会从 O(n) 变为O(log n)。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 1000; i++) m.put(i, i);
        System.out.println("Lookups stay fast: " + m.get(742));
    }
}

阈值：TREEIFY_THRESHOLD

常量 TREEIFY_THRESHOLD 的值为8。桶达到 8 个条目时会转换为树。

但还有第二个条件：表的容量也必须至少达到 MIN_TREEIFY_CAPACITY（64），否则映射会改为扩容。

public class Main {
    public static void main(String[] args) {
        int TREEIFY_THRESHOLD = 8;
        int MIN_TREEIFY_CAPACITY = 64;
        System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
        System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
    }
}

先扩容，后树化

如果桶溢出但表仍然很小（小于 64），HashMap 会先扩容表。

扩容通常会重新分配条目并消除热点，因此树化只是哈希分布确实很差时的最后手段。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16);
        for (int i = 0; i < 50; i++) m.put(i, i);
        // Many resizes happened before any treeify would
        System.out.println("size = " + m.size());
    }
}

取消树化

树并非永久存在。如果删除操作使桶缩小到 UNTREEIFY_THRESHOLD（6）以下，树会还原为链表。

8（树化）与 6（取消树化）之间的间隔可以避免在边界处反复切换。

public class Main {
    public static void main(String[] args) {
        System.out.println("TREEIFY_THRESHOLD   = 8");
        System.out.println("UNTREEIFY_THRESHOLD = 6");
        System.out.println("Gap prevents flip-flopping at the edge");
    }
}

树需要可比较性或标识顺序

红黑树必须为其条目排序。HashMap 首先比较哈希码；如果键实现了 Comparable，则使用它来打破平局，否则根据类名和对象标识进行稳定的平局处理。

实现了 Comparable 的键（例如 String 或整数类型）可以提供最清晰的树排序。

public class Main {
    public static void main(String[] args) {
        System.out.println("String is Comparable: " + ("a" instanceof Comparable));
        System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
    }
}

实际影响

对于大多数哈希码良好的实际程序，您永远不会看到树化。桶会保持较短。

即使哈希质量较差或受到恶意构造，树化这一安全机制也能将最坏情况下的查找复杂度限制在 O(log n)。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("alpha", 1);
        m.put("beta", 2);
        m.put("gamma", 3);
        // Tiny buckets, plain linked lists, no trees needed
        System.out.println(m.get("beta"));
    }
}

常量 hashCode 会强制树化

如果您故意返回常量 hashCode，所有键都会落入同一个桶。当容量达到 64 或更大时，该桶就会树化。

这展示了安全机制的作用，但这是一种设计坏味道。请改进 hashCode。

import java.util.HashMap;
import java.util.Map;

public class Main {
    static class Bad implements Comparable<Bad> {
        final int v;
        Bad(int v) { this.v = v; }
        @Override public int hashCode() { return 1; } // forces collisions
        @Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
        @Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
    }
    public static void main(String[] args) {
        Map<Bad, Integer> m = new HashMap<>();
        for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
        System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
    }
}

树的内存开销

树节点比普通链表节点更大，因为它们存储了父节点、左节点、右节点和颜色引用。

这也是树化作为后备方案而非默认方案的另一个原因：树用内存换取最坏情况下的速度。

public class Main {
    public static void main(String[] args) {
        System.out.println("Node: hash, key, value, next");
        System.out.println("TreeNode: + parent, left, right, prev, red flag");
        System.out.println("=> trees cost more memory per entry");
    }
}

如何避免树化

您几乎不应依赖树化。请通过以下方式避免它：

编写分布良好的 hashCode()。
使用内置类型或记录类作为键。
预先设置映射容量以减少冲突。

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Main {
    record Key(int a, int b) {}
    public static void main(String[] args) {
        Map<Key, Integer> m = new HashMap<>(256);
        for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
        System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
    }
}

性能总结

HashMap 操作的开销：

良好的哈希：平均 O(1)。
链式桶：每个桶最坏为 O(n)。
树化的桶：每个桶为 O(log n)。

树化限制了最坏情况，但良好的 hashCode 可以让您保持在 O(1) 的性能范围内。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(1 << 14);
        for (int i = 0; i < 10000; i++) m.put(i, i);
        System.out.println("10k entries, O(1) get: " + m.get(9999));
    }
}

快速检查

请测试您对树化的了解。

回顾

您已了解现代 HashMap 如何处理冲突：

当容量至少为 64 时，桶在达到 8 个条目后会树化。
树可以将最坏情况下的查找复杂度保持在O(log n)。
桶少于 6 个条目时会取消树化。
良好的 hashCode 意味着您很少会触发这一安全机制。

您已完成 HashMap 内部机制课程。

public class Main {
    public static void main(String[] args) {
        System.out.println("Treeification course complete");
    }
}

常见问题解答

「树化与性能」课时是免费的吗？

是的 — 「树化与性能」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Java Academy 课程的其余内容，请升级到 CoddyKit PRO。 Java Academy 课程共包含 4 节课。

「树化与性能」这节课中我会学到什么？

了解 Java 8+ 如何处理冲突你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Java Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Java Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 4 节课，共 4 节。

「树化与性能」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Java Academy 课中编写并运行代码吗？

能。每节 Java Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Java Academy