Java 集合框架中 HashSet、HashMap、TreeSet 与 TreeMap 的关系解析

Java 集合框架中 HashSet、HashMap、TreeSet 与 TreeMap 的关系解析 | 极客日志

TreeMap

NavigableMap

TreeSet

key

TreeMap

value

特性	TreeSet	TreeMap
存储内容	只存储单个元素（作为 `key`）	存储键值对（`key-value` pairs）
实现接口	实现 `Set`接口	实现 `Map`接口
重复元素	不允许重复元素	不允许重复的 `key`，但 `value`可以重复
数据关联	只关心元素本身	通过 `key`来关联和索引 `value`

// 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());

特性	TreeMap	HashMap
底层数据结构	红黑树（一种自平衡的二叉查找树）	数组 + 链表 + 红黑树（JDK 1.8后，链表过长会树化）
元素顺序	有序。根据键的自然顺序或构造时提供的`Comparator`进行排序。	无序。不保证插入顺序或任何其他顺序（但LinkedHashMap可以保持插入顺序）。
性能 O( )	增、删、查的平均时间复杂度为 O(log n)。	增、删、查的平均时间复杂度为 O(1)。在哈希冲突严重时可能退化。
键 Key 的要求	键必须实现`Comparable`接口，或者在构造时提供`Comparator`。	键必须正确实现`hashCode()`和`equals()`方法。
允许 null 键	不允许（因为需要比较，`null`无法比较）。	允许一个 `null` 键。
线程安全	非线程安全。	非线程安全。
内存占用	通常比 HashMap 占用更多内存，因为需要维护树结构（父、左、右指针等）。	相对较低，但为了减少哈希冲突，需要有负载因子控制，可能存在部分空间未利用。

特性	TreeSet	HashSet
底层实现	基于 TreeMap（红黑树）	基于 HashMap（哈希表）
元素顺序	有序。元素按自然顺序或指定的`Comparator`排序。	无序。不保证任何顺序。
性能 O( )	增、删、查的平均时间复杂度为 O(log n)。	增、删、查的平均时间复杂度为 O(1)。
元素的要求	元素必须实现`Comparable`接口，或者在构造时提供`Comparator`。	元素必须正确实现`hashCode()`和`equals()`方法。
允许 null 元素	不允许（取决于比较器，但默认自然排序不允许）。	允许一个 `null` 元素。
线程安全	非线程安全。	非线程安全。
内存占用	较高（维护树结构）。	较低。

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 
    } 
}

// 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 
    } 
}

集合类	底层实现	虚拟 Value 对象	本质
HashSet	HashMap	`private static final Object PRESENT = new Object()`	只使用 HashMap 的 Key 部分
TreeSet	TreeMap	同上	只使用 TreeMap 的 Key 部分

Java 集合框架中 HashSet、HashMap、TreeSet 与 TreeMap 的关系解析

1. 核心实现关系

2. 共同特征

3. 主要区别

4. 一个简单的类比

5. 代码示例说明关系

6. TreeMap vs HashMap

关系

用法区别（核心在于底层数据结构）

使用场景选择

7. TreeSet vs HashSet

关系

用法区别

使用场景选择

8. 总结与记忆口诀

9. 代码示例：有序 vs 无序

TreeMap（有序）

HashMap（无序）

TreeSet vs HashSet（有序 vs 无序）

10. Set 的底层确实是 Map 吗？（代码证明）

1. HashSet 的源码片段

2. TreeSet 的源码片段

3. 自己模拟实现（最直观的理解）

11. 为什么 Set 要用 Map 实现？

12. 总结表格

更多推荐文章

相关免费在线工具

Java 集合框架中 HashSet、HashMap、TreeSet 与 TreeMap 的关系解析

1. 核心实现关系

2. 共同特征

3. 主要区别

4. 一个简单的类比

5. 代码示例说明关系

6. TreeMap vs HashMap

关系

用法区别（核心在于底层数据结构）

使用场景选择

7. TreeSet vs HashSet

关系

用法区别

使用场景选择

8. 总结与记忆口诀

9. 代码示例：有序 vs 无序

TreeMap（有序）

HashMap（无序）

TreeSet vs HashSet（有序 vs 无序）

10. Set 的底层确实是 Map 吗？（代码证明）

1. HashSet 的源码片段

2. TreeSet 的源码片段

3. 自己模拟实现（最直观的理解）

11. 为什么 Set 要用 Map 实现？

12. 总结表格

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具