Java 集合框架笔记（基于 Java 8）

一、集合框架概述

集合框架是一个统一的架构，用于存储和操作一组对象。根接口是 Iterable，核心接口包括 Collection（单列集合）和 Map（双列集合）。

1.1 接口继承关系图

Iterable<E>
    ↓
Collection<E>
    ├── List<E>
    │   ├── ArrayList<E>
    │   ├── LinkedList<E>
    │   ├── Vector<E>
    │   └── Stack<E>
    ├── Set<E>
    │   ├── HashSet<E>
    │   ├── LinkedHashSet<E>
    │   └── SortedSet<E> (接口)
    │       └── TreeSet<E>
    └── Queue<E>
        ├── PriorityQueue<E>
        └── Deque<E>
            └── ArrayDeque<E>

Map<K,V> (独立体系)
    ├── HashMap<K,V>
    ├── LinkedHashMap<K,V>
    ├── Hashtable<K,V>
    └── SortedMap<K,V> (接口)
        └── TreeMap<K,V>

1.2 核心接口简介

二、Collection 接口

所有集合类的根接口，定义了集合的基本操作。

2.1 基本方法

三、List 接口

有序集合，允许重复元素，支持通过索引操作。

3.1 List 特有方法

3.2 ArrayList

数据结构：动态数组
初始容量：10（默认构造函数）
扩容机制：新容量 = 旧容量 + 旧容量 >> 1（即 1.5 倍）
时间复杂度：

• get(index) / set(index, element)：O(1)
• add(E e) 平均 O(1)，最坏 O(n)（扩容）
• add(index, E e) / remove(index)：O(n)
  线程安全：否

创建方式

// 默认初始容量10
ArrayList<String> list1 = new ArrayList<>();

// 指定初始容量
ArrayList<String> list2 = new ArrayList<>(20);

// 从其他集合创建（Java 9+ List.of 返回不可变List）
List<String> source = List.of("Java", "Python", "C++");
ArrayList<String> list3 = new ArrayList<>(source);

// 使用接口引用（推荐）
List<String> list4 = new ArrayList<>();

常用操作

// 添加
list.add("Java");               // 末尾添加
list.add(1, "C++");             // 指定位置插入
list.addAll(List.of("Go", "Rust")); // 添加多个

// 访问与修改
String first = list.get(0);
String last = list.get(list.size() - 1);
list.set(1, "Python");

// 查找
int idx = list.indexOf("Java");
boolean has = list.contains("C++");

// 删除
list.remove(0);                 // 按索引
list.remove("Java");            // 按对象（删除第一个匹配）
list.removeAll(List.of("Go", "Rust"));
list.removeIf(s -> s.length() > 4); // Java 8+
list.clear();

// 缩容释放内存
list.trimToSize();

线程安全解决方案

• Collections.synchronizedList(new ArrayList<>())
• CopyOnWriteArrayList（读多写少场景）
• 手动 synchronized 同步

注意事项

• 遍历时（增强 for 或迭代器）不能直接调用 list.remove() 或 list.add()，应使用迭代器的 remove() 或 removeIf()。
• List.of() 返回的集合不可修改。

3.3 LinkedList

数据结构：双向链表
时间复杂度：

• get(index) / set(index, element)：O(n)
• addFirst / addLast / removeFirst / removeLast：O(1)
• 中间插入/删除：O(n)（需先定位）

特点：实现 List 和 Deque 接口，可作列表、队列、双端队列、栈。

创建与添加

LinkedList<String> list = new LinkedList<>();
List<String> list2 = new LinkedList<>(); // 接口引用

list.add("Apple");          // 末尾
list.addFirst("Grape");     // 头部
list.addLast("Banana");     // 尾部
list.add(1, "Orange");      // 指定位置
list.offer("Cherry");       // 队列入队（末尾）

访问操作

String first = list.getFirst();
String last = list.getLast();
String element = list.get(2);   // O(n)

// 队列/双端队列查看
String head = list.peek();
String headFirst = list.peekFirst();
String headLast = list.peekLast();

int index = list.indexOf("Apple");

删除操作

list.removeFirst();
list.removeLast();
list.remove(1);
list.remove("Apple");

// 队列出队
String polled = list.poll();
list.pollFirst();
list.pollLast();

作为队列（FIFO）

Queue<String> queue = new LinkedList<>();
queue.offer("客户1");
queue.offer("客户2");
String head = queue.peek();      // 查看队首
String customer = queue.poll();  // 出队

作为栈（LIFO）

Deque<String> stack = new LinkedList<>();
stack.push("方法A");
stack.push("方法B");
String top = stack.peek();   // 查看栈顶
String method = stack.pop(); // 出栈

作为双端队列

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(2);
deque.addLast(3);
deque.addFirst(1);
deque.addLast(4);          // 结果 [1,2,3,4]
deque.peekFirst();
deque.peekLast();
deque.removeFirst();
deque.removeLast();

注意事项

• get(index) 在大列表上频繁使用会导致性能问题（O(n)）。
• 没有 trimToSize 方法（链表动态分配）。

3.4 Vector 和 Stack

• Vector：早期动态数组，方法使用 synchronized 实现线程安全，性能较差，现已不推荐使用。
• Stack：继承 Vector，提供栈操作 push、pop、peek。同样不推荐，建议使用 Deque 实现（如 ArrayDeque）。

四、Set 接口

不允许重复元素（最多一个 null），无索引。底层依赖 equals() 和 hashCode() 判断重复。

4.1 实现类对比

4.2 使用示例

Set<String> fruits = new HashSet<>();
fruits.add("苹果");
fruits.add("香蕉");
fruits.add("苹果"); // 重复，不会添加
System.out.println(fruits.size()); // 2

4.3 最佳实践

• 默认使用 HashSet，需要有序用 LinkedHashSet，需要排序用 TreeSet。
• 线程安全包装：Collections.synchronizedSet(new HashSet<>()) 或 ConcurrentHashMap.newKeySet()。
• 自定义对象存入 Set 时必须重写 equals() 和 hashCode()；存入 TreeSet 还需实现 Comparable 或提供 Comparator。
• 合理设置 HashSet 初始容量（避免频繁扩容），负载因子默认 0.75。

4.4 注意事项

• HashSet 迭代顺序不确定，不要依赖。
• TreeSet 不允许 null，会抛出 NullPointerException。
• 修改已添加到 Set 中的对象可能导致数据丢失或重复。

五、Queue 接口

FIFO 队列，提供队首队尾操作。Deque 子接口支持双端操作。

5.1 主要方法

推荐使用：offer、poll、peek（避免异常）。

5.2 实现类对比

5.3 使用示例

Queue<String> queue = new ArrayDeque<>();
queue.offer("A");
queue.offer("B");
String head = queue.peek();  // A
String out = queue.poll();   // A

// 优先级队列
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll()); // 1

5.4 线程安全队列

• ArrayBlockingQueue（有界阻塞队列）
• LinkedBlockingQueue（可选有界）
• PriorityBlockingQueue（无界优先级队列）

六、Map 接口

键值对映射，键唯一，值可重复。不继承 Collection。

6.1 常用方法

6.2 实现类对比

6.3 使用示例

Map<String, Integer> map = new HashMap<>();
map.put("apple", 10);
map.put("banana", 20);
int value = map.get("apple"); // 10
map.remove("banana");

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

6.4 最佳实践

• 声明时使用接口类型：Map<K,V> map = new HashMap<>()。
• 作为键的类必须重写 equals() 和 hashCode()，最好使用不可变对象。
• 合理设置 HashMap 初始容量，避免频繁 rehash。
• 多线程环境使用 ConcurrentHashMap（不要使用 Hashtable）。

七、迭代器（Iterator）

7.1 Iterator 接口

统一遍历集合的方式，支持安全删除。

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (condition) it.remove(); // 安全删除
}

方法：

• boolean hasNext()
• E next()
• void remove()（可选）

7.2 ListIterator 接口

Iterator 的子接口，专门用于 List，支持双向遍历和修改。

额外方法：

• boolean hasPrevious()
• E previous()
• int nextIndex() / int previousIndex()
• void set(E e) 修改当前元素
• void add(E e) 在当前位置插入

7.3 增强 for 循环（for-each）

语法糖，编译器自动转换为 Iterator 遍历。

int[] numbers = {1,2,3,4,5};
for (int num : numbers) {
    System.out.println(num);
}

List<String> list = ...;
for (String s : list) {
    // 不能修改 list 结构（添加/删除）
}

限制：

• 无法获取当前索引
• 遍历时不能修改集合结构（否则抛出 ConcurrentModificationException）
• 不能修改基本类型数组的元素值（但可以修改引用类型对象的属性）

八、并发集合（java.util.concurrent）

8.1 ConcurrentHashMap

• Java 7 及之前：分段锁（Segment），默认 16 个段。
• Java 8+：Node 数组 + CAS + synchronized 对链表/红黑树头节点加锁，锁粒度更细。
• 支持并发读（无锁）和并发写（部分加锁）。
• 不允许 null 键/值。

8.2 CopyOnWriteArrayList

• 写时复制策略：修改时复制整个数组，修改后替换原数组。
• 读操作无锁，性能极高。
• 适用于读多写极少的场景（如配置列表、监听器列表）。
• 缺点：写操作内存开销大，数据一致性弱（可能读到旧数据）。

8.3 BlockingQueue 阻塞队列

核心阻塞方法：

• put(E e)：队列满时阻塞
• take()：队列空时阻塞

典型应用：生产者-消费者模式。

九、选择指南

9.1 根据数据结构选择

9.2 时间复杂度速查

• 扩容时 O(n)
  ** 假设哈希函数良好

十、常见问题与注意事项

1. ConcurrentModificationException：在遍历集合时直接修改结构（增删），应使用迭代器的 remove() 或 removeIf()。
2. HashSet / HashMap 中自定义对象：必须正确重写 equals() 和 hashCode()，否则无法去重或查找。
3. TreeSet / TreeMap 中元素：必须实现 Comparable 或传入 Comparator，否则抛出 ClassCastException。
4. ArrayList 删除元素后不会自动缩容：可调用 trimToSize() 释放多余内存。
5. LinkedList 的 get(index)：效率低（O(n)），避免在循环中频繁调用。
6. Arrays.asList() 返回的 List：是固定大小的视图，不支持 add / remove，会抛出 UnsupportedOperationException。
7. 优先使用接口类型声明：List<String> list = new ArrayList<>();，便于更换实现。