本节目标：能按「是否允许重复、是否关心顺序、是否按 key 查找」选择 List、Set、Map，能说清
equals/hashCode对集合行为的影响，并把内存仓储从ArrayList换成Map。
适用版本：JDK 25 LTS（Temurin 25.0.5）；集合框架的接口与行为在 JDK 21 上一致。
三条查询暴露的问题
第 8 章的 InMemoryLibraryRepository 用两个 ArrayList 存书和借阅。它有三条典型查询：
findByIsbn(isbn)：按 ISBN 找一本书。现在要遍历整个列表，数据越多越慢。save(book)：ISBN 已存在就替换。现在也要遍历列表，先找到位置再set。findByAuthor(author)：按作者找书。default 方法同样遍历整个列表。
三条查询都在做同一件事：按某个键找东西。 列表擅长「按位置访问」和「保持插入顺序」，不擅长「按业务键查找」。要解决这个问题，得先分清 List、Set、Map 三种容器各自承诺了什么。
List、Set、Map 的契约
三种接口的差异可以用三个问题概括：
| 接口 | 允许重复 | 顺序 | 主要用途 |
|---|---|---|---|
List | 允许 | 有索引，按插入位置 | 有序序列、按位置访问 |
Set | 不允许 | 取决于实现 | 去重、成员判断 |
Map | key 不允许重复 | 取决于实现 | 按 key 查找 value |
用 library 的数据试一遍：
Book threeBody = new Book("9787536692930", "三体", "刘慈欣", 2008);
Book threeBodyReprint = new Book("9787536692930", "三体（重印）", "刘慈欣", 2008);
List<Book> shelf = new ArrayList<>();
shelf.add(threeBody);
shelf.add(threeBodyReprint);
System.out.println("List size = " + shelf.size());
Set<String> isbns = new HashSet<>();
isbns.add(threeBody.isbn());
isbns.add(threeBodyReprint.isbn());
System.out.println("Set size = " + isbns.size());
Map<String, Book> byIsbn = new HashMap<>();
byIsbn.put(threeBody.isbn(), threeBody);
byIsbn.put(threeBodyReprint.isbn(), threeBodyReprint);
System.out.println("Map size = " + byIsbn.size());
System.out.println("Map value = " + byIsbn.get("9787536692930").title());
本机 JDK 25 输出：
List size = 2
Set size = 1
Map size = 1
Map value = 三体（重印）
三行结果对应三条契约：
List允许两个 ISBN 相同的Book，因为它们不是同一个对象，列表也不做去重。Set<String>用String.equals判断重复，两个相同的 ISBN 只保留一个。Map的 key 重复时，后放入的 value 覆盖前一个，所以Map value是「三体（重印）」。
这里的 Map 行为很容易被忽略：put 不报错，也不保留两个值，而是静默覆盖。如果「同一 ISBN 不允许重复添加」是业务规则，必须在 LibraryService.addBook 里先 findByIsbn 检查，不能指望 Map 帮你拦住。
实现类怎么选
接口只定义契约，具体行为由实现类决定：
| 接口 | 常用实现 | 顺序 | 查找 | 适用场景 |
|---|---|---|---|---|
List | ArrayList | 插入顺序 | 按索引 O(1) | 大多数有序集合 |
List | LinkedList | 插入顺序 | 按索引 O(n) | 频繁在两端增删（多数场景用 ArrayDeque） |
Set | HashSet | 不保证 | 平均 O(1) | 去重、成员判断 |
Set | LinkedHashSet | 插入顺序 | 平均 O(1) | 去重且要稳定输出 |
Set | TreeSet | 排序顺序 | O(log n) | 需要有序遍历 |
Map | HashMap | 不保证 | 平均 O(1) | 大多数 key-value 查找 |
Map | LinkedHashMap | 插入顺序 | 平均 O(1) | 查找且要稳定遍历 |
Map | TreeMap | key 排序 | O(log n) | 需要按 key 范围查询 |
几条实践建议：
- 默认用
ArrayList。 它的随机访问快、内存连续、遍历友好；LinkedList只有在确实频繁在中间增删时才有优势，而那种场景往往可以用ArrayDeque或重建列表代替。 - 需要去重又需要稳定输出时用
LinkedHashSet。HashSet的遍历顺序不保证，测试里断言顺序会随机失败。 - 需要按 key 排序时用
TreeMap。 它的 key 必须可比较，或者构造时传入Comparator；第 10.3 节会讲比较器。 - 不要用
Hashtable、Vector这些遗留类。 它们是早期同步实现，性能和 API 都不如新集合；需要线程安全时用ConcurrentHashMap，卷三再讲并发。
LinkedHashSet 和 TreeSet 的差异可以直接看到：
Set<String> insertionOrder = new LinkedHashSet<>();
insertionOrder.add("三体");
insertionOrder.add("红楼梦");
insertionOrder.add("三体");
System.out.println("LinkedHashSet = " + insertionOrder);
Set<String> sorted = new TreeSet<>();
sorted.add("三体");
sorted.add("红楼梦");
sorted.add("Java 编程思想");
System.out.println("TreeSet = " + sorted);
本机 JDK 25 输出：
LinkedHashSet = [三体, 红楼梦]
TreeSet = [Java 编程思想, 三体, 红楼梦]
LinkedHashSet 保留第一次插入的顺序，重复的「三体」被忽略；TreeSet 按字符串的自然顺序（UTF-16 码元）排序，所以 Java 排在中文前面。注意这不是拼音顺序，中文排序要用 Collator，10.3 会讲。
equals 与 hashCode 是门票
HashSet 和 HashMap 能快速判断「这个元素在不在」，靠的是 hashCode() 定位桶、equals() 确认相等。两个方法必须一起正确实现：
- 两个对象
equals为true，hashCode必须相等。 hashCode相等的对象，equals不一定为true（哈希碰撞）。- 对象放进
HashSet/HashMap后，如果参与hashCode的字段变了，就再也找不回来。
9.1 的 record 自动生成基于全部组件的 equals/hashCode，所以 Book 放进 Set 能正确去重。如果手写普通类，漏掉一个字段就会出问题：两个 ISBN 相同的 Book 可能被当成不同对象，或者 hashCode 不一致导致 get 返回 null。
反例用可变对象当 key：
Map<StringBuilder, Integer> badKeys = new HashMap<>();
StringBuilder key = new StringBuilder("a");
badKeys.put(key, 1);
System.out.println("get(new StringBuilder(\"a\")) = " + badKeys.get(new StringBuilder("a")));
System.out.println("get(same instance) = " + badKeys.get(key));
本机 JDK 25 输出：
get(new StringBuilder("a")) = null
get(same instance) = 1
StringBuilder 没有覆写 equals/hashCode，两个内容相同的实例并不相等。HashMap 用新的 StringBuilder 去查，哈希不同、equals 也不成立，所以返回 null。
这条规则对 library 的直接含义是：key 用不可变类型。 ISBN 用 String，会员 ID 用 String，枚举用枚举常量；不要把 Book 的可变字段、List、数组当 key。如果非要用对象做 key，用 record 或确保它不可变且 equals/hashCode 正确。
在 library 里落地：Map 版仓储
把两个 ArrayList 换成三个 Map：
booksByIsbn：ISBN ->Book，负责按 ISBN 查找和去重。activeLoansByIsbn：ISBN -> 当前未结束的Loan，负责「一本书同时只能借给一个人」。loansByMember：会员 ID -> 该会员的借阅列表，负责按会员查询。
package com.plume.library.repository;
import com.plume.library.domain.Book;
import com.plume.library.domain.Loan;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
public final class InMemoryLibraryRepository implements LibraryRepository {
private final Map<String, Book> booksByIsbn = new LinkedHashMap<>();
private final Map<String, Loan> activeLoansByIsbn = new HashMap<>();
private final Map<String, List<Loan>> loansByMember = new HashMap<>();
@Override
public void save(Book book) {
booksByIsbn.put(book.isbn(), book);
}
@Override
public Optional<Book> findByIsbn(String isbn) {
return Optional.ofNullable(booksByIsbn.get(isbn));
}
@Override
public List<Book> findAll() {
return List.copyOf(booksByIsbn.values());
}
@Override
public boolean deleteByIsbn(String isbn) {
return booksByIsbn.remove(isbn) != null;
}
@Override
public void saveLoan(Loan loan) {
if (loan.status().isOpen()) {
activeLoansByIsbn.put(loan.isbn(), loan);
} else {
activeLoansByIsbn.remove(loan.isbn());
}
List<Loan> memberLoans = loansByMember.computeIfAbsent(
loan.memberId(), key -> new ArrayList<>());
for (int i = 0; i < memberLoans.size(); i++) {
Loan existing = memberLoans.get(i);
if (existing.isbn().equals(loan.isbn())
&& existing.borrowedOn().equals(loan.borrowedOn())) {
memberLoans.set(i, loan);
return;
}
}
memberLoans.add(loan);
}
@Override
public Optional<Loan> findActiveLoanByIsbn(String isbn) {
return Optional.ofNullable(activeLoansByIsbn.get(isbn));
}
@Override
public List<Loan> findLoansByMember(String memberId) {
return List.copyOf(loansByMember.getOrDefault(memberId, List.of()));
}
}
几个设计点：
booksByIsbn用LinkedHashMap，findAll()的输出顺序稳定，CLI 的list命令不会每次换顺序；按 key 查找仍是平均 O(1)。activeLoansByIsbn用HashMap，key 是 ISBN，value 是当前借阅；归还时remove，续借时put覆盖。loansByMember的 value 是List<Loan>，因为一个会员可以有多条借阅；computeIfAbsent在 key 不存在时创建列表。saveLoan做 upsert：同一 ISBN + 借出日期视为同一条借阅，续借和归还时替换，不重复添加。findByAuthor没有出现在实现类里，接口的 default 方法仍然遍历findAll()。10.2 会加作者索引，把它从 O(n) 降到平均 O(1)。
LibraryService 一行都不用改。它只依赖 LibraryRepository 接口，findByIsbn、findActiveLoanByIsbn、findLoansByMember 的签名不变，换实现不影响业务。
搜索没有单独的数据结构，仍然是遍历 findAll() 做子串匹配：
public List<Book> search(String keyword) {
String needle = keyword.strip().toLowerCase(Locale.ROOT);
List<Book> matched = new ArrayList<>();
for (Book book : repository.findAll()) {
if (book.title().toLowerCase(Locale.ROOT).contains(needle)
|| book.author().toLowerCase(Locale.ROOT).contains(needle)) {
matched.add(book);
}
}
return List.copyOf(matched);
}
这是 O(n) 的线性搜索，因为「标题包含某个词」不是 Map 的 key 查找能直接表达的。10.2 会给作者精确查询加索引，但子串搜索仍然要扫描；要让它变快，得引入分词或 n-gram 索引，那是另一个量级的复杂度。
本机跑一遍：
total = 6
byIsbn = 9787536692930
byAuthor(刘慈欣) = 1
borrow due = 2026-10-26
return fine = 300
这里 findByAuthor 仍走 default 的线性扫描，所以结果正确；数据量上来后，它的成本会在 10.2 被单独拎出来处理。
常见错误与边界
把 Map.get 返回 null 当成「key 不存在」。 如果 value 本身允许 null，两者无法区分。仓储里 value 不允许 null，所以 get != null 可以用；更稳妥的写法是 containsKey 或 Optional.ofNullable。Map.copyOf 和 List.copyOf 都不接受 null 元素，这条约束要提前定好。
用 Map 去重却忘了 key 的选择。 Map<String, Book> 按 ISBN 去重；如果 key 用 Book 对象，两个 ISBN 相同但标题不同的 Book 会被当成不同 key，去重失效。
在遍历 Map 时修改它。 for (var entry : map.entrySet()) { map.remove(...); } 会抛 ConcurrentModificationException；用 Iterator.remove、removeIf 或先收集 key 再删。10.3 会讲遍历的细节。
把 List.of 当成可变列表。 List.of(...)、Set.of(...)、Map.of(...) 返回不可变集合，add、put、remove 会抛 UnsupportedOperationException。需要修改时用 new ArrayList<>(List.of(...))。
小结
List允许重复、按位置访问；Set去重；Map按 key 查找，key 重复会覆盖。- 默认用
ArrayList和HashMap；需要稳定顺序用LinkedHashSet/LinkedHashMap，需要排序用TreeSet/TreeMap。 equals/hashCode是HashSet、HashMap的门票；record 自动生成，手写类必须写对。- key 用不可变类型；可变对象做 key，修改后就再也查不到。
library用三个Map分别承担 ISBN 查找、当前借阅、会员借阅列表，接口不变，业务代码不变。findByAuthor的 default 实现仍是 O(n)，作者索引和容量规划留到 10.2。
容器选对了，性能问题才刚开始。10.2 会用真实查询对比线性扫描和哈希查找，讲清扩容、负载因子、索引和内存开销，回答「为什么 map 快了三个数量级，以及它贵在哪」。
阅读导航：上一节：9.3 sealed 与模式匹配 · 下一节：10.2 复杂度与内存 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。