集合与函数式编程

选型先问“数据之间是什么关系”，再问“怎么访问”，最后才落到具体实现类。流程相同而规则不同时，把变化的部分当参数传进去；集合处理到一定复杂度，再用 Stream 的生命周期组织起来。

一、先选接口

数组适合“数量固定、类型一致”的数据，但它有个硬限制：创建后长度不能变。要在中间插入元素，只能新建一个更长的数组、把后面的内容整体搬过去。删除同理。集合框架把这些搬运动作封装起来，并给不同语义准备了不同接口。

第一句问题就能分开一大半：允许重复且要按下标访问用 List；要求唯一用 Set；按键查值用 Map；按到达或优先级处理用 Queue。注意 Map 不继承 Collection，要观察其中的数据得用 keySet()、values()、entrySet()。

二、List 实现取舍

List 保证插入顺序，但不保证排序。[A, Z, A, B, F] 是有序的，[1, 2, 10] 才叫排序——两个概念别混。

ArrayList 底层是动态数组：按下标算地址就是 O(1)，末尾追加摊销 O(1)，中间插入删除要搬后面的元素所以是 O(n)。连续存储对 CPU 缓存友好，因此它是绝大多数业务里 List 的默认选择。

LinkedList 是双向链表，每个节点多存前后两个引用。它真正的优势是“已经定位到那个节点时改链接很快”，以及头尾操作为 O(1)；代价是按下标访问必须从头走（O(n)）、内存开销更大、缓存局部性更差。

ArrayList:  [0][1][2][3]     随机访问快，中间增删要搬移
LinkedList: 0 <- 1 <-> 2 <-> 3  已定位则增删快，定位本身很贵

提示：说“LinkedList 增删更快”是不准确的——如果每次都要先按下标找位置，它照样要遍历一遍。真正适合 LinkedList 的是频繁在头尾操作、或者用迭代器游走时插入删除的场景。

Vector 从 Java 1.0 就有，方法带 synchronized；ArrayList 不带。单线程优先 ArrayList。

命名本身能给出实现特征，记三条就够用：

三、Set 与 Map 的有序性

对字符列表 [A, Z, A, B, F] 去重：只要排序结果用 TreeSet，要首次出现顺序用 LinkedHashSet，两种都不要用 HashSet。

new TreeSet<>(chars);       // [A, B, F, Z]
new LinkedHashSet<>(chars); // [A, Z, B, F]

哈希表可以想成很多桶：hashCode() 大致决定去哪个桶，冲突时再用 equals() 区分。所以查找是“直接定位桶 + 少量比较”，平均 O(1)——注意是平均，分布很差或冲突严重时性能会降。

HashMap 可以有一个 null 键和 null 值；Hashtable 两者都不允许。这个差别在读配置文件、统计允许缺键的场景里经常被用到。

警告：TreeMap / TreeSet 的键必须能比较——实现 Comparable，或在构造时传 Comparator，否则运行时报 ClassCastException。另外 TreeSet 判“重复”依据的是比较结果而不是 equals：compareTo 返回 0 的两个对象会被当成同一个元素。

统计字符与单词出现次数是 HashMap 的典型用法。merge 把“取值、为空则初始化、加一”收成一次清晰的更新动作：

Map<Character, Integer> charCounts = new HashMap<>();
for (char ch : text.toCharArray()) {
    if (Character.isLetter(ch)) {
        charCounts.merge(Character.toLowerCase(ch), 1, Integer::sum);
    }
}

四、Queue 与优先级

普通 Queue 是先进先出：offer/add 入队，poll/remove 出队（空队列时前者返回 null、后者抛异常），peek 只看队头。ArrayDeque 还能在两端操作，是 Deque 的首选实现——它不允许放 null，因为 null 被内部用来表示“没有元素”。

PriorityQueue 虽然实现了 Queue，含义却是“优先级最高的先出队”：

var pq = new PriorityQueue<String>(Comparator.comparingInt(String::length));
pq.offer("apple"); pq.addAll(List.of("zebra", "monkey", "cat"));
pq.poll();  // apple（最短）

提示：只有队头保证是优先级最高的那个，遍历整个队列的顺序不是排序结果，不要拿它当有序数据用。

BlockingQueue 服务于生产者—消费者：队列空时消费者等待，队列满时生产者等待，还可以设超时。生产者—消费者、线程池任务交接都会用到它。

五、迭代、删除与快速失败

增强 for 在编译后大致变成迭代器：

for (String word : words) { }  // 相当于 words.iterator() 循环

问题出在边遍历边删。假设列表是 apple, bat, cat，增强 for 刚取出 bat，下标就前移了一位；此时删掉 bat，cat 向左补位，下一轮仍按旧下标前进，于是 cat 被跳过。

更严格的实现会记录结构性修改的次数，发现迭代器没有通过规定途径改动集合就抛 ConcurrentModificationException：

Iterator<String> it = words.iterator();
while (it.hasNext()) {
    String word = it.next();
    if (word.endsWith("at")) it.remove();   // 只能删最近一次 next() 返回的元素
}
words.removeIf(word -> word.endsWith("at")); // 等价的现代写法

这个异常和线程安全没有必然关系，同一线程在增强 for 里直接 remove 一样会触发。

并发场景下，“会不会抛”取决于集合的迭代器类型：

快速失败的作用是尽早暴露“遍历算法和修改方式互相破坏”，它不是并发控制机制。同样，不抛 CME 不等于业务操作原子：

if (!map.containsKey(key)) map.put(key, value);   // 非原子
Integer n = map.get(key);
map.put(key, n + 1);                              // 非原子

这两段要换成原子 API：

map.putIfAbsent(key, value);
map.merge(key, 1, Integer::sum);
map.compute(key, (k, old) -> old == null ? 1 : old + 1);

六、不可变集合与复制语义

确定不改就优先用工厂方法：List.of / Set.of / Map.of 及其 copyOf 版本返回拒绝 null 且不接受结构修改的集合；copyOf 的源集合和元素都不能为 null。

不可变通常只是“浅不可变”——集合本身不能改，里面的可变对象照样能改。

提示：把只读视图当快照是很常见的误用。视图会跟着原列表一起变，要隔离就必须复制。

七、排序：Comparable 与 Comparator

Comparable 表达“这个类型通常该怎么排”，属于类型自身；Comparator 表达“这次想怎么排”，属于调用场景。同一个学生类有时按学号、有时按姓名，用 Comparator 就不必改类。

static class Student implements Comparable<Student> {
    @Override public int compareTo(Student other) {
        return Integer.compare(this.id, other.id);
    }
}
Collections.sort(students);                                  // 按学号
students.sort(Comparator.comparing(Student::name));          // 按姓名
students.sort(Comparator.comparing(Student::id).reversed()); // 学号降序

排序结果不稳定多半是比较器自相矛盾：比较器必须满足传递性，混合多个字段时用 thenComparing 串起来，别手工拼 if 链。

警告：List.sort 和 Collections.sort 都直接改动原列表。要保留原顺序，用 stream().sorted() 生成新流。

八、有序导航

数据已排好序时，边界查询不用手写二分。TreeSet 实现 NavigableSet，TreeMap 实现 NavigableMap：

var numbers = new TreeSet<>(Set.of(12, 34, 54, 65));
numbers.floor(34);    // 34，不大于它的最大值
numbers.lower(34);    // 12，严格小于它的最大值
numbers.ceiling(34);  // 34，不小于它的最小值
numbers.higher(34);   // 54，严格大于它的最小值
numbers.subSet(20, 80); // [34, 54, 65]，左闭右开

TreeMap 提供同名的 floorKey / lowerKey / higherKey / ceilingKey，以及 firstEntry / lastEntry / subMap。

九、Lambda 与函数式接口

函数是一等公民，指的是它能像变量、参数、返回值那样被传来传去：

Predicate<Integer> isEven = n -> n % 2 == 0;
Predicate<Integer> alias   = isEven;    // 存进变量
Predicate<Integer> wrapped = () -> isEven; // 作为返回值

Java 没有独立的通用函数类型，于是用函数式接口充当函数的类型——恰好含一个抽象方法的接口。编译器在看到 Lambda 时，自动提供该抽象方法的实现。

Lambda 的骨架是 参数 -> 函数体，按参数数量变形：

() -> "hello"           // 无参
name -> name.length()   // 单参可省略括号
(a, b) -> a + b         // 多参必须加括号
x -> { return x * x; }  // 块体要显式 return

四大类别覆盖了绝大多数场景：

原始类型版本（IntPredicate、IntFunction、IntConsumer）能省掉装箱拆箱。

十、方法引用与捕获

函数体只调一个现成方法时可以用 :: 简写，四种形式：

Integer::compare       // 静态方法
System.out::println    // 已绑定对象的实例方法
String::length         // 未绑定接收者的实例方法，Stream 元素当接收者
ArrayList::new          // 构造器

Lambda 捕获的局部变量必须 final 或事实上不可再赋值：

String prefix = "Hi";
// prefix = "Hello";   // 放开这句，prefix 不再 effectively final，编译失败
Runnable task = () -> System.out.println(prefix + " Tom");

警告：语法简洁不保证线程安全。把可变集合共享给并发 Lambda 会产生竞态；在 Lambda 里做阻塞 I/O 还会拖累并行流。

十一、Stream 的生命周期

流分三段：数据源、中间操作、终端操作。中间操作返回新流并且惰性执行，终端操作才触发真正的计算。

List<Integer> squares = numbers.stream()
        .filter(n -> n % 2 == 0)   // 中间
        .map(n -> n * n)           // 中间
        .toList();                 // 终端

两条硬规则：没有终端操作，什么都不会执行；终端操作执行后流已消费，不能复用。

var pipeline = numbers.stream().map(n -> n * n); // 还没算
pipeline.forEach(System.out::println);
pipeline.forEach(System.out::println);  // IllegalStateException

数据源有很多种，范围方法的上界是排他的：

Arrays.stream(array);
Stream.of("A", "B");
Stream.builder();
IntStream.range(1, 11);          // 1..10，不含 11
IntStream.rangeClosed(1, 10);    // 1..10

归约结果可能不存在，max/min/findFirst 返回 Optional：

int biggestEven = numbers.stream()
        .filter(n -> n % 2 == 0)
        .max(Integer::compare)
        .orElse(0);

Optional 把“可能没有”写进 API 签名。几个方法的选择很关键：

Optional.ofNullable(findName())
        .map(String::toUpperCase)
        .ifPresent(System.out::println);

警告：不要无保护地 get()——空 Optional 会抛 NoSuchElementException；isPresent() 加 get() 两步也不理想，中间状态可能变化。

十二、同步集合与并发集合

Vector、Hashtable、Collections.synchronizedList 的思路是“同一时刻只允许一个线程进入”：简单正确，但一个线程在改 Map 的 A 键，其他线程只是读 B 键也得排队；同一个对象上的多个同步方法会互相阻塞。

并发集合把冲突范围缩小：

ConcurrentHashMap 内部对不同区域用不同的协调机制，线程操作一个键不必阻塞其他键。把它简化成“区域 A 用 A 的锁、区域 B 用 B 的锁”的模型就足够理解这个意思。

原子类和并发队列背后是 CAS（比较并交换）：

读取 expected
按旧值算出 newValue
比较内存当前值是否仍等于 expected
  相等 → 写入 newValue
  不等 → 别的线程改过了，重新读取重试

它不预先拿一把大锁，竞争时让线程自旋重试；竞争极其激烈时也会浪费 CPU。

CopyOnWriteArrayList 把代价放在写侧：读直接用当前数组不加读锁；写时复制一个新数组、填好内容、再切换引用。

var occurrences = new ConcurrentHashMap<Character, LongAdder>();
occurrences.computeIfAbsent(ch, k -> new LongAdder()).increment();

适合一万次读、十几次写；写频繁时每次都复制整个数组，优势会完全反转。

提示：线程安全集合只保证单个方法安全，不会把“查库 + 写库 + 改 Map”这样的多步流程自动变成原子的。

十三、高级 Collectors 与归约

单条流水线之外，分组与合并是 Collectors 的主战场：

Map<String, List<Course>> byCategory =
        courses.stream().collect(Collectors.groupingBy(Course::category));

Map<String, Long> countByCategory =          // 分组后计数
        courses.stream().collect(Collectors.groupingBy(Course::category, Collectors.counting()));

Map<Boolean, List<Course>> passFail =        // 按真假二分
        courses.stream().collect(Collectors.partitioningBy(c -> c.rating() >= 90));

Map<String, Integer> totalByCategory =       // 键重复必须给合并函数
        courses.stream().collect(Collectors.toMap(
                Course::category, Course::rating, Integer::sum));

四条容易踩的细节：

• groupingBy 默认返回 HashMap，不保证顺序；要按首次出现顺序输出就传 LinkedHashMap::new 作为 mapFactory。
• toMap 不给第三个参数时遇到重复键会抛异常。字符统计正需要合并函数。
• partitioningBy 总是给出 true/false 两个分组，空组也会存在。
• Collectors.toList() 不承诺具体类型与可修改性；要明确要 ArrayList 就用 Collectors.toCollection(ArrayList::new)。

十四、命令式还是 Stream

两者没有高下，选看任务的形状：

提示：不要为了显得高级，把一个五行能读完的循环拆成十个 Stream 操作。流水线的收益来自“多步变形”，只有一个动作时它只是噪音。

十五、排序去重与并行边界

distinct 去重、sorted 排序，都是中间操作可以继续串联。Stream.toList() 返回不可修改列表，尝试 add 会抛 UnsupportedOperationException；Collectors.toList() 则不提供这类保证。

并行流只在数据量与计算量都够大时才划算。任务会被拆分到公共 ForkJoinPool 再合并，拆分与合并本身有成本，小数据量或简单加法反而更慢。并行归约函数必须满足结合律，且不能修改共享外部状态——浮点求和顺序变化会带来舍入差异。

LongStream.rangeClosed(1, 1_000_000).parallel().map(n -> n * n).sum();

警告：并行 forEach 不保证元素顺序，需要顺序时用 forEachOrdered；共享计数要用 LongAdder、原子类或并发容器，forEach(list::add) 这类副作用写法在并行流里会直接出错。性能判断以 JMH 为准，不靠“加了 parallel 感觉更快”。

十六、易错点总表

集合四句话：接口定取数方式、实现定顺序代价、比较器定排序规则、导航定边界查询。函数式再补一句：规则不同就把规则当参数传，变形多了就串成流水线。字符串、时间、精确数值这些基础数据在集合之外另有一套 API。