《Java 编程入门》10.2 复杂度与内存

本节目标：能估算常见集合操作的时间复杂度，能解释哈希查找为什么平均 O(1)、最坏 O(n)，能给仓储做容量规划，并知道集合在内存上多花了什么。
适用版本：JDK 25 LTS（Temurin 25.0.5）；文中数字来自本机单次运行，只用于展示数量级。

快了多少，为什么快

10.1 把 findByIsbn 从 ArrayList 的线性扫描换成了 HashMap 的 key 查找。接口没变，调用方式没变，但数据量上来后差距会非常明显。

先给一个可复现的对比：2 万本书，5 千次随机 ISBN 查询，分别用 ArrayList 线性扫描和 HashMap.get。下面是核心循环：

private static int linearScan(List<Book> books, String[] queries) {
    int hits = 0;
    for (String query : queries) {
        for (Book book : books) {
            if (book.isbn().equals(query)) {
                hits++;
                break;
            }
        }
    }
    return hits;
}

private static int mapLookup(Map<String, Book> byIsbn, String[] queries) {
    int hits = 0;
    for (String query : queries) {
        if (byIsbn.get(query) != null) {
            hits++;
        }
    }
    return hits;
}

本机 JDK 25 单次运行输出：

list :  354 ms, hits=5000
map  :    0 ms, hits=5000

这个数字不是基准测试，只说明数量级：线性扫描大约做了 5000 × 20000 / 2 ≈ 5000 万次字符串比较；哈希查找只做了 5000 次哈希和桶定位。数据量翻倍，线性扫描翻倍，哈希查找基本不变。 这就是复杂度的现实含义。

需要说明的是，map 显示 0 ms 不代表真的零成本，而是单次运行低于 1 ms 的计时精度。要得到可靠数字，需要预热、多次采样、用 JMH 之类的工具；卷四会讲怎么正确做 JVM 基准测试。这里只回答「该不该换容器」。

大 O 不是秒表

大 O 描述的是「输入变大时，成本怎么增长」，不是「跑多少毫秒」。同一个 O(n) 的循环，在 n=10 时可能比 O(log n) 的树查找更快，因为树的节点跳转、缓存未命中、对象分配都有常数成本。反过来，O(1) 也不等于零成本：哈希计算、桶定位、equals 比较都要花时间。

所以上面的 354 ms 和 0 ms 只能得出一个结论：在 2 万条数据、5 千次查询这个规模下，线性扫描已经成为可观测的瓶颈，哈希查找不是。 它不能推出「HashMap 永远比 ArrayList 快」，也不能推出「换成 HashMap 后程序就快了」；如果查询只发生一次，或者数据只有几十条，差异可以忽略。

看复杂度时还要注意常数因子和内存局部性：ArrayList 连续存储，遍历时缓存命中率高；LinkedList 和 HashMap 的节点分散在堆上，指针跳转多。同样是 O(n)，数组往往比链表快，这也是「默认用 ArrayList」的原因之一。

常见操作的成本

把常用操作列成表，选容器时先看这张表：

几个容易误读的点：

• HashMap 的 O(1) 是平均情况。 所有 key 都落进同一个桶时，查找退化成链表或红黑树，最坏 O(n) 或 O(log n)。正常哈希函数下这种概率极低，但恶意构造的 key 可以做到，所以对外部输入做 key 时要注意。
• LinkedList 的「中间插入 O(1)」有前提：你已经持有那个位置的节点。按索引找过去仍然是 O(n)，所以大多数业务场景它并不比 ArrayList 快。
• HashMap 的遍历成本是 O(n + 容量)，不是 O(n)。 容量远大于元素个数时，遍历会扫很多空桶；这也是容量规划的一个理由。

哈希碰撞长什么样

把 hashCode 固定成同一个值，所有 key 都会落进同一个桶：

record BadKey(String value) {
    @Override
    public int hashCode() {
        return 1;
    }
}

Map<BadKey, Integer> map = new HashMap<>();
for (int i = 0; i < 10_000; i++) {
    map.put(new BadKey("k" + i), i);
}
System.out.println("size = " + map.size());
System.out.println("get = " + map.get(new BadKey("k9999")));

本机 JDK 25 输出：

size = 10000
get = 9999

结果仍然正确，因为 equals 还把 key 区分开了；但所有 entry 挤在一个桶里，查找从「一次定位」退化成「在桶内逐个或按树比较」。JDK 8 起，桶内元素超过阈值会转成红黑树，最坏从 O(n) 改善到 O(log n)，但常数远大于正常哈希。哈希函数的质量直接决定 HashMap 的实际性能，这也是为什么不要随意覆写 hashCode 返回常量，以及为什么对外部可控的 key 要警惕哈希碰撞攻击。

扩容、负载因子与初始容量

ArrayList 和 HashMap 都会在元素变多时扩容：

• ArrayList 默认容量 10，满了之后按约 1.5 倍增长，把旧数组复制到新数组。
• HashMap 默认容量 16、负载因子 0.75；元素数超过 容量 × 0.75 时，容量翻倍并重新分配所有 entry。

扩容本身是 O(n)，但摊还到每次插入后仍是 O(1)。真正的问题是如果你知道数据量，却让它反复扩容，就会多做几次全量复制。仓储可以在构造时给出预期容量：

public InMemoryLibraryRepository(int expectedBooks) {
    int capacity = (int) (expectedBooks / 0.75f) + 1;
    this.booksByIsbn = new LinkedHashMap<>(capacity);
    this.isbnsByAuthor = new HashMap<>(capacity);
}

expectedBooks / 0.75 + 1 保证在预期元素数下不会触发扩容。+1 是防止整数截断后刚好差一个。容量不必精确，给一个量级正确的值就能减少大部分 rehash。

但别过度优化：如果预期只有几十本书，默认容量足够；如果预期是 10 万本，而实际只装了 100 本，预设大容量会白占内存。容量规划的依据是可信的规模估计，不是拍脑袋。

索引：把按作者查询降到 O(1)

10.1 的 findByAuthor 仍然走 default 方法，遍历 findAll()，复杂度 O(n)。如果按作者查询很频繁，可以维护一个倒排索引：作者 -> ISBN 集合。

private final Map<String, Set<String>> isbnsByAuthor = new HashMap<>();

@Override
public void save(Book book) {
    Book previous = booksByIsbn.put(book.isbn(), book);
    if (previous != null) {
        Set<String> oldAuthorBooks = isbnsByAuthor.get(previous.author());
        if (oldAuthorBooks != null) {
            oldAuthorBooks.remove(previous.isbn());
        }
    }
    isbnsByAuthor.computeIfAbsent(book.author(), key -> new LinkedHashSet<>()).add(book.isbn());
}

@Override
public List<Book> findByAuthor(String author) {
    Set<String> isbns = isbnsByAuthor.getOrDefault(author, Set.of());
    List<Book> matched = new ArrayList<>(isbns.size());
    for (String isbn : isbns) {
        Book book = booksByIsbn.get(isbn);
        if (book != null) {
            matched.add(book);
        }
    }
    return List.copyOf(matched);
}

索引把查询从「扫所有书」变成「取一个作者对应的 ISBN 集合，再按 ISBN 取书」，平均 O(1) + O(k)，k 是该作者的书数。代价是：

• 写入变慢、变复杂。 每次 save 都要更新索引；替换一本书时，还要先把旧作者索引里的 ISBN 删掉，否则会留下脏数据。
• 删除也要维护。 deleteByIsbn 不能只从 booksByIsbn 删除，还要从 isbnsByAuthor 里移除，否则查询会拿到已经不存在的书。
• 内存增加。 索引本身是额外的 Map 和 Set，每个 ISBN 在索引里多存一份引用。

不是所有查询都值得建索引。search(keyword) 是标题/作者的子串匹配，普通的 Map 索引帮不上忙；要么全表扫描，要么引入分词或 n-gram 索引，那是另一个复杂度层级。先确认查询频率和慢查询的实际成本，再决定建不建索引。

内存不是免费的

集合的便利有内存代价。三个主要来源：

1. 对象头与引用。 ArrayList 内部是一个 Object[]，每个元素是一个引用；HashMap 的每个 entry 是一个 Node 对象，包含 hash、key 引用、value 引用、next 引用。同样存 10 万个对象，HashMap 比 ArrayList 多出 10 万个 Node 对象和一张桶数组。具体字节数随 JVM 版本、压缩指针开关变化，但「每个 entry 多一个对象」这个量级是稳定的。

2. 装箱。 泛型不能直接用基本类型，List<Integer> 存的是 Integer 对象。每个 Integer 是一个独立对象（除了缓存范围），比 int 大得多。JDK 缓存了 -128 到 127 的 Integer：

Integer a = 127;
Integer b = 127;
Integer c = 128;
Integer d = 128;

System.out.println("127 == 127 : " + (a == b));
System.out.println("128 == 128 : " + (c == d));
System.out.println("128 equals 128 : " + c.equals(d));

本机 JDK 25 输出：

127 == 127 : true
128 == 128 : false
128 equals 128 : true

127 落在缓存范围，两个变量指向同一个对象；128 超出范围，== 比较的是引用，所以是 false。这提醒两件事：比较包装类型用 equals，不要用 ==；大量数值用 int[] 或专用集合，不要用 List<Integer>。

3. 集合视图持有原集合。 List.subList 返回的是原列表的视图，不是拷贝；只要视图还在，原列表就回收不了。截取一小段却长期持有，可能让整个大列表无法释放。

一次可复现的内存测量

下面这段程序用 Runtime 粗测 100 万个 Integer 和 100 万个 int 的堆占用。每次测量前调用 System.gc() 并等待 100 ms，减少上一次分配的影响：

int n = 1_000_000;

long beforeBoxed = usedMemory();
List<Integer> boxed = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
    boxed.add(i);
}
long afterBoxed = usedMemory();

long beforePrimitive = usedMemory();
int[] primitive = new int[n];
for (int i = 0; i < n; i++) {
    primitive[i] = i;
}
long afterPrimitive = usedMemory();

System.out.printf("List<Integer> delta = %.1f MB (size=%d)%n",
        (afterBoxed - beforeBoxed) / 1024.0 / 1024.0, boxed.size());
System.out.printf("int[] delta = %.1f MB (length=%d)%n",
        (afterPrimitive - beforePrimitive) / 1024.0 / 1024.0, primitive.length);

usedMemory() 的实现是「触发 GC、等一会儿、读已用堆」：

private static long usedMemory() throws InterruptedException {
    System.gc();
    Thread.sleep(100);
    Runtime runtime = Runtime.getRuntime();
    return runtime.totalMemory() - runtime.freeMemory();
}

本机 JDK 25 两次运行结果一致：

List<Integer> delta = 18.5 MB (size=1000000)
int[] delta = 4.6 MB (length=1000000)

List<Integer> 比 int[] 多出约 14 MB，主要来自 100 万个 Integer 对象头和引用。这个测量方法很粗：System.gc() 不保证立刻回收，JIT 和线程栈也会影响结果，所以只适合看量级，不适合做精确对比。但它足以说明：当数据是大量数值时，装箱的代价是实实在在的。

在 library 里落地

把容量规划和作者索引合进仓储，LibraryService 的调用方式不变：

LibraryRepository repository = new InMemoryLibraryRepository(catalog.size());
LibraryService service = new LibraryService(repository, new StandardFinePolicy());

本机跑 6 本书的目录：

total = 6
byAuthor(刘慈欣) = 1
borrow due = 2026-10-26
return fine = 300

数据量小的时候，索引和线性扫描的差别看不出来；但容量规划、索引维护、删除清理这些代码路径必须提前写对，否则数据量上来后才补，容易漏掉「替换书时旧作者索引没删」这类 bug。

一个实用的判断顺序：

1. 先用最简单的 ArrayList 或 HashMap 把功能写对。
2. 用真实数据量测一次最慢的查询。
3. 只有确认它成为瓶颈，才加索引、调容量、换数据结构。
4. 每次优化后重新测，确认收益大于维护成本。

常见错误与边界

在循环里用 List.contains 做去重。 两层循环的复杂度是 O(n²)；1 万条数据就是 1 亿次比较。需要去重时用 HashSet，需要保序用 LinkedHashSet。

在循环里做无意义的装箱。 Long sum = 0L; for (...) sum += i; 每次都会创建 Long 对象；用 long sum 而不是 Long sum。集合里存大量数值时，优先考虑 int[]、long[] 或专用库。

用 == 比较包装类型或字符串。 Integer 的缓存范围、String 的常量池都会让 == 偶尔「看起来对」，换个数据就错。值比较用 equals，枚举比较用 ==。

没有预热就测性能。 第一次运行包含类加载、JIT 编译，数字偏高；单次 nanoTime 也可能被 GC 或调度打断。要做可靠对比，至少预热几轮、多次采样，并记录 JVM 参数。

为了「以后可能快」提前上复杂结构。 没有测量数据的优化，通常只是把代码变复杂。先写对，再测，再优化。

小结

• 线性扫描是 O(n)，哈希查找平均 O(1)；2 万本书、5 千次查询在本机相差三个数量级。
• HashMap 的 O(1) 是平均情况，最坏会退化；TreeMap 稳定 O(log n)，但常数更大。
• 扩容是 O(n) 摊还 O(1)；知道数据量时用 预期元素数 / 0.75 + 1 预设容量。
• 索引能把按作者查询降到平均 O(1)，代价是写入、删除和内存都要同步维护。
• 集合的内存开销来自对象头、entry 对象、装箱和视图引用；List<Integer> 远比 int[] 贵。
• 优化顺序是：写对、测量、确认瓶颈、再换结构；没有测量的优化不算优化。

知道了每种容器贵在哪，下一步是把它们用顺手：怎么遍历、怎么在遍历中删除、怎么按多个字段排序，以及为什么中文排序不能用默认的字符串比较。

阅读导航：上一节：10.1 List、Set、Map：三种容器的选择 · 下一节：10.3 遍历、排序与比较器 。