SwiftUI List 中隐藏的 O(n²)：一行 contains 如何悄悄拖慢整个列表
type
status
date
slug
summary
tags
category
icon
password
wechat_gate
深入解析 SwiftUI List 中 Array.contains() 带来的隐藏 O(n²) 性能问题，理解 SwiftUI body 重计算机制，学习使用 Set 将查找优化为 O(1)，提升列表滚动性能。
最近代码评审时遇到一个非常典型的性能问题。
代码看起来完全合理，功能没有任何问题，甚至大多数时候运行也很流畅。
但当数据量慢慢变大以后，滚动开始出现轻微卡顿，而性能瓶颈却非常难定位。
原因就在这一行：
很多人第一次看到都会觉得：
不就是判断一下是否收藏了吗？
事实上，这里隐藏着一个典型的算法复杂度问题。
为什么它会变成 O(n²)
假设：
对于 List 中的每一个帖子：
都需要遍历一次
favorites。一次查找的复杂度是：
整个 List：
也就是：
如果：
那么就是大家熟悉的：
例如：
理论上一次完整遍历就是：
如果 View 又频繁重新计算，这部分开销就会不断重复。
为什么 SwiftUI 会放大这个问题？
这里容易产生一个误解。
很多文章都会写：
SwiftUI 每一帧都会重新执行整个 List。
严格来说，这句话并不准确。
实际上，
List 自身具有很多优化：- Lazy Creation（懒创建）
- Cell Reuse（复用）
- Diffing（差异计算）
- Virtualization（虚拟化）
也就是说：
SwiftUI 并不会每一帧重新创建整个 List。
但是：
只要某个 Row 的
body 被重新计算，这里的 contains 就会再次执行。例如：
- State 更新
- ObservableObject 更新
- Environment 更新
- 滚动导致可见 Cell 更新
都会重新执行：
所以真正的问题不是：
List 很慢。
而是：
每一次 Row 重绘，都需要重新扫描整个收藏数组。
当可见区域较多、滚动频繁、数据规模较大时，这部分算法成本就会逐渐放大。
更好的写法
最简单的方法，就是把收藏 ID 提前放进一个
Set。这里发生了两件事情。
首先：
构建 Set：
之后：
每一次查询：
平均复杂度：
于是整个 List 的复杂度变成：
相比原来的：
这是一个数量级上的优化。
为什么 Set 能做到 O(1)
因为：
需要一个一个比较：
而：
底层是哈希表（Hash Table）。
查询时会先计算：
直接定位到对应的 Bucket。
平均情况下：
需要说明的是：
理论上的最坏情况仍然可能退化成 O(n)，例如大量 Hash Collision。
不过 Swift 标准库的 Hash 实现已经非常成熟，在实际开发中通常可以认为查询成本是常数时间。
一个经常踩的坑
很多人知道应该用
Set，于是这样写：这实际上更慢。
因为：
每一个 Row 都重新创建了一次 Set。
假设：
那么：
就会创建：
整个复杂度重新变成：
甚至由于：
- Hash 计算
- 内存分配
- Bucket 初始化
很多情况下比原来的
contains(where:) 还要慢。因此：
Set 一定要在 List 外面构建一次。
Instruments 才优化，还是提前优化？
这是一个很值得讨论的问题。
我的看法是：
这属于一种低成本、高收益的优化，可以提前做。
原来的代码：
和：
可读性几乎没有区别。
却把算法复杂度从：
降低到了：
几乎没有任何维护成本。
这种优化完全没有必要等 Instruments 告诉你。
当然，如果为了性能引入复杂缓存、手写索引或者额外状态管理，那就应该以实际 Profiling 数据为依据，而不是过早优化。
Diffable Data Source 能解决吗？
很多人会想到：
Diffable Data Source 会不会自动优化这种问题？
答案是否定的。
Diffable Data Source 负责的是：
- 插入
- 删除
- 更新
- 动画
- Diff 算法
它不会改变：
的查找复杂度。
因为这是你的业务查询逻辑，而不是列表更新算法。
生产环境更推荐的做法
如果「是否收藏」属于高频查询，通常不会每次都从数组开始查找。
更常见的是直接维护一个索引结构，例如：
或者：
这样：
查询：
更新：
整个数据结构天然就是面向 O(1) 查询设计的，而不是每次都重新把数组转换成 Set。
总结
这段代码的问题，并不是 SwiftUI，也不是
List。真正的问题在于：
放在了每一个 Row 的计算路径中。
随着数据量增长，它会不断重复线性扫描数组，使整体复杂度从 O(n + m) 退化为 O(n × m)，当两个集合规模接近时，就形成了典型的 O(n²) 性能问题。
对于这种高频查找场景，提前构建
Set 或维护基于哈希的索引，是一种几乎没有额外维护成本、却能显著降低算法复杂度的优化方式。很多 SwiftUI 性能问题，本质上并不是框架的问题，而是把线性查找放进了会被频繁重新计算的
body 中。理解这一点，比记住某一种优化技巧更重要。