java数据结构-map&set

Java 中的 Map 和 Set 是集合框架（Java Collections Framework）中最核心的两种数据结构，它们都用于高效查找，但用途和底层实现有明显区别。下面从概念、接口、常用实现类、底层原理、使用场景、性能对比等方面进行系统讲解（基于 Java 17/21+ 的现状）。

1. Map 和 Set 的本质区别

特性	Map	Set
存储内容	键值对（Key-Value）	单个元素（只有 Key）
是否允许重复	Key 不可重复，Value 可重复	元素不可重复
是否有序	取决于实现（HashMap 无序）	取决于实现（HashSet 无序）
是否允许 null	多数实现 Key 和 Value 都允许 null（Hashtable 除外）	多数实现允许 null（TreeSet 除外）
本质关系	Set 的很多实现内部依赖 Map	HashSet 底层就是 HashMap
主要用途	键 → 值 映射、缓存、配置、计数	去重、成员判断、唯一元素集合

一句话总结：
Set ≈ Map 的 Key 集合（不存 Value，或 Value 都用同一个 dummy 对象）

2. Map 接口核心实现类对比

实现类	底层数据结构	是否有序	是否线程安全	null 支持	性能特点	典型使用场景
HashMap	数组 + 链表 + 红黑树 (JDK8+)	无序	否	Key/Value 都允许	增删查平均 O(1)，最差 O(log n)	普通键值存储、缓存（最常用）
LinkedHashMap	HashMap + 双向链表	插入顺序 / 访问顺序	否	支持	比 HashMap 略慢，但迭代有序	LRU 缓存、按插入顺序输出
TreeMap	红黑树	按 Key 排序	否	Key 不允许 null	增删查 O(log n)，天然有序	需要 Key 排序的场景（如字典序输出）
Hashtable	数组 + 链表	无序	是（全方法 synchronized）	不允许 null	性能较差，已过时	极少用（建议用 ConcurrentHashMap）
ConcurrentHashMap	数组 + 链表 + 红黑树 + 分段锁	无序	是（高并发）	Key 不允许 null	高并发下性能优秀	多线程缓存、并发计数

JDK8+ HashMap 重要变化：

• 链表长度 ≥ 8 且数组长度 ≥ 64 时 → 转为红黑树
• 红黑树节点 ≤ 6 时 → 退化为链表
• 极大改善哈希冲突严重时的最坏性能（从 O(n) → O(log n)）

3. Set 接口核心实现类对比

实现类	底层数据结构	是否有序	是否线程安全	null 支持	性能特点	典型使用场景
HashSet	HashMap（Key存元素，Value为固定对象）	无序	否	允许 null	增删查平均 O(1)	普通去重、快速成员判断
LinkedHashSet	LinkedHashMap	插入顺序	否	允许 null	比 HashSet 略慢，但迭代有序	需要保持插入顺序的去重集合
TreeSet	TreeMap（Key存元素）	按自然顺序/自定义排序	否	不允许 null	增删查 O(log n)，有序	需要排序的唯一元素集合
EnumSet	位向量（专门为枚举）	枚举定义顺序	否	不允许 null	极致性能	存储枚举类型的标志位
CopyOnWriteArraySet	CopyOnWriteArrayList 底层	无序	是（写时复制）	允许 null	读多写少场景性能好	并发读多、修改少的去重集合

4. 代码示例（常用操作对比）

import java.util.*;

public class MapSetDemo {
    public static void main(String[] args) {
        // ====================== Map 使用 ======================
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("apple", 3);        // 覆盖旧值
        map.put(null, 100);         // 允许 null key

        System.out.println(map.get("apple"));      // 3
        System.out.println(map.containsKey("banana")); // true
        System.out.println(map.getOrDefault("orange", 0)); // 0

        // Java 8+ 常用新方法
        map.computeIfAbsent("cherry", k -> 10);
        map.merge("apple", 5, Integer::sum);   // apple 变成 3+5=8

        // 遍历（推荐方式）
        map.forEach((k, v) -> System.out.println(k + " -> " + v));

        // ====================== Set 使用 ======================
        Set<String> set = new HashSet<>();
        set.add("java");
        set.add("python");
        set.add("java");           // 不会重复添加
        set.add(null);

        System.out.println(set.contains("java"));   // true
        System.out.println(set.size());             // 3（java只算一次）

        // TreeSet 自动排序
        Set<Integer> sortedSet = new TreeSet<>();
        sortedSet.add(5);
        sortedSet.add(1);
        sortedSet.add(8);
        System.out.println(sortedSet);   // [1, 5, 8]

        // LinkedHashSet 保持插入顺序
        Set<String> orderedSet = new LinkedHashSet<>();
        orderedSet.add("第三");
        orderedSet.add("第一");
        orderedSet.add("第二");
        System.out.println(orderedSet);   // [第三, 第一, 第二]
    }
}

5. 性能对比总结（平均情况，O表示时间复杂度）

操作	HashMap / HashSet	LinkedHashMap / LinkedHashSet	TreeMap / TreeSet	ConcurrentHashMap
put / add	O(1)	O(1)	O(log n)	O(1)
get / contains	O(1)	O(1)	O(log n)	O(1)
迭代全部元素	O(n)	O(n)	O(n)	O(n)
内存开销	中等	较高（链表）	较高（树节点）	较高
有序性	无	插入/访问顺序	Key 自然/自定义序	无

6. 面试高频问题快速回答

1. HashMap 为什么线程不安全？
   put 时可能出现死循环（JDK7）、数据丢失、多线程扩容冲突等。
2. HashSet 如何保证不重复？
   内部用 HashMap，add(e) → put(e, PRESENT)，依赖 equals() 和 hashCode()。
3. HashMap JDK7 和 JDK8 的区别？
   JDK7：头插法（扩容可能死循环）
   JDK8：尾插法 + 链表转红黑树（解决长链表性能问题）
4. 什么时候用 TreeMap / TreeSet？
   需要元素/Key 保持排序时（范围查询、最大最小值、字典序输出等）。
5. LRU 缓存怎么实现？
   LinkedHashMap + 重写 removeEldestEntry() 方法。
6. Java 21 新特性对 Map/Set 的影响？
   引入 SequencedCollection / SequencedSet / SequencedMap 接口，让 LinkedHashMap、LinkedHashSet 等可以更统一地访问首尾元素、反向视图等（但核心实现类没变）。

如果你想深入某个具体实现（如 HashMap 1.8 源码、红黑树转换、ConcurrentHashMap 分段锁原理、LRU 完整实现等），或者想要性能测试对比代码，告诉我，我可以继续展开讲解。