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

6. TreeMap vs HashMap

关系

它们都是Map接口的实现类，用于存储键 - 值对，且都不允许重复的键。它们是满足不同场景需求的两种不同实现方案。

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

使用场景选择

• 使用 TreeMap当：你需要一个始终排序的键值对集合。例如，根据员工 ID 排序显示员工信息，或者需要频繁进行范围查找（如subMap，headMap，tailMap）。
• 使用 HashMap当：你只需要高效的存储和检索，不关心顺序。这是最常用的Map实现，在绝大多数场景下都是默认选择。

7. TreeSet vs HashSet

关系

与上面类似，它们都是Set接口的实现类，用于存储不重复的元素。TreeSet基于TreeMap实现，HashSet基于HashMap实现。因此，它们的区别本质上就是其底层Map实现的区别。

用法区别

使用场景选择

• 使用 TreeSet当：你需要一个去重且自动排序的集合。例如，从数据库读取一堆用户 ID，并希望它们按顺序排列。
• 使用 HashSet当：你只需要一个高效的、用于去重的集合，不关心顺序。这是最常用的Set实现。

8. 总结与记忆口诀

1. 实现关系：
   • TreeSet-> 包装了一个TreeMap（元素作 Key）
   • HashSet-> 包装了一个HashMap（元素作 Key）
2. 核心区别口诀：
   • TreeXxx（TreeMap/TreeSet）：有序，基于红黑树，需要元素可比较，性能 O(log n)。
   • HashXxx（HashMap/HashSet）：无序，基于哈希表，需要元素有哈希码，性能 O(1)。
3. 默认选择：
   • 在大多数不需要排序的场景下，优先选择HashMap和HashSet，因为它们的平均性能更好。
   • 只有在明确需要排序功能时，才选择TreeMap或TreeSet。

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

TreeMap（有序）

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

HashMap（无序）

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

TreeSet vs HashSet（有序 vs 无序）

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

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

**是的，100%确定。**​ 让我们从源码角度证明：

1. HashSet 的源码片段

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

2. TreeSet 的源码片段

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

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

// 模拟一个 "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 
    } 
}

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

这是一个非常巧妙的设计：

1. 代码复用：不需要重新实现哈希算法或红黑树，直接复用 Map 的成熟实现。
2. Set 的特性：Set 的核心要求就是元素不重复，这正好对应 Map 的Key 不重复特性。
3. 简单高效：只需要一个固定的虚拟对象（PRESENT）作为 Value，所有 Key 共享这一个 Value，节省内存。

12. 总结表格

所以当面试官问"Set 的底层是 Map 吗'，你可以自信地回答：是的，HashSet 基于 HashMap 实现，TreeSet 基于 TreeMap 实现，Set 元素就是 Map 的 Key，用一个固定的虚拟对象作为 Value。