TreeSet 和 TreeMap 是 Java 集合框架中两个重要的类,它们的关系非常紧密。简单来说,TreeSet 是基于 TreeMap 实现的。可以将它们的关系理解为:TreeSet 是一个只包含'键'的 TreeMap。
下面详细解释一下:
1. 核心实现关系
在 Java 的源代码中,TreeSet内部维护了一个 对象(或 对象)作为其核心存储。当您向 中添加一个元素时,这个元素实际上被当作 放入了内部的 中,而 则是一个固定的、无意义的占位对象。
本文深入解析 Java 集合框架中 HashSet、HashMap、TreeSet 和 TreeMap 的核心关系。指出 TreeSet 基于 TreeMap 实现,HashSet 基于 HashMap 实现,元素作为 Key,固定对象作为 Value。对比了四者在底层数据结构(红黑树 vs 哈希表)、有序性、性能复杂度及 null 处理上的区别。通过源码片段和模拟代码验证了 Set 底层是 Map 的设计原理,并提供了使用场景建议:需排序选 Tree 系列,追求效率选 Hash 系列。
TreeSet 和 TreeMap 是 Java 集合框架中两个重要的类,它们的关系非常紧密。简单来说,TreeSet 是基于 TreeMap 实现的。可以将它们的关系理解为:TreeSet 是一个只包含'键'的 TreeMap。
下面详细解释一下:
在 Java 的源代码中,TreeSet内部维护了一个 对象(或 对象)作为其核心存储。当您向 中添加一个元素时,这个元素实际上被当作 放入了内部的 中,而 则是一个固定的、无意义的占位对象。
TreeMapNavigableMapTreeSetkeyTreeMapvalueTreeMap来说是键)进行自然排序(元素实现 Comparable接口)或根据构造时传入的 Comparator 进行排序。遍历时,元素会按照排序后的顺序输出。| 特性 | TreeSet | TreeMap |
|---|---|---|
| 存储内容 | 只存储单个元素(作为 key) | 存储键值对(key-value pairs) |
| 实现接口 | 实现 Set接口 | 实现 Map接口 |
| 重复元素 | 不允许重复元素 | 不允许重复的 key,但 value可以重复 |
| 数据关联 | 只关心元素本身 | 通过 key来关联和索引 value |
您可以把 TreeMap想象成一本字典,每个单词(key)后面都有对应的详细解释(value)。
而 TreeSet就像是这本字典的索引表或单词列表,它只关心有哪些单词(key),并不包含解释。
// TreeSet 的添加操作,内部近似于:
public boolean add(E e) {
return this.backingTreeMap.put(e, PRESENT) == null; // PRESENT 是一个固定的 Object 对象
}
// 所以,当您使用 TreeSet 时:
TreeSet<String> set = new TreeSet<>();
set.add("Apple"); // 内部相当于执行了:treeMap.put("Apple", new Object());
它们都是Map接口的实现类,用于存储键 - 值对,且都不允许重复的键。它们是满足不同场景需求的两种不同实现方案。
| 特性 | TreeMap | HashMap |
|---|---|---|
| 底层数据结构 | 红黑树(一种自平衡的二叉查找树) | 数组 + 链表 + 红黑树(JDK 1.8后,链表过长会树化) |
| 元素顺序 | 有序。根据键的自然顺序或构造时提供的Comparator进行排序。 | 无序。不保证插入顺序或任何其他顺序(但LinkedHashMap可以保持插入顺序)。 |
| 性能 O( ) | 增、删、查的平均时间复杂度为 O(log n)。 | 增、删、查的平均时间复杂度为 O(1)。在哈希冲突严重时可能退化。 |
| 键 Key 的要求 | 键必须实现Comparable接口,或者在构造时提供Comparator。 | 键必须正确实现hashCode()和equals()方法。 |
| 允许 null 键 | 不允许(因为需要比较,null无法比较)。 | 允许一个 null 键。 |
| 线程安全 | 非线程安全。 | 非线程安全。 |
| 内存占用 | 通常比 HashMap 占用更多内存,因为需要维护树结构(父、左、右指针等)。 | 相对较低,但为了减少哈希冲突,需要有负载因子控制,可能存在部分空间未利用。 |
TreeMap当:你需要一个始终排序的键值对集合。例如,根据员工 ID 排序显示员工信息,或者需要频繁进行范围查找(如subMap,headMap,tailMap)。HashMap当:你只需要高效的存储和检索,不关心顺序。这是最常用的Map实现,在绝大多数场景下都是默认选择。与上面类似,它们都是Set接口的实现类,用于存储不重复的元素。TreeSet基于TreeMap实现,HashSet基于HashMap实现。因此,它们的区别本质上就是其底层Map实现的区别。
| 特性 | TreeSet | HashSet |
|---|---|---|
| 底层实现 | 基于 TreeMap(红黑树) | 基于 HashMap(哈希表) |
| 元素顺序 | 有序。元素按自然顺序或指定的Comparator排序。 | 无序。不保证任何顺序。 |
| 性能 O( ) | 增、删、查的平均时间复杂度为 O(log n)。 | 增、删、查的平均时间复杂度为 O(1)。 |
| 元素的要求 | 元素必须实现Comparable接口,或者在构造时提供Comparator。 | 元素必须正确实现hashCode()和equals()方法。 |
| 允许 null 元素 | 不允许(取决于比较器,但默认自然排序不允许)。 | 允许一个 null 元素。 |
| 线程安全 | 非线程安全。 | 非线程安全。 |
| 内存占用 | 较高(维护树结构)。 | 较低。 |
TreeSet当:你需要一个去重且自动排序的集合。例如,从数据库读取一堆用户 ID,并希望它们按顺序排列。HashSet当:你只需要一个高效的、用于去重的集合,不关心顺序。这是最常用的Set实现。TreeSet-> 包装了一个TreeMap(元素作 Key)HashSet-> 包装了一个HashMap(元素作 Key)TreeXxx(TreeMap/TreeSet):有序,基于红黑树,需要元素可比较,性能 O(log n)。HashXxx(HashMap/HashSet):无序,基于哈希表,需要元素有哈希码,性能 O(1)。HashMap和HashSet,因为它们的平均性能更好。TreeMap或TreeSet。import java.util.*;
public class OrderDemo {
public static void main(String[] args) {
// TreeMap - 自动按键排序(这里是字符串的自然顺序:字母顺序)
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Charlie");
treeMap.put(1, "Alice");
treeMap.put(4, "David");
treeMap.put(2, "Bob");
System.out.println("TreeMap 输出(按键排序):");
for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// 输出:
// 1: Alice
// 2: Bob
// 3: Charlie
// 4: David
// 注意:无论怎么插入,遍历时都是按数字键 1,2,3,4 的顺序
// TreeMap 特有的有序操作:获取子映射
System.out.println("\nTreeMap 范围查询(2 到 3 之间的键):");
SortedMap<Integer, String> subMap = treeMap.subMap(2, 4); // [2, 4)
System.out.println(subMap); // 输出:{2=Bob, 3=Charlie}
}
}
import java.util.*;
public class OrderDemo {
public static void main(String[] args) {
// HashMap - 不保证任何顺序
HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(3, "Charlie");
hashMap.put(1, "Alice");
hashMap.put(4, "David");
hashMap.put(2, "Bob");
System.out.println("HashMap 输出(不保证顺序,可能与插入顺序不同):");
for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// 可能的输出(每次运行可能不同):
// 1: Alice
// 2: Bob
// 3: Charlie
// 4: David
// 或者:
// 3: Charlie
// 1: Alice
// 4: David
// 2: Bob
}
}
import java.util.*;
public class SetOrderDemo {
public static void main(String[] args) {
// TreeSet - 有序
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("Orange");
treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Cherry");
System.out.println("TreeSet(字母顺序排序):");
for (String fruit : treeSet) {
System.out.println(fruit);
}
// 输出:
// Apple
// Banana
// Cherry
// Orange
// HashSet - 无序
HashSet<String> hashSet = new HashSet<>();
hashSet.add("Orange");
hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Cherry");
System.out.println("\nHashSet(不保证顺序):");
for (String fruit : hashSet) {
System.out.println(fruit);
}
// 可能的输出(每次可能不同):
// Orange
// Apple
// Cherry
// Banana
}
}
**是的,100%确定。** 让我们从源码角度证明:
// JDK 中的 HashSet 源码(简化版)
public class HashSet<E> {
private transient HashMap<E, Object> map; // 关键:内部维护一个 HashMap
// 虚拟的 Value 值,所有 Key 共享这一个对象
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>(); // 构造时创建 HashMap
}
public boolean add(E e) {
return map.put(e, PRESENT) == null; // 将元素作为 Key,PRESENT 作为 Value 放入 HashMap
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT; // 从 HashMap 中移除 Key
}
}
// JDK 中的 TreeSet 源码(简化版)
public class TreeSet<E> {
private transient NavigableMap<E, Object> m; // 维护一个 NavigableMap(TreeMap 实现了它)
private static final Object PRESENT = new Object();
public TreeSet() {
this(new TreeMap<E, Object>()); // 构造时创建 TreeMap
}
TreeSet(NavigableMap<E, Object> m) {
this.m = m;
}
public boolean add(E e) {
return m.put(e, PRESENT) == null; // 同样,元素作为 Key
}
}
// 模拟一个 "MyHashSet",使用 HashMap 作为底层存储
class MyHashSet<E> {
private HashMap<E, Object> map;
private static final Object DUMMY = new Object(); // 虚拟值
public MyHashSet() {
map = new HashMap<>();
}
public boolean add(E element) {
// 如果 map 中已经存在这个 key,put 会返回旧值(不是 null)
// 如果不存在,put 返回 null
return map.put(element, DUMMY) == null;
}
public boolean contains(E element) {
return map.containsKey(element);
}
public boolean remove(E element) {
return map.remove(element) == DUMMY;
}
public int size() {
return map.size();
}
}
public class SetIsMapDemo {
public static void main(String[] args) {
MyHashSet<String> mySet = new MyHashSet<>();
System.out.println("添加 Apple: " + mySet.add("Apple")); // true
System.out.println("添加 Banana: " + mySet.add("Banana")); // true
System.out.println("再次添加 Apple: " + mySet.add("Apple")); // false(已存在)
System.out.println("集合大小:" + mySet.size()); // 2
System.out.println("包含 Banana? " + mySet.contains("Banana")); // true
}
}
这是一个非常巧妙的设计:
PRESENT)作为 Value,所有 Key 共享这一个 Value,节省内存。| 集合类 | 底层实现 | 虚拟 Value 对象 | 本质 |
|---|---|---|---|
| HashSet | HashMap | private static final Object PRESENT = new Object() | 只使用 HashMap 的 Key 部分 |
| TreeSet | TreeMap | 同上 | 只使用 TreeMap 的 Key 部分 |
所以当面试官问"Set 的底层是 Map 吗',你可以自信地回答:是的,HashSet 基于 HashMap 实现,TreeSet 基于 TreeMap 实现,Set 元素就是 Map 的 Key,用一个固定的虚拟对象作为 Value。

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online