4. 算法与数据结构优化

聊到性能优化，算法和数据结构这块是绕不开的硬骨头。我见过太多项目，硬件堆得挺猛，结果跑起来慢得像蜗牛，一查全是算法选型出了问题。说白了，代码写得再漂亮，底层逻辑不对，一切都是白搭。

这一章，咱们就扎进去看看，怎么从算法和数据结构的角度，把性能给榨出来。

4.1 时间复杂度与空间复杂度：性能的度量衡

你想想看，两个程序都能算出结果，但一个眨眼功夫，另一个要喝杯咖啡。区别在哪？就在复杂度上。

时间复杂度，衡量的是代码执行时间随数据量增长的趋势。不是精确的秒数，而是“量级”。比如 O(1) 是常数级，不管数据多大，时间都差不多；O(n) 是线性级，数据翻倍，时间也翻倍；O(n²) 是平方级，数据一多，时间就爆炸。

空间复杂度，衡量的是代码运行时占用的内存空间。有些算法快是快，但内存吃得厉害，这在嵌入式或移动端就是灾难。

核心原则： 时间复杂度和空间复杂度往往需要权衡。用空间换时间，或者用时间换空间，没有绝对的好坏，只有合不合适的场景。

我记得有一次优化一个日志分析系统，原始代码用了三层嵌套循环，数据量一上百万，直接卡死。我把它改成哈希表加一次遍历，时间复杂度从 O(n³) 降到了 O(n)，内存虽然多了几百 KB，但执行时间从 5 分钟降到了 2 秒。这笔买卖，值。

4.2 常见算法优化技巧

实战中，我总结了几招特别管用的优化技巧。嗯，这里要注意，不是所有技巧都万能，得看场景。

4.2.1 空间换时间：缓存与预计算

这是最常用的招数。把重复计算的结果存起来，下次直接用。

  • 缓存： 比如用 Redis 缓存数据库查询结果，或者用本地 HashMap 缓存函数计算结果。
  • 预计算： 比如游戏里的碰撞检测，提前把地图网格化，运行时直接查表，省得每帧都算一遍。
// 一个简单的斐波那契数列缓存示例
// 没有缓存时，n=50 能算到天荒地老
// 加了缓存，瞬间出结果

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {
    private static Map<Integer, Long> cache = new HashMap<>();

    public static long fib(int n) {
        if (n <= 1) return n;
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        long result = fib(n - 1) + fib(n - 2);
        cache.put(n, result);
        return result;
    }
}

我的习惯： 写递归函数时，第一件事就是考虑要不要加缓存。尤其是那种参数组合有限、但调用次数极多的场景，缓存能救命。

4.2.2 减少不必要的计算：懒加载与短路求值

能不现在算的，就晚点算。能不全部算的，就只算一部分。

  • 懒加载： 对象创建时，不初始化所有字段。等真正用到某个字段时，再加载。比如 ORM 框架里的延迟加载。
  • 短路求值： 逻辑与 (&&) 和逻辑或 (||) 运算中，如果第一个条件已经能决定结果，第二个条件就不执行了。比如 if (user != null && user.getName().equals("admin"))，如果 user 是 null，就不会执行 getName()，避免了空指针。

4.2.3 循环优化：减少循环次数与循环内操作

循环是性能杀手。优化循环，往往立竿见影。

  • 减少循环次数： 能用二分查找的，别用线性查找。能用哈希的，别用遍历。
  • 减少循环内操作： 把循环内不变的表达式提到外面。比如 for (int i = 0; i < list.size(); i++)，每次循环都调用 size() 方法，不如先 int len = list.size() 再循环。
  • 循环展开： 对于固定次数的循环，手动展开可以减少分支判断。不过现代编译器很多会自动做，不用太刻意。
// 优化前：每次循环都计算 size()
for (int i = 0; i < list.size(); i++) {
    // do something
}

// 优化后：只计算一次 size()
int len = list.size();
for (int i = 0; i < len; i++) {
    // do something
}

4.2.4 分治与并行：把大问题拆成小问题

数据量太大，单线程搞不定？那就分而治之。

  • 分治： 把大任务拆成多个小任务，分别解决，再合并结果。比如归并排序、MapReduce。
  • 并行： 利用多核 CPU，同时处理多个任务。Java 里的 ForkJoinPool、Python 里的 multiprocessing，都是干这个的。

我曾经踩过的坑： 并行不是万能的。任务拆分和合并本身有开销，如果任务太小，并行反而比串行慢。另外，线程安全问题也得小心，一不小心就死锁或者数据不一致。

4.3 数据结构选择策略

数据结构选对了，算法优化事半功倍。选错了，神仙也救不了。

下面这张图，是我自己总结的数据结构选择决策流程，你可以参考一下。

数据结构选择决策流程图 开始：分析需求 需要快速查找？ 是 需要有序？ 是 平衡树（如红黑树） 否 哈希表（HashMap） 否 频繁插入/删除？ 是 链表（LinkedList） 否 数组（ArrayList）

当然，实际场景比这张图复杂得多。比如你需要一个既能快速查找又能保持插入顺序的结构，那 LinkedHashMap 就是你的菜。你需要一个线程安全的队列，那 ConcurrentLinkedQueue 或者 BlockingQueue 就得上场。

4.3.1 数组 vs 链表

特性 数组 (ArrayList) 链表 (LinkedList)
随机访问 O(1) — 极快 O(n) — 慢
插入/删除（头部） O(n) — 需要移动元素 O(1) — 只需改指针
插入/删除（尾部） O(1) 均摊 — 很快 O(1) — 很快
内存占用 连续内存，较少 分散内存，每个节点有额外指针开销
适用场景 频繁读取，很少插入删除 频繁插入删除，很少随机访问

我个人习惯是，90% 的场景直接用 ArrayList。只有在明确需要频繁在头部插入删除，或者数据量极大且不确定大小时，才考虑 LinkedList。

4.3.2 哈希表 vs 树结构

特性 哈希表 (HashMap) 树结构 (TreeMap)
查找 O(1) 平均，O(n) 最坏 O(log n)
有序性 无序 有序（按自然顺序或比较器）
内存 较高（有负载因子和扩容） 较高（有节点指针）
适用场景 快速查找，不需要顺序 需要范围查询、排序、按顺序遍历

避坑指南： 我曾经在需要频繁范围查询的场景用了 HashMap，结果每次都要遍历所有数据，性能惨不忍睹。后来换成 TreeMap，利用它的 subMap() 方法，性能直接提升了 10 倍。选对结构，比优化代码本身更重要。

4.4 总结

算法与数据结构优化，说白了就是两件事：选对结构，用对技巧。时间复杂度、空间复杂度是衡量标准，缓存、懒加载、循环优化、分治并行是常用手段。而数据结构的选择，得根据你的业务场景来——要快查用哈希，要有序用树，要频繁插删用链表，要随机访问用数组。

没有银弹，只有权衡。多积累实战经验，慢慢你就会有感觉了。

← 上一章 📖 返回目录 下一章 →