集合与 SequencedCollection

选型：先确定访问模式01

集合选型只需要回答四个问题：是否需要顺序、是否允许重复、是否需要按键查找、是否需要并发。大部分性能问题不是集合选错，而是用错访问模式（例如在 ArrayList 头部频繁插入）。

工厂方法与不可变集合02

JDK 9 引入 List.of / Set.of / Map.of，一行创建不可变集合。它们拒绝 null、拒绝重复 key，并在创建时拷贝元素（不是视图）。

List<String> list = List.of("a", "b", "c");
Set<Integer> set = Set.of(1, 2, 3);
Map<String, Integer> map = Map.of("a", 1, "b", 2);
Map<String, Integer> big = Map.ofEntries(
    Map.entry("a", 1),
    Map.entry("b", 2),
    Map.entry("c", 3)
);

list.add("d");            // UnsupportedOperationException
List.of("a", null);       // NullPointerException
Set.of(1, 1);             // IllegalArgumentException: duplicate element
Map.of("a", 1, "a", 2);   // IllegalArgumentException: duplicate key

• List.of 保留参数顺序；Set.of 的迭代顺序不保证，不要依赖。
• 不可变的是结构：元素对象本身仍可能可变。需要深不可变时自行拷贝。
• List.copyOf(collection) 在入参已经是不可变 List 时可能直接返回同一个实例；不要依赖这一点。
• Arrays.asList 是固定长度视图，支持 set 但不支持增删，且会写回原数组；List.of 才是真正不可变。

String[] arr = {"a", "b"};
List<String> fixed = Arrays.asList(arr);
fixed.set(0, "z");
System.out.println(Arrays.toString(arr)); // [z, b] —— 会写回原数组

List<String> immutable = List.of(arr);
// immutable.set(0, "x"); // UnsupportedOperationException

SequencedCollection：统一首尾操作03

在 JDK 21 之前，首尾操作分散在 List（get(0)、get(size-1)）、Deque（getFirst、addLast）和 SortedSet（first、last）里。SequencedCollection 把这些能力抽象成统一接口。

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
System.out.println(list.getFirst()); // a
System.out.println(list.getLast());  // c

SequencedCollection<String> rev = list.reversed();
System.out.println(rev);             // [c, b, a]

rev.addFirst("z");                   // 等价于原 list.addLast("z")
System.out.println(list);            // [a, b, c, z]
System.out.println(rev);             // [z, c, b, a]

LinkedHashSet 的 addFirst 对已存在元素是移动而不是重复插入；List 的 addFirst 则允许重复，直接插入。这是 Set 与 List 的语义差异，不是 API 差异。

LinkedHashSet<String> set = new LinkedHashSet<>(List.of("a", "b", "c"));
set.addFirst("c");
System.out.println(set); // [c, a, b] —— 已存在元素被移到最前

SequencedMap：有序映射的统一入口04

SequencedMap 为有序 Map 提供首尾条目、首尾插入与反转视图。LinkedHashMap、TreeMap、SortedMap 都实现了它。

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);

System.out.println(map.firstEntry()); // a=1
System.out.println(map.lastEntry());  // c=3

map.putFirst("c", 30);                // 已存在的 key 移到最前，返回旧值 3
System.out.println(map);              // {c=30, a=1, b=2}

System.out.println(map.sequencedKeySet());   // [c, a, b]
System.out.println(map.sequencedValues());   // [30, 1, 2]
System.out.println(map.reversed());          // {b=2, a=1, c=30}

Map.Entry<String, Integer> first = map.pollFirstEntry(); // 取出并删除 c=30
System.out.println(first + " → " + map);     // c=30 → {a=1, b=2}

TreeMap 的第一/最后由排序决定，不是插入顺序。它支持 firstEntry / lastEntry / reversed，但 putFirst / putLast 会抛 UnsupportedOperationException——因为位置由比较器决定，不能随意插入。

TreeMap<String, Integer> tm = new TreeMap<>();
tm.put("b", 2);
tm.put("a", 1);
System.out.println(tm.firstEntry()); // a=1
System.out.println(tm.reversed());   // {b=2, a=1}
tm.putFirst("c", 3);                 // UnsupportedOperationException

• 只读包装：Collections.unmodifiableSequencedCollection / unmodifiableSequencedSet / unmodifiableSequencedMap。
• 从 Map 造 Set：Collections.newSequencedSetFromMap(map)，适合需要「有序 Set 视图」的底层实现。
• SequencedMap.reversed() 同样是视图，写入会反映到原 Map。

常见坑与真实行为05

1. subList 是视图

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
List<Integer> sub = list.subList(1, 4); // [2, 3, 4]
sub.set(0, 20);
System.out.println(list); // [1, 20, 3, 4, 5] —— 原列表被修改

list.add(6);              // 结构修改后，sub 再访问会抛 ConcurrentModificationException

2. 遍历时删除

// 错误：ConcurrentModificationException
for (String s : list) {
    if (s.isBlank()) list.remove(s);
}

// 正确：Iterator.remove
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().isBlank()) it.remove();
}

// 或 removeIf
list.removeIf(String::isBlank);

3. computeIfAbsent 的返回值

Map<String, List<String>> index = new HashMap<>();
index.computeIfAbsent("a", k -> new ArrayList<>()).add("x");
System.out.println(index); // {a=[x]}

// 注意：mapping function 返回 null 时不会插入，也不会抛异常
index.computeIfAbsent("b", k -> null);
System.out.println(index.containsKey("b")); // false

4. equals / hashCode 可变 key

把可变对象放进 HashSet 或作为 HashMap 的 key，修改字段后哈希值变化，会导致再也找不到该元素。key 应该是不可变对象——record 是很好的选择。

5. 并发集合不是万能

ConcurrentHashMap 只保证单个操作的原子性。if (!map.containsKey(k)) map.put(k, v) 这种复合操作仍要使用 putIfAbsent / computeIfAbsent。

常用配方06

词频统计

Map<String, Long> freq = words.stream()
    .collect(Collectors.groupingBy(w -> w, Collectors.counting()));

Map<String, Integer> freq2 = new HashMap<>();
for (String w : words) {
    freq2.merge(w, 1, Integer::sum);
}

按 key 分组

Map<String, List<Order>> byUser = orders.stream()
    .collect(Collectors.groupingBy(Order::userId));

// 保留插入顺序
Map<String, List<Order>> ordered = orders.stream()
    .collect(Collectors.groupingBy(
        Order::userId, LinkedHashMap::new, Collectors.toList()));

LRU 缓存（LinkedHashMap）

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LruCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

var cache = new LruCache<String, Integer>(3);
cache.put("a", 1); cache.put("b", 2); cache.put("c", 3);
cache.get("a");          // 访问 a，a 变成最近使用
cache.put("d", 4);       // 淘汰 b
System.out.println(cache.keySet()); // [c, a, d]

版本边界BOUNDARY

这张表比 API 本身更值得记。写代码时先确认你的运行时版本。

费曼自检SELF CHECK

先合上页面，用自己的话回答，再展开对照。能讲出因果和反例，才算真正掌握。