第 10 章 · 集合类

10.1 集合概述

集合用于存储一组对象，比数组更灵活（动态扩容、丰富算法）。Java 集合框架（Collection Framework）主要分两大接口：Collection（单列）和 Map（键值对）。

Collection
├── List（有序、可重复）：ArrayList / LinkedList
└── Set（无序、不可重复）：HashSet / TreeSet

Map（键唯一）：HashMap / TreeMap / Properties

10.2 Collection 接口

通用方法：add、remove、contains、size、isEmpty、clear、iterator。

10.3 List 接口

ArrayList：底层动态数组，随机访问 O(1)，增删中间元素 O(n)，适合读多写少。

LinkedList：底层双向链表，增删首尾 O(1)，随机访问 O(n)，适合频繁插入删除。

List<String> list = new ArrayList<>();
list.add("a");
list.get(0);          // 按下标访问

遍历：

for (String s : list) { }                     // 增强 for
Iterator<String> it = list.iterator();        // 迭代器
while (it.hasNext()) { String s = it.next(); }
list.forEach(s -> System.out.println(s));     // Lambda

对比：ArrayList ≈ C++ std::vector ≈ Python list；LinkedList ≈ C++ std::list。Python 的 list 是最常用的动态数组，但 Java 需要显式选择实现类。

10.4 Set 接口

HashSet：基于哈希表，无序、O(1) 增删查，元素不可重复（靠 hashCode + equals）。

TreeSet：基于红黑树，有序（自然序或比较器）、O(log n)。

Set<String> set = new HashSet<>();
set.add("a"); set.add("b"); set.add("a");  // 重复的 a 不加入

10.5 Map 接口

HashMap：键值对，基于哈希表，键不可重复，O(1) 查找；TreeMap：按键排序。

Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.get("apple");                 // 3
for (Map.Entry<String, Integer> e : map.entrySet()) { }

对比：HashMap ≈ Python dict ≈ C++ unordered_map；TreeMap ≈ C++ std::map（红黑树）。

10.6 泛型（JDK 5）

泛型让集合在编译期检查类型，避免运行期 ClassCastException：

List<String> list = new ArrayList<>();   // 只能存 String
list.add(1);                             // 编译错误

• 自定义泛型：class Box<T> { T value; }。
• 泛型靠类型擦除实现，运行期无泛型信息。

对比：C++ 模板是编译期代码生成（每个类型生成一份），Java 泛型是类型擦除（运行期统一）；Python 无静态泛型，靠类型注解（typing）辅助、不强制。

10.7 Collections 与 Arrays 工具类

• Collections.sort(list)、Collections.reverse、Collections.shuffle、Collections.max/min。
• Arrays.sort(a)、Arrays.binarySearch、Arrays.asList、Arrays.copyOf。

10.8 与其他语言对比

需求	Java	C++	Python
动态数组	ArrayList	vector	list
哈希表	HashMap	unordered_map	dict
有序集合	TreeSet/TreeMap	set/map	需 sortedcontainers
类型安全	泛型（擦除）	模板	动态

核心差异：Java 集合框架统一、类型安全；Python 靠内置 dict/list 语法糖极简；C++ STL 性能极致但接口相对晦涩。