Java 集合 Set、List、Map 辨析

一、概述

Java 集合框架（Java Collections Framework）是 Java 语言中最核心、最常用的部分之一。它提供了一套统一的 API 来存储、操作和传递数据。集合框架主要分为三大体系：

• List — 有序、可重复的集合
• Set — 无序（或特定顺序）、不可重复的集合
• Map — 键值对映射，键不可重复

它们都位于 java.util 包下，是日常开发中使用频率最高的数据类型。

二、Collection 接口层次结构

Java 集合框架的根接口是 Collection，它定义了集合最基本的操作（如 add、remove、size、iterator 等）。Collection 之下又划分出三个核心子接口：

Iterable (迭代器根接口)
  └── Collection (集合根接口)
        ├── List (有序、可重复)
        │     ├── ArrayList
        │     ├── LinkedList
        │     └── Vector (已过时)
        │
        ├── Set (不可重复)
        │     ├── HashSet
        │     │     └── LinkedHashSet
        │     └── SortedSet (排序)
        │           └── TreeSet
        │
        └── Queue (队列)
              ├── PriorityQueue
              └── Deque
                    └── ArrayDeque

Map (独立的键值对体系，不继承 Collection)
  ├── HashMap
  │     └── LinkedHashMap
  ├── Hashtable (已过时)
  └── SortedMap
        └── TreeMap

注意： Map 并不继承 Collection 接口，它自成一体作为键值对映射体系存在。但由于它同样属于集合框架的重要组成部分，通常与 List、Set 一并讨论。

三、List 接口 — 有序序列

特点： 元素有序（按插入顺序排列）、允许重复、允许 null。

3.1 ArrayList

ArrayList 是基于动态数组实现的 List。它的底层是一个 Object[] 数组，当容量不足时自动扩容（通常扩为原来的 1.5 倍）。

// 基本使用
List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
list.add("Apple");          // 允许重复
list.add(null);             // 允许 null

System.out.println(list);   // [Apple, Banana, Cherry, Apple, null]
System.out.println(list.get(1)); // Banana

// 遍历
for (String s : list) {
    System.out.println(s);
}

// 随机访问 — O(1)
String fruit = list.get(2); // Cherry

核心特性：

适用场景： 频繁随机访问、尾部插入/删除为主，很少在中间插入或删除。

3.2 LinkedList

LinkedList 是基于双向链表实现的 List。每个节点（Node）持有前驱和后继引用，元素之间通过指针链接。

List<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");

// 双向链表，也实现了 Deque 接口
LinkedList<String> linkedList = (LinkedList<String>) list;
linkedList.addFirst("First");    // 头部插入 O(1)
linkedList.addLast("Last");      // 尾部插入 O(1)
String first = linkedList.getFirst(); // O(1)
String last  = linkedList.getLast();  // O(1)

System.out.println(linkedList); // [First, Apple, Banana, Cherry, Last]

核心特性：

适用场景： 频繁在头部或中间插入/删除，对随机访问需求低。

3.3 ArrayList vs LinkedList 对比

经验法则： 90% 的场景应该默认使用 ArrayList，只有确定需要频繁头插或中间插删时才用 LinkedList。

四、Set 接口 — 不可重复集合

特点： 元素唯一（通过 equals() 和 hashCode() 判定）、不允许重复。

4.1 HashSet

HashSet 基于哈希表（实际使用 HashMap 实现），元素无序，查找效率极高。

Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Cherry");
set.add("Apple");        // 重复，不会被加入
set.add(null);           // 允许一个 null

System.out.println(set); // 输出顺序不确定，如 [Banana, Apple, Cherry]

// 判断是否存在 — O(1)
boolean exists = set.contains("Apple"); // true

// 遍历
for (String s : set) {
    System.out.println(s);
}

核心特性：

适用场景： 需要快速查找和去重，不关心元素顺序。

4.2 TreeSet

TreeSet 基于红黑树（实际使用 TreeMap 实现），元素按自然顺序或自定义 Comparator 排序。

Set<String> set = new TreeSet<>();
set.add("Banana");
set.add("Apple");
set.add("Cherry");

System.out.println(set); // [Apple, Banana, Cherry] — 自然升序

// 自定义排序（降序）
Set<String> descSet = new TreeSet<>(Comparator.reverseOrder());
descSet.add("Banana");
descSet.add("Apple");
descSet.add("Cherry");
System.out.println(descSet); // [Cherry, Banana, Apple]

// 范围查询
TreeSet<Integer> numbers = new TreeSet<>();
numbers.addAll(Arrays.asList(1, 3, 5, 7, 9, 2, 4, 6, 8));

System.out.println(numbers.first()); // 1
System.out.println(numbers.last());  // 9
System.out.println(numbers.headSet(5)); // [1, 2, 3, 4] — 小于 5
System.out(numbers.subSet(3, 7));    // [3, 4, 5, 6] — 范围 3~6

核心特性：

适用场景： 需要元素保持排序状态，或需要范围查询。

4.3 LinkedHashSet

LinkedHashSet 继承自 HashSet，在哈希表基础上额外维护一个双向链表来记录插入顺序。

Set<String> set = new LinkedHashSet<>();
set.add("Banana");
set.add("Apple");
set.add("Cherry");
set.add("Apple"); // 重复，忽略

System.out.println(set); // [Banana, Apple, Cherry] — 插入顺序

// 删除后重新添加会回到末尾
set.remove("Apple");
set.add("Apple");
System.out.println(set); // [Banana, Cherry, Apple]

核心特性：

适用场景： 既需要快速查找，又需要保持插入顺序。

4.4 HashSet vs TreeSet vs LinkedHashSet 对比

五、Map 接口 — 键值对映射

特点： 存储键值对（key-value），键唯一，值可重复。

5.1 HashMap

HashMap 基于哈希表实现（JDK 8+ 采用数组 + 链表/红黑树），是使用最广泛的 Map 实现。

Map<String, Integer> map = new HashMap<>();
map.put("Apple", 10);
map.put("Banana", 20);
map.put("Cherry", 30);
map.put("Apple", 15);     // 覆盖旧值
map.put(null, 0);         // key 和 value 都允许 null

System.out.println(map); // 顺序不确定

// 获取
Integer price = map.get("Apple");   // 15
Integer missing = map.get("Durian"); // null

// 遍历方式 1：entrySet
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

// 遍历方式 2：keySet
for (String key : map.keySet()) {
    System.out.println(key + " = " + map.get(key));
}

// 遍历方式 3：forEach (Java 8+)
map.forEach((k, v) -> System.out.println(k + " = " + v));

// 常用方法
map.containsKey("Apple");   // true
map.containsValue(20);      // true
map.getOrDefault("Durian", -1); // -1
map.putIfAbsent("Banana", 99);  // 已存在，不覆盖

核心特性：

适用场景： 通用键值映射，无特殊顺序要求。

5.2 TreeMap

TreeMap 基于红黑树实现，键按自然顺序或 Comparator 排序。

Map<String, Integer> map = new TreeMap<>();
map.put("Banana", 20);
map.put("Apple", 10);
map.put("Cherry", 30);

System.out.println(map); // {Apple=10, Banana=20, Cherry=30} — 键排序

// 自定义排序（按值长度？不，TreeMap 只比较键）
Map<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder());
reverseMap.put("Banana", 20);
reverseMap.put("Apple", 10);
reverseMap.put("Cherry", 30);
System.out.println(reverseMap); // {Cherry=30, Banana=20, Apple=10}

// 范围查询
TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(1, "One");
tm.put(3, "Three");
tm.put(5, "Five");
tm.put(7, "Seven");
tm.put(9, "Nine");

System.out.println(tm.firstKey());        // 1
System.out.println(tm.lastKey());         // 9
System.out.println(tm.lowerKey(5));       // 3  — 小于 5 的最大键
System.out.println(tm.higherKey(5));      // 7  — 大于 5 的最小键
System.out.println(tm.subMap(3, 8));      // {3=Three, 5=Five, 7=Seven}

核心特性：

适用场景： 需要按键排序存储，或需要键的范围查询。

5.3 LinkedHashMap

LinkedHashMap 继承 HashMap，额外维护一个双向链表来记录插入顺序（或访问顺序）。

// 默认：插入顺序
Map<String, Integer> map = new LinkedHashMap<>();
map.put("Banana", 20);
map.put("Apple", 10);
map.put("Cherry", 30);

System.out.println(map); // {Banana=20, Apple=10, Cherry=30} — 插入顺序

// 访问顺序：可用于实现 LRU 缓存
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
lru.put("A", 1);
lru.put("B", 2);
lru.put("C", 3);
lru.get("A");                   // 访问 A，A 被移到末尾
System.out.println(lru);        // {B=2, C=3, A=1} — 最近最少使用在头部

// 实现简易 LRU 缓存
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;

    public LRUCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }
}

LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("A", "1");
cache.put("B", "2");
cache.put("C", "3");
cache.get("A");                 // 使用 A
cache.put("D", "4");            // 触发淘汰，B 被移除
System.out.println(cache);      // {C=3, A=1, D=4}

核心特性：

适用场景： 需要保留键值对的插入顺序，或需要构建 LRU 缓存。

5.4 HashMap vs TreeMap vs LinkedHashMap 对比

六、时间复杂度总对比

† 摊还 O(1)，最坏情况下（大量哈希冲突）可能退化为 O(log n) 或 O(n)。

七、线程安全版本

上述所有集合实现都是非线程安全的。在多线程环境下，有以下几种方案保证线程安全：

7.1 使用 Collections 工具类包装

List<String> syncList    = Collections.synchronizedList(new ArrayList<>());
Set<String>  syncSet     = Collections.synchronizedSet(new HashSet<>());
Map<String,Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

// 注意：迭代时需要在外层同步
synchronized (syncList) {
    for (String s : syncList) {
        // 安全迭代
    }
}

缺点： 整个方法加 synchronized 块，并发性能差；迭代需手动同步。

7.2 使用 JUC 包中的并发集合（推荐）

java.util.concurrent 包提供了专为高并发设计的实现：

// 线程安全且性能更好的替代方案
List<String> list = new CopyOnWriteArrayList<>();
Set<String>  set  = new CopyOnWriteArraySet<>();
Set<String>  tree = new ConcurrentSkipListSet<>();     // 排序的线程安全 Set
Map<String,Integer> map = new ConcurrentHashMap<>();   // 最常用的并发 Map
Map<String,Integer> skipMap = new ConcurrentSkipListMap<>(); // 排序的并发 Map

CopyOnWriteArrayList

• 读操作无锁（读多写少的场景极快）
• 写操作创建新数组副本，写入后原子替换引用
• 适用： 读多写少、迭代操作远多于修改的场景（如监听器列表）

// 读多写少的典型场景
CopyOnWriteArrayList<String> events = new CopyOnWriteArrayList<>();
events.add("Event1");
events.add("Event2");
// 并发迭代安全，不会抛 ConcurrentModificationException
for (String e : events) {
    System.out.println(e);
}

ConcurrentHashMap

• JDK 7：分段锁（Segment，最多 16 个）
• JDK 8+：CAS + synchronized 对桶加锁，粒度更细，性能更好
• 完全支持多线程并发读写，迭代不需外层同步

ConcurrentHashMap<String, Integer> chm = new ConcurrentHashMap<>();
chm.put("A", 1);
chm.put("B", 2);

// 原子组合操作
chm.merge("A", 1, Integer::sum);   // A 变为 2
chm.computeIfAbsent("C", k -> 3);  // 不存在才计算

// 安全迭代
chm.forEach((k, v) -> System.out.println(k + " = " + v));

ConcurrentSkipListMap / ConcurrentSkipListSet

• 基于**跳表（Skip List）**实现，是 TreeMap / TreeSet 的并发版本
• 时间复杂度 O(log n)，支持排序和范围查询
• 无锁并发、高性能

ConcurrentSkipListMap<Integer, String> skipMap = new ConcurrentSkipListMap<>();
skipMap.put(3, "Three");
skipMap.put(1, "One");
skipMap.put(2, "Two");

System.out.println(skipMap); // {1=One, 2=Two, 3=Three} — 自动排序

// 范围查询一样可用
System.out.println(skipMap.subMap(2, 4)); // {2=Two, 3=Three}

7.3 线程安全方案对比

选型建议： 多线程环境下，优先使用 ConcurrentHashMap 替代 HashMap，使用 CopyOnWriteArrayList 替代读多写少的 ArrayList，使用 ConcurrentSkipListMap 替代需要排序的 TreeMap。

八、总结与实践建议

快速选型指南

需要快速查找？
  ├── 需要去重？
  │     ├── 不关心顺序 → HashSet (默认首选)
  │     ├── 需要排序   → TreeSet
  │     └── 需要插入顺序 → LinkedHashSet
  └── 键值对存储？
        ├── 不关心顺序 → HashMap (默认首选)
        ├── 需要排序   → TreeMap
        └── 需要插入顺序 → LinkedHashMap

需要有序序列？
  ├── 主要用索引访问 → ArrayList (默认首选)
  └── 频繁头插/中间插删 → LinkedList

多线程环境？
  ├── Map     → ConcurrentHashMap
  ├── Set     → CopyOnWriteArraySet / ConcurrentSkipListSet
  └── List    → CopyOnWriteArrayList

关键记忆点

1. ArrayList 是 List 的默认首选，只有明确需要头插/中间插删才考虑 LinkedList
2. HashSet / HashMap 是 Set / Map 的默认首选，它们提供 O(1) 操作的极致性能
3. TreeSet / TreeMap 用空间换排序，O(log n) 操作，支持范围查询
4. LinkedHashSet / LinkedHashMap 用少量内存换顺序保留，O(1) 操作 + 插入顺序
5. 多线程环境不要用原始集合类，改用 java.util.concurrent 下的实现
6. 注意 null 值的兼容性： TreeSet / TreeMap 不允许 null 键，HashSet/HashMap/LinkedHashSet/LinkedHashMap 允许

本文涵盖了 Java 集合框架中 List、Set、Map 三大体系的核心实现类的底层原理、性能对比、代码示例和线程安全方案，希望能帮助读者在实际开发中做出正确的选型决策。