Flutter 基础体系 · 第 24/80 篇。示例基于当前稳定 Flutter 与 Dart 3 语言能力；Android、iOS、桌面和 Web 差异会明确说明。
Dart 集合：List、Set、Map、Iterable、扩展和复杂度
Dart 集合主要用于组织一组对象。List 表示有序序列，Set 表示不重复的元素集合，Map 表示键到值的映射，Iterable 表示可以被逐个遍历的数据源。它们都位于 dart:core，不需要额外导入；dart:collection 还提供了树结构、不可变视图和其他集合实现。
理解 Dart 集合不能只记住“List 是数组、Set 去重、Map 存键值对”。实际代码中的行为还取决于：
- 元素或键如何比较相等；
- 集合是否可变；
- 集合是否保留插入顺序；
- 操作是立即执行还是延迟执行；
- 访问、查找、插入和删除的复杂度；
- 集合是否只是某个底层集合的视图；
- 遍历期间底层数据是否发生变化。
一、集合的共同基础：对象、相等性和可变性
1.1 final 只限制变量绑定，不限制集合内容
下面的 final 变量不能重新指向另一个 List，但仍然可以修改原列表：
void main() {
final numbers = <int>[1, 2];
numbers.add(3); // 合法
print(numbers); // [1, 2, 3]
// numbers = <int>[4, 5]; // 编译错误：不能重新赋值
}
final 约束的是变量本身：
变量 numbers ──► List 对象 [1, 2]
调用 add 改变的是对象内容，而不是 numbers 这个引用。若需要内容也不能修改，应使用不可变集合或只暴露只读接口。
void main() {
final numbers = List<int>.unmodifiable([1, 2]);
// numbers.add(3); // UnsupportedError
print(numbers);
}
List.unmodifiable 会创建一个不可修改的列表结果。它不是“把已有列表加一个只读类型标记”这么简单；如果需要的是对已有集合的动态只读视图，可以使用 UnmodifiableListView：
import 'dart:collection';
void main() {
final source = <int>[1, 2];
final view = UnmodifiableListView(source);
source.add(3);
print(view); // [1, 2, 3]
// view.add(4); // UnsupportedError
}
这里的 view 不允许通过自身修改数据，但仍然反映 source 后续的变化。工程中暴露只读数据时，必须明确需要“不可变快照”还是“动态只读视图”。
1.2 Dart 默认不是结构化比较
两个内容相同的 List 默认不因为元素相同而相等：
void main() {
final a = [1, 2, 3];
final b = [1, 2, 3];
print(a == b); // false
print(identical(a, b)); // false
}
默认集合的 == 通常是对象身份比较。Set 和 Map 也不能直接假定 == 会执行深度内容比较。
如果业务需要按内容比较列表，需要显式定义比较规则。例如不引入第三方包时，可以自己实现：
bool listEquals<T>(List<T> a, List<T> b) {
if (identical(a, b)) return true;
if (a.length != b.length) return false;
for (var i = 0; i < a.length; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
void main() {
print(listEquals([1, 2], [1, 2])); // true
}
Flutter 项目中也常见 package:flutter/foundation.dart 提供的 listEquals，但它依然是浅层比较：如果列表元素本身是对象，则元素对象的相等性仍由该对象的 == 决定。
1.3 Set 和 Map 依赖 == 与 hashCode
对于哈希集合，若两个对象相等，则它们必须有相同的哈希值：
a == b ⇒ a.hashCode == b.hashCode
反方向不成立：
a.hashCode == b.hashCode ⇏ a == b
哈希冲突是可能的，集合仍需通过 == 做最终判断。
因此，作为 Set 元素或 Map 键的对象，其参与相等性和哈希计算的字段不应在存入集合后改变。否则会出现“对象明明存在，却查找不到”的现象：
class User {
User(this.id);
int id;
@override
bool operator ==(Object other) =>
other is User && other.id == id;
@override
int get hashCode => id.hashCode;
}
void main() {
final user = User(1);
final users = <User>{user};
user.id = 2;
print(users.contains(user)); // 结果可能为 false
}
这里不是集合把对象删除了，而是对象的哈希位置已经由 id == 1 对应的位置变成了 id == 2 对应的位置。哈希集合通常不会扫描所有桶重新定位对象。
更安全的做法是让键对象不可变：
class ImmutableUser {
const ImmutableUser(this.id);
final int id;
@override
bool operator ==(Object other) =>
other is ImmutableUser && other.id == id;
@override
int get hashCode => id.hashCode;
}
二、List：有序、可索引的序列
List<E> 表示按照整数索引访问的元素序列：
final names = <String>['Ada', 'Linus', 'Grace'];
print(names[0]); // Ada
print(names.length); // 3
索引必须满足：
0 ≤ index < list.length
否则会抛出 RangeError。
2.1 List 的核心操作
void main() {
final numbers = <int>[10, 20, 30];
numbers.add(40); // 追加
numbers.insert(1, 15); // 在索引 1 插入
numbers[0] = 5; // 按索引更新
numbers.remove(30); // 删除第一个等于 30 的元素
numbers.removeAt(0); // 删除索引 0 的元素
print(numbers);
}
List 主要适合以下关系：
位置有意义
可以重复
需要按索引访问
经常顺序遍历
例如分页数据、消息列表、Flutter 中的子组件列表，通常使用 List。
2.2 可增长 List、固定长度 List 和不可修改 List
默认列表字面量创建的是可增长列表：
final values = <int>[1, 2];
values.add(3); // 合法
可以显式创建固定长度列表：
void main() {
final values = List<int>.filled(3, 0);
values[0] = 10; // 合法
// values.add(20); // UnsupportedError
print(values); // [10, 0, 0]
}
固定长度表示长度不能改变，但已有位置仍可能可以赋值。List.unmodifiable 则连已有位置的赋值也禁止：
void main() {
final values = List<int>.unmodifiable([1, 2]);
// values[0] = 10; // UnsupportedError
// values.add(3); // UnsupportedError
}
List.filled 的另一个边界是：填充值只计算一次，所有位置可能引用同一个可变对象。
void main() {
final lists = List<List<int>>.filled(2, []);
lists[0].add(1);
print(lists); // [[1], [1]]
}
如果每个位置都需要独立对象，应使用生成器：
void main() {
final lists = List<List<int>>.generate(
2,
(_) => <int>[],
);
lists[0].add(1);
print(lists); // [[1], []]
}
2.3 List 的典型复杂度
设列表当前有 n 个元素：
| 操作 | 常见复杂度 | 原因 |
|---|---|---|
list[i] |
O(1) | 直接按索引定位 |
list[i] = value |
O(1) | 直接更新位置 |
add |
摊销 O(1) | 容量不足时可能扩容复制 |
insert(0, value) |
O(n) | 后续元素需要移动 |
removeAt(0) |
O(n) | 后续元素需要前移 |
remove(value) |
O(n) | 先查找，再移动元素 |
contains(value) |
O(n) | 线性扫描 |
sort |
通常 O(n log n) | 取决于实现和比较器 |
sublist |
O(k) | 复制 k 个元素 |
“摊销 O(1)”表示不是每次追加都只付出常数代价。底层容量不足时，列表可能申请更大的存储空间并复制旧元素，这一次可能是 O(n)；但把一系列追加操作平均到整体上，单次追加的平均成本通常仍为 O(1)。
这解释了为什么以下代码通常比不断在头部插入更合适：
final result = <int>[];
for (var i = 0; i < 10000; i++) {
result.add(i);
}
若改成每次 insert(0, i)，每一步都可能移动已有元素，总成本近似为：
1 + 2 + 3 + ... + n = n(n + 1) / 2 = O(n²)
三、Set：不重复元素的集合
Set<E> 表示元素集合。集合的关键约束是：按照集合使用的相等性规则，同一个元素不能出现多次。
void main() {
final tags = <String>{'dart', 'flutter', 'dart'};
print(tags); // [dart, flutter]，具体显示顺序取决于具体实现
print(tags.length); // 2
}
空集合必须显式标注类型或调用构造函数：
final emptySet = <String>{};
下面是空的 Map，不是空的 Set：
final emptyMap = <String, int>{};
因为 {} 在 Dart 中表示空 Map；而包含元素的集合字面量会根据元素形状推断为 Set 或 Map。
3.1 Set 的用途和相等性
当问题是“某个元素是否已经出现过”时，Set 通常比 List 更直接：
void main() {
final visited = <String>{};
if (visited.add('home')) {
print('第一次访问 home');
}
if (!visited.add('home')) {
print('home 已经访问过');
}
}
Set.add 返回一个布尔值：
- 返回
true：集合原来没有该元素，本次成功加入； - 返回
false：等价元素已经存在，集合内容未增加。
这比先 contains 再 add 更好，因为后者通常需要进行两次查找：
if (!visited.contains(page)) {
visited.add(page);
}
3.2 默认 Set、HashSet 和 SplayTreeSet
Set 的接口不等于某一种具体数据结构。常见实现包括：
LinkedHashSet：默认 Set 字面量通常使用它，保留插入顺序；HashSet：基于哈希，通常不应依赖遍历顺序；SplayTreeSet：按照比较器排序，查找、插入和删除通常为 O(log n)。
import 'dart:collection';
void main() {
final insertionOrder = <int>{3, 1, 2};
final sorted = SplayTreeSet<int>()..addAll([3, 1, 2]);
print(insertionOrder); // 常见结果：[3, 1, 2]
print(sorted); // [1, 2, 3]
}
对于默认 Set，插入顺序是常见 LinkedHashSet 的语义；如果代码明确要求排序，应直接使用 SplayTreeSet 或显式排序后的 List，不要把“当前实现碰巧输出有序”当作无序结构的保证。
3.3 Set 运算
Set 适合表达集合运算：
void main() {
final a = {1, 2, 3};
final b = {3, 4, 5};
print(a.union(b)); // {1, 2, 3, 4, 5}
print(a.intersection(b)); // {3}
print(a.difference(b)); // {1, 2}
print(a.containsAll({1, 3})); // true
}
若 a 有 n 个元素，b 有 m 个元素，哈希 Set 上的并集、交集和差集通常可以做到接近 O(n + m)，但具体成本仍取决于哈希质量、实现和元素相等性计算。
四、Map：从键到值的映射
Map<K, V> 建立键和值之间的关系：
void main() {
final ages = <String, int>{
'Ada': 36,
'Grace': 28,
};
print(ages['Ada']); // 36
}
同一个键只能对应一个值。再次写入相同键会覆盖旧值：
void main() {
final scores = <String, int>{'dart': 80};
scores['dart'] = 95;
print(scores['dart']); // 95
}
Map 的主要模型是：
key ──► value
它适合通过唯一标识查找对象，例如用户 ID、配置名、缓存键和 JSON 对象字段。
4.1 区分“键不存在”和“值为 null”
如果值类型允许 null，下面两种情况都可能得到 null：
final data = <String, String?>{
'present-null': null,
};
print(data['missing']); // null：键不存在
print(data['present-null']); // null：键存在，值为 null
必须用 containsKey 区分：
void main() {
final data = <String, String?>{
'present-null': null,
};
print(data.containsKey('missing')); // false
print(data.containsKey('present-null')); // true
}
这是处理缓存、配置和数据库结果时的常见边界。不能仅通过 map[key] == null 判断键是否不存在。
4.2 Map 的遍历
void main() {
final prices = <String, double>{
'book': 10.5,
'pen': 2.0,
};
for (final entry in prices.entries) {
print('${entry.key}: ${entry.value}');
}
prices.forEach((key, value) {
print('$key costs $value');
});
}
entries 返回一个 Iterable<MapEntry<K, V>>。如果只需要键或值，可以使用：
prices.keys; // Iterable<String>
prices.values; // Iterable<double>
默认 Map 字面量通常是 LinkedHashMap，会保留插入顺序。HashMap 不应依赖遍历顺序，而 SplayTreeMap 按比较器排序：
import 'dart:collection';
void main() {
final sorted = SplayTreeMap<String, int>()
..['c'] = 3
..['a'] = 1
..['b'] = 2;
print(sorted.keys); // (a, b, c)
}
4.3 Map 的典型复杂度
设 Map 有 n 个键：
| 操作 | 哈希 Map 常见平均复杂度 | SplayTreeMap 常见复杂度 |
|---|---|---|
map[key] |
O(1) | O(log n) |
map[key] = value |
O(1) | O(log n) |
containsKey |
O(1) | O(log n) |
remove(key) |
O(1) | O(log n) |
| 遍历全部键值 | O(n) | O(n) |
哈希 Map 的 O(1) 是平均复杂度，不是无条件保证。哈希冲突严重、键的 hashCode 实现不佳或哈希表扩容时，实际性能会下降。
如果需求是“按照键排序并持续插入、查找”，树 Map 比“每次改动后重新对 Map 的键排序”更符合问题模型。反过来，如果只是最终显示一次排序结果，转成列表后排序可能更简单：
final keys = prices.keys.toList()..sort();
五、Iterable：遍历能力，而不是具体存储结构
Iterable<E> 描述的是“可以逐个产生 E 类型元素的对象”。它不规定底层一定是 List、Set 还是已经存储好的数组。
Iterable<int> values() sync* {
yield 1;
yield 2;
yield 3;
}
List 和 Set 都实现了 Iterable，但 Iterable 本身不提供列表的随机索引语义。下面的操作不一定具有相同复杂度：
Iterable<int> values = [10, 20, 30];
print(values.first); // 第一个元素
print(values.last); // 最后一个元素
print(values.elementAt(1));
print(values.length);
对于普通列表，elementAt(1) 可以直接访问；对于一个只会逐个生成元素的 Iterable，它可能必须从头产生元素直到第 2 个。
5.1 map、where 等操作通常是惰性的
void main() {
final source = [1, 2, 3, 4];
final result = source
.where((value) => value.isEven)
.map((value) => value * 10);
print(result); // (20, 40)
}
where 和 map 返回的通常是惰性 Iterable。创建 result 时，过滤和乘法不一定已经执行；真正遍历它时才逐个计算。
可以通过日志观察这一点：
void main() {
final source = [1, 2, 3];
final result = source.map((value) {
print('计算 $value');
return value * 2;
});
print('Iterable 已创建');
print(result.first);
}
典型输出顺序是：
Iterable 已创建
计算 1
2
惰性计算带来两个重要后果。
第一，某些终止操作可以提前结束：
final firstLarge = source
.map((value) => value * 100)
.firstWhere((value) => value > 150);
找到满足条件的元素后，不必处理后面的元素。
第二，多次遍历可能重复执行计算：
void main() {
final source = [1, 2, 3];
final result = source.map((value) {
print('计算 $value');
return value * 2;
});
print(result.toList());
print(result.toList());
}
两次 toList() 通常会各自重新遍历 source，转换逻辑也会各自执行一次。如果结果需要复用，应物化为 List：
final cached = source.map((value) => value * 2).toList();
物化意味着立即遍历并分配新列表，时间通常为 O(n)，空间为 O(n)。
5.2 Iterable 的链式复杂度
考虑：
final result = source
.where((x) => x > 0)
.map((x) => x * 2)
.take(3)
.toList();
如果 source 是长度为 n 的普通列表：
where、map和take通常不会各自创建完整中间列表；toList触发一次遍历；- 最多为了找到 3 个符合条件的元素而访问整个源；
- 最坏时间复杂度为 O(n)；
- 最终结果空间为 O(1) 到 O(n)，这里
take(3)的结果最多存 3 个元素，因此结果存储是 O(1)。
这和手工写出多个中间列表不同：
final positive = source.where((x) => x > 0).toList();
final doubled = positive.map((x) => x * 2).toList();
final result = doubled.take(3).toList();
后者会分配多个列表，可能占用更多内存。惰性链并不保证一定更快：如果链中的转换很复杂，或者结果需要反复遍历，提前物化可能更合适。
5.3 常用 Iterable 操作的复杂度
设源序列最多包含 n 个元素：
| 操作 | 一般复杂度 | 说明 |
|---|---|---|
where / map 创建结果 |
通常 O(1) | 创建惰性包装 |
遍历 where / map |
O(n) | 每个源元素可能被处理 |
contains |
O(n) | 找到目标后可提前结束 |
firstWhere |
最好 O(1)，最坏 O(n) | 线性查找 |
any / every |
最好 O(1)，最坏 O(n) | 支持提前结束 |
length |
通常 O(n) | 一般需要遍历计算 |
elementAt(i) |
取决于实现 | List 常见 O(1)，一般 Iterable 可能 O(i) |
toList / toSet |
O(n) | 遍历并创建集合 |
skip(k) |
创建通常 O(1)，遍历时跳过 | 具体实现可能不同 |
这些是常见实现下的复杂度分析，不应把 Iterable 接口误认为固定的数据结构。若代码依赖随机访问或高频索引访问，应明确保存为 List，而不是只保存为 Iterable。
5.4 Iterable 与 Stream 不是同一种抽象
Iterable 用于同步遍历：
for (final item in iterable) {
print(item);
}
Stream 用于异步事件序列：
await for (final item in stream) {
print(item);
}
两者都能表达“多个元素”，但生命周期和错误传播方式不同：
Iterable的计算发生在当前同步调用栈中；Stream可能跨越事件循环和异步边界；Iterable的异常通常在调用遍历操作时同步抛出；Stream的错误通过异步流订阅传播。
Flutter 中网络响应、文件读取和用户事件通常是 Future 或 Stream，不能为了方便把异步数据直接当成 Iterable 使用。
六、集合字面量、展开和条件元素
Dart 支持集合字面量：
final list = <int>[1, 2, 3];
final set = <int>{1, 2, 3};
final map = <String, int>{
'one': 1,
'two': 2,
};
还支持集合 if 和集合 for：
void main() {
final includeZero = true;
final values = <int>[
if (includeZero) 0,
for (final value in [1, 2, 3]) value * 10,
];
print(values); // [0, 10, 20, 30]
}
展开运算符 ... 把一个可遍历集合中的元素加入外层集合：
void main() {
final base = [1, 2];
final values = [0, ...base, 3];
print(values); // [0, 1, 2, 3]
}
空安全展开 ...? 允许被展开对象为 null：
void main() {
List<int>? optionalValues;
final values = [0, ...?optionalValues, 1];
print(values); // [0, 1]
}
展开通常会把元素加入新集合，而不是让新集合自动成为旧集合的动态视图：
final source = [1, 2];
final copy = [...source];
source.add(3);
print(copy); // [1, 2]
这与 sublist 类似，属于复制结果。若业务需要源集合变化时同步反映，应使用明确的视图类型或重新计算。
七、扩展：为已有类型增加调用语法
Dart 的扩展（extension）允许在不修改原类型源码、也不创建子类的情况下，为类型增加方法、getter、setter 或运算符。
extension IntIterableSum on Iterable<int> {
int sum() {
var total = 0;
for (final value in this) {
total += value;
}
return total;
}
}
void main() {
print([1, 2, 3].sum()); // 6
}
这里的 sum 是扩展方法：
Iterable<int> ──扩展──► sum()
它不会真的把成员写入 Iterable 类，也不会给每个对象增加字段。
7.1 扩展方法根据静态类型解析
扩展调用是静态解析的，不是普通实例方法那样根据运行时类型动态分派：
extension OnString on String {
String describe() => 'extension';
}
class MyString implements String {
// 实际上 String 不能这样简单实现，这里只用于说明概念
}
更容易观察的例子是接口类型和具体类型：
extension OnObject on Object {
String label() => 'object extension';
}
extension OnString on String {
String label() => 'string extension';
}
void main() {
final String text = 'Dart';
final Object value = text;
print(text.label()); // string extension
print(value.label()); // object extension
}
虽然 value 在运行时实际保存的是 String，但它的静态类型是 Object，所以编译器选择 OnObject.label。
这意味着扩展适合提供语法便利，但不应被误解为运行时多态。若需要根据对象运行时类型选择行为，应使用真正的实例方法、接口实现或显式类型判断。
7.2 扩展不能覆盖已有实例成员
如果原类型已经有同名实例成员，实例成员优先：
extension ListLengthOverride<T> on List<T> {
int get length => -1;
}
void main() {
final values = [1, 2, 3];
print(values.length); // 3，不是 -1
}
扩展无法覆盖或替换 List 已有的 length。如果多个扩展提供同名成员，调用可能产生歧义，可以通过扩展前缀显式调用：
extension FirstValue<T> on Iterable<T> {
T? firstValue() => isEmpty ? null : first;
}
extension AnotherFirstValue<T> on Iterable<T> {
T? firstValue() => isEmpty ? null : first;
}
void main() {
final values = [1, 2, 3];
// print(values.firstValue()); // 可能产生扩展冲突
}
实际项目中应避免导入多个提供同名扩展的库，或使用库前缀、重命名导入来消除冲突。
7.3 扩展不能保存每个对象的状态
扩展可以定义方法和计算属性，但不能像类一样为每个目标对象增加实例字段：
extension on List<int> {
// int cachedSum; // 不允许：扩展不能添加实例字段
int sum() {
var total = 0;
for (final value in this) {
total += value;
}
return total;
}
}
如果需要缓存状态，应使用包装类：
class NumberCollection {
NumberCollection(this.values);
final List<int> values;
int? _cachedSum;
int get sum {
return _cachedSum ??= values.fold(0, (a, b) => a + b);
}
}
但缓存又引入了失效问题：如果外部仍能修改 values，_cachedSum 可能过期。因此包装类通常应同时控制可变性，或者在每次计算时不缓存。
7.4 用扩展封装集合操作，但不要隐藏复杂度
扩展适合表达领域语义：
extension NonEmpty<T> on Iterable<T> {
T? get firstOrNull => isEmpty ? null : first;
}
void main() {
print(<int>[].firstOrNull); // null
print([10, 20].firstOrNull); // 10
}
但调用者仍应知道其复杂度。下面这个扩展对一般 Iterable 可能是 O(n)：
extension HasAny<T> on Iterable<T> {
bool hasAny(Iterable<T> other) {
return other.any(contains);
}
}
若两个集合分别有 n、m 个元素，且 this.contains 是线性查找，最坏可能达到 O(nm)。如果需要高频交集判断，应先建立 Set：
extension ContainsAny<T> on Iterable<T> {
bool containsAny(Iterable<T> other) {
final values = toSet(); // O(n)
return other.any(values.contains); // 平均最多 O(m)
}
}
总的平均复杂度接近 O(n + m)，代价是额外 O(n) 空间。扩展改善的是表达方式，不会自动改善底层算法。
7.5 扩展声明与扩展类型不是一回事
Dart 3 还提供扩展类型（extension type）能力。扩展类型可以围绕某个表示值建立更受约束的接口，例如区分不同语义的字符串或整数；它与传统 extension method 不同：
- extension 为已有类型增加静态可调用成员；
- extension type 定义一种新的静态接口和表示方式；
- extension type 不等同于传统 class，也不应当被当作普通继承使用。
处理普通集合时，通常需要的是 extension，而不是 extension type。选择 extension type 前还应确认当前 Dart SDK 和目标编译链都支持项目使用的相关语言能力。
八、集合操作的物化、视图和副作用
集合 API 中经常出现三种不同结果：
8.1 新集合
final source = [1, 2, 3];
final copy = source.toList();
source.add(4);
print(copy); // [1, 2, 3]
toList() 创建了独立结果。map、where 本身通常返回惰性 Iterable，而 toList 会把它物化。
8.2 惰性 Iterable
final source = [1, 2, 3];
final doubled = source.map((x) => x * 2);
doubled 通常不保存完整结果，而是在遍历时计算。它适合一次性管道处理，但不适合需要频繁重复遍历且转换代价较高的场景。
8.3 动态视图
某些 API 返回底层集合的视图。例如 Map 的 keys、values 和 entries：
void main() {
final map = <String, int>{'a': 1};
final keys = map.keys;
map['b'] = 2;
print(keys); // 通常反映为 (a, b)
}
视图不等于快照。保存视图后，如果底层 Map 发生变化，后续访问视图可能观察到变化。遍历期间修改底层集合则可能抛出 ConcurrentModificationError，应避免这种写法：
final map = <String, int>{'a': 1, 'b': 2};
// 不要在遍历 map 时直接删除 map 中的元素
for (final key in map.keys) {
if (key == 'a') {
// map.remove(key); // 可能抛出 ConcurrentModificationError
}
}
可以先复制键：
for (final key in map.keys.toList()) {
if (key == 'a') {
map.remove(key);
}
}
这会额外产生 O(n) 的复制成本，但把“遍历集合”和“修改集合”分离开来。
九、复杂度：如何从操作组合推导总成本
复杂度不是集合类型的标签，而是一次操作序列的成本模型。
设：
n：第一个集合的元素数量；m：第二个集合的元素数量；k：最终需要生成的结果数量。
9.1 List 查找和嵌套查找
bool hasDuplicate(List<int> values) {
for (var i = 0; i < values.length; i++) {
for (var j = i + 1; j < values.length; j++) {
if (values[i] == values[j]) return true;
}
}
return false;
}
最坏情况下需要比较：
(n - 1) + (n - 2) + ... + 1
= n(n - 1) / 2
= O(n²)
使用 Set 可以把常见平均复杂度降低到 O(n)：
bool hasDuplicateFast<T>(Iterable<T> values) {
final seen = <T>{};
for (final value in values) {
if (!seen.add(value)) return true;
}
return false;
}
代价是额外 O(n) 空间，并且要求元素的 == 和 hashCode 正确。
9.2 Map + List 的组合
下面代码对每个用户都在列表中查找权限：
for (final user in users) {
final permission = permissions.firstWhere(
(item) => item.userId == user.id,
);
}
如果用户数为 n，权限记录数为 m，最坏复杂度是 O(nm)。
预先建立索引：
final permissionByUserId = <int, Permission>{
for (final permission in permissions)
permission.userId: permission,
};
for (final user in users) {
final permission = permissionByUserId[user.id];
}
建立 Map 平均为 O(m)，之后查询 n 次平均为 O(n)，总复杂度接近：
O(m + n)
这是集合选择中最重要的推导之一：不是“Map 永远比 List 快”，而是当问题具有唯一键时，Map 能把重复线性搜索变成索引查找。
9.3 先过滤再排序
final result = values
.where((value) => value.isValid)
.toList()
..sort(compareValues);
设过滤后有 k 个元素：
- 过滤：O(n)；
- 复制结果：包含在 O(n) 遍历中；
- 排序：通常 O(k log k)。
总复杂度通常写作：
O(n + k log k)
不能直接写成 O(n log n) 并认为两者完全相同，因为当过滤结果远小于源数据时，k 和 n 的差异会影响实际成本。
十、Flutter 中的集合：平台语义一致，运行时成本不同
List、Set、Map 和 Iterable 属于 Dart 核心库。相同 Dart 代码在 Android、iOS、桌面和 Web 上，集合的类型语义、空安全规则、相等性规则和 API 约束应保持一致。
平台差异主要来自运行时和编译目标：
- Android、iOS 和桌面通常运行 Dart 原生编译产物；
- Web 会编译到 Web 目标，底层 JavaScript 或 WebAssembly 运行时的内存模型、优化策略和调试表现可能不同；
- 集合 API 的复杂度是算法层面的分析，不应据此假定所有平台上都有相同的绝对耗时；
- 集合对象属于某个 Dart isolate 的内存。不同 isolate 之间不能直接共享可变集合，消息传递需要发送可传输的数据结构或副本语义；
- Flutter 的
build方法中常见的列表字面量会在每次构建时重新创建。若集合很大，频繁构建和转换可能增加分配与遍历成本，但是否需要缓存必须结合数据生命周期判断。
例如，下面代码在每次 build 中都创建一个新列表：
@override
Widget build(BuildContext context) {
final items = List.generate(1000, (index) => index);
return ListView.builder(
itemCount: items.length,
itemBuilder: (context, index) {
return Text('${items[index]}');
},
);
}
这段代码语义正确，但 items 只服务于当前构建。如果数据并未随构建变化，可以把它放在状态对象或其他合适的生命周期中；如果数据会变化，则应确保缓存不会导致显示旧数据。集合缓存的核心问题不是“能不能缓存”，而是数据变更后缓存何时失效。
十一、完整可运行示例：索引、去重、惰性转换和扩展
下面程序可在 Dart 3 环境中直接运行：
extension IterableStatistics on Iterable<int> {
int get sum {
var result = 0;
for (final value in this) {
result += value;
}
return result;
}
double get average {
var count = 0;
var result = 0;
for (final value in this) {
count++;
result += value;
}
if (count == 0) {
throw StateError('不能计算空集合的平均值');
}
return result / count;
}
}
class User {
const User(this.id, this.name);
final int id;
final String name;
@override
String toString() => 'User($id, $name)';
}
void main() {
final rawUsers = <User>[
const User(1, 'Ada'),
const User(2, 'Grace'),
const User(1, 'Ada again'),
];
// 1. 使用 Map 按唯一 id 建立索引。
// 相同 id 的后一个用户会覆盖前一个用户。
final userById = <int, User>{
for (final user in rawUsers) user.id: user,
};
print(userById[1]); // User(1, Ada again)
print(userById.containsKey(3)); // false
// 2. 使用 Set 去重。
final ids = rawUsers.map((user) => user.id).toSet();
print(ids); // {1, 2}
// 3. 使用 Iterable 做惰性过滤和转换。
final names = rawUsers
.where((user) => user.id > 1)
.map((user) => user.name);
print(names.toList()); // [Grace]
// 4. 扩展方法可以直接用于 Iterable<int>。
final scores = [10, 20, 30];
print(scores.sum); // 60
print(scores.average); // 20.0
}
这个示例中的数据流是：
rawUsers: List<User>
│
├── map(user => user.id).toSet()
│ └── 得到唯一 ID
│
├── for 集合字面量
│ └── 得到 Map<int, User> 索引
│
└── where(...).map(...)
└── 得到惰性 Iterable<String>
其中：
rawUsers保留顺序，并允许重复；ids只关心唯一 ID；userById通过 ID 快速查找，但重复键会发生覆盖；names在调用toList时才完成遍历；sum和average是扩展提供的调用语法，不是List或Iterable类本身新增的实例成员。
十二、常见误解与失败表现
12.1 用 List 表示唯一键索引
如果代码频繁执行：
items.firstWhere((item) => item.id == targetId);
它通常是 O(n)。当查询次数增加时，总成本会迅速变成 O(nq)，其中 q 是查询次数。若 id 唯一，应建立 Map<Id, Item>。
但如果数据量很小、只查询一次，直接使用 firstWhere 可能更简单。复杂度优化必须建立在真实访问模式上，而不是看到 Map 就机械替换。
12.2 认为 Set 或 Map 一定保持顺序
默认字面量常见地使用 LinkedHashSet 和 LinkedHashMap，所以开发者容易形成“所有 Set 和 Map 都有顺序”的错觉。
如果顺序是业务条件，应选择明确的有序实现或保存为 List。如果顺序不重要，不应依赖调试输出或当前运行时的遍历结果。
12.3 把 where 当成已经计算好的列表
final filtered = values.where(predicate);
// filtered.length 可能触发一次完整遍历
// filtered.toList() 又会再次遍历
如果 predicate 有副作用、读取外部可变状态或执行昂贵计算，多次遍历可能得到不同结果或重复执行工作。集合转换函数最好保持纯函数：相同输入产生相同输出，不修改外部状态。
12.4 忽略 Map 的空值歧义
if (cache[key] == null) {
// 这里不能确定是缓存未命中，还是缓存了 null
}
正确诊断方式是：
if (!cache.containsKey(key)) {
// 未命中
} else {
// 命中，即使值为 null
}
如果业务不允许缓存空值，也可以从类型上设计为 Map<K, V>，并在写入前拒绝 null，从而减少状态分支。
12.5 在哈希集合中修改键对象
如果修改了参与 == 或 hashCode 的字段，可能出现：
set.contains(object) == false
即便遍历集合仍能看到这个对象。诊断时应检查：
- 对象是否已经加入
Set或作为Map键； - 加入后是否修改了比较字段；
==和hashCode是否满足一致性；- 是否存在自定义比较器与默认相等性规则不一致的情况。
恢复方式通常是移除旧对象后，以新状态重新插入；更稳妥的设计是使用不可变键。
十三、选择集合的判断方式
可以按照数据关系而不是个人习惯选择：
| 需求 | 合适的类型 |
|---|---|
| 保留顺序、允许重复、按位置访问 | List<T> |
| 判断是否存在、自动去重 | Set<T> |
| 通过唯一键查找值 | Map<K, V> |
| 只需要逐个处理、希望惰性链式操作 | Iterable<T> |
| 需要按键或元素排序并维护顺序 | SplayTreeMap / SplayTreeSet |
| 需要只读快照 | List.unmodifiable / Map.unmodifiable |
| 需要底层变化可见但禁止通过视图修改 | UnmodifiableListView 等视图 |
最终需要同时回答三个问题：
数据是否有位置顺序？
元素是否允许重复？
主要操作是遍历、按索引、按键查找，还是排序？
如果答案是“有顺序、允许重复、按索引访问”，使用 List；如果答案是“只关心唯一成员”，使用 Set；如果答案是“通过稳定标识定位对象”，使用 Map；如果只需要描述遍历过程，则使用 Iterable 作为更抽象的参数类型。
例如函数通常应尽可能接受 Iterable，以支持更多输入类型：
int sumPositive(Iterable<int> values) {
var result = 0;
for (final value in values) {
if (value > 0) result += value;
}
return result;
}
调用者可以传入 List、Set 或惰性转换结果：
sumPositive([1, -2, 3]);
sumPositive({1, 1, 2});
sumPositive(StreamedData.values); // 若它实现 Iterable
而当函数确实依赖随机访问时，应明确声明 List<T>，让类型表达约束：
T middle<T>(List<T> values) {
if (values.isEmpty) {
throw StateError('列表不能为空');
}
return values[values.length ~/ 2];
}
集合类型、相等性规则、是否可变以及复杂度共同决定了代码的实际行为。掌握这些机制后，List、Set、Map 和 Iterable 不再只是几种容器，而会成为可以准确表达数据关系、访问方式和成本模型的 Dart 类型。
系列导航与关联阅读
- 系列入口：Flutter 完整学习路线：从 Dart 与 Widget 到多端架构和应用发布
- 上一篇：Dart 函数与闭包：参数、类型、捕获、Callable 和 API 设计
- 下一篇：Dart 泛型：类型参数、边界、协变、运行时类型和 API 设计
官方资料
本文依据 Flutter 与 Dart 官方文档重新梳理；正文与示例由 WR BLOG 编写。
评论
0 条讨论