# 集合

Source: https://codewiki.com/zh/csharp/collections/

> - **what**: C# 集合用不同结构保存一组值；应根据实际访问模式选择 `List`、`Dictionary<TKey, TValue>`、`HashSet`、队列或其他类型。
> - **trap**: 哈希集合依赖稳定且一致的相等性，`IReadOnlyList` 也不保证底层数据不会变化；线程安全的单次调用更不等于整个工作流原子化。
> - **fix**: 先写清查找方式、重复策略、顺序、所有权和并发边界，再选择最窄的接口与满足这些约束的具体集合。

## 是什么，为什么存在

集合（collection）把多个同类值放进一个可遍历的对象中。它不仅负责保存元素，还规定如何定位元素、是否允许重复、是否维持顺序，以及修改时会发生什么。选集合就是选择这些行为，不是换一种容器拼写。

最常用的默认类型是 `List`。它适合按位置读取、顺序遍历和在尾部追加。需要通过业务键定位值时，使用 `Dictionary<TKey, TValue>`；只关心某个值是否出现，或者要做并集与交集时，使用 `HashSet`。

访问顺序本身也可能是契约。`Queue` 按先进先出处理工作，`Stack` 按后进先出处理撤销记录，`PriorityQueue<TElement, TPriority>` 则先取比较器认为优先级最小的元素。要求始终按键排序时，可选择 `SortedDictionary<TKey, TValue>` 或 `SortedSet`。

泛型集合在编译期约束元素类型。与旧式 `ArrayList` 和 `Hashtable` 相比，它们不要求调用方围绕 `object` 强制转换，保存值类型时通常也不需要逐个装箱。新代码一般从 `System.Collections.Generic`、`System.Collections.Concurrent` 或 `System.Collections.Immutable` 中选择。

集合会出现在模型边界、缓存、批处理、调度器和 API 返回值中。此时具体类型只是问题的一部分；相等性、可变性、所有权和并发策略共同决定代码是否正确。

## 工作原理

### 接口描述调用方需要的能力

`IEnumerable` 只承诺可以依次取得元素。它不承诺能按索引读取、能重复遍历、数据已经驻留内存，甚至不承诺两次遍历得到相同结果。接受这个接口的函数不应偷偷假设参数是列表。

`ICollection` 增加 `Count` 与常见修改操作，`IList` 再增加索引访问，`ISet` 表达唯一元素和集合运算，`IDictionary<TKey, TValue>` 表达键值映射。只读接口会去掉调用方可见的修改成员，但并不自动冻结底层对象。

对参数使用满足算法所需的最窄接口。只需遍历就接收 `IEnumerable`，需要稳定计数和索引时才接收 `IReadOnlyList`。返回值则要同时表达所有权：实时只读视图、独立快照和不可变值不是同一份契约。

### 具体类型决定访问成本

| 需求 | 通常选择 | 关键约束 |
| --- | --- | --- |
| 按索引读取、在尾部追加 | `List` | 中间插入和删除会移动后续元素 |
| 通过唯一键读取值 | `Dictionary<TKey, TValue>` | 键需要稳定的哈希与相等性 |
| 去重、成员测试、集合运算 | `HashSet` | 没有可依赖的业务顺序 |
| 先进先出或后进先出 | `Queue` / `Stack` | 只从规定的一端取元素 |
| 始终按比较器排序 | `SortedDictionary<TKey, TValue>` / `SortedSet` | 查找和更新通常是 O(log n) |
| 已知节点附近频繁插入 | `LinkedList` | 找到节点本身仍是 O(n) |
| 多线程共同修改 | `System.Collections.Concurrent` 类型 | 复合业务操作可能仍需协调 |
| 发布后不再变化 | `System.Collections.Immutable` 或 `System.Collections.Frozen` 类型 | 构建成本与更新模型不同 |

`List` 以连续存储支持 O(1) 索引访问。尾部还有容量时，`Add` 只写入新位置；容量不足时需要分配更大的存储并复制元素，所以连续追加的单次成本会波动，但整体具有摊还 O(1)（amortized O(1)）成本。

`Dictionary<TKey, TValue>` 与 `HashSet` 建立在哈希表（hash table）上。它们先用哈希码缩小候选范围，再以相等性确认命中。查找通常接近 O(1)，但它依赖比较器质量、负载和输入，不能当成对所有一次调用的最坏情况保证。

排序集合通过比较器维持顺序，典型查找和更新成本是 O(log n)。它们解决的是“存储本身始终有序”，而 LINQ 的 `OrderBy` 解决的是“为这次结果产生排序序列”。如果每次只在输出前排序，不必为了排序而改变主存储结构。

### 三种顺序不能互换

“保留插入顺序”“随时按值排序”和“只取下一个最高优先级元素”是三种不同要求。把它们都写成“有序”会让实现看似合理，实际却暴露错误的操作。

| 顺序要求 | 合适结构 | 不承诺的能力 |
| --- | --- | --- |
| 按位置保留业务顺序 | `List` | 不自动按元素值排序 |
| 枚举时始终按比较器排序 | `SortedSet` / `SortedDictionary<TKey, TValue>` | 不保留插入先后 |
| 反复取出最小优先级 | `PriorityQueue<TElement, TPriority>` | 枚举本身不表示出队顺序 |

`PriorityQueue` 只保证 `Dequeue` 或 `TryDequeue` 取出比较器认为优先级最小的元素。优先级相同的元素没有先进先出保证；若稳定性属于契约，可以把递增序号纳入复合优先级。

若需要同一批数据的多条访问路径，通常应保留一个权威存储，再建立索引。例如列表保存展示顺序，字典按 ID 定位对象。更新逻辑必须同时维护这些结构，或者在边界处从权威数据重建派生索引。

### 相等性是集合契约的一部分

字典与哈希集合使用 `IEqualityComparer`。未显式提供时，它们使用 `EqualityComparer.Default`，后者依据类型的相等性实现工作。领域规则不同，例如 SKU 不区分大小写时，应在构造集合时传入明确的相等比较器（equality comparer）。

比较器必须满足同一套关系：相等的两个值必须产生相同哈希码。参与哈希与相等判断的数据在元素留在集合期间还必须保持稳定。否则对象可能仍在某个桶中，却再也无法通过修改后的键找到。

记录（record）通常会生成基于内容的结构相等性（structural equality）。这并不自动说明所有字段都适合构成业务身份；集合键仍应选择小而稳定的标识，或者传入只比较该标识的比较器。

## 示例

四个例子使用同一个库存领域，但每个集合负责不同的访问模式。输出顺序需要稳定时，示例会显式排序，而不是依赖哈希集合的枚举细节。

### 用列表保存顺序，用字典建立索引

商品先进入 `List`，因为录入顺序有意义。字典提供按 SKU 的第二条访问路径，并在构造时固定大小写规则。

<!-- quick -->

```csharp
// file: CatalogIndex.cs
using System;
using System.Collections.Generic;
using System.Linq;

List<Product> products =
[
    new("BK-1", "Book"),
    new("PN-2", "Pen"),
    new("NB-3", "Notebook")
];

var bySku = new Dictionary<string, Product>(
    StringComparer.OrdinalIgnoreCase);

foreach (Product product in products)
{
    bySku.Add(product.Sku, product);
}

bool accepted = bySku.TryAdd("bk-1", new("bk-1", "Duplicate"));
Console.WriteLine($"SKUs: {string.Join(", ", products.Select(p => p.Sku))}");
Console.WriteLine($"duplicate accepted: {accepted}");

if (bySku.TryGetValue("nb-3", out Product? found))
{
    Console.WriteLine($"lookup: {found.Name}");
}

public sealed record Product(string Sku, string Name);
```

```text
SKUs: BK-1, PN-2, NB-3
duplicate accepted: False
lookup: Notebook
```

<!-- /quick -->

`TryAdd` 把“键已存在”作为普通结果，而 `Add` 会在重复键上抛出 `ArgumentException`。`TryGetValue` 只做一次查找，并让缺失分支在控制流中可见。索引器 `bySku[key]` 更适合调用方已经建立“键必然存在”不变量的情况。

`StringComparer.OrdinalIgnoreCase` 同时提供哈希与相等判断，所以 `"BK-1"` 和 `"bk-1"` 属于同一个键。对协议标识符使用 ordinal 规则，不会受当前区域性影响。

### 用哈希集合表达唯一性与集合运算

仓库权限没有业务顺序，而且同一个权限只应出现一次。两个集合共享比较器，交集结果也会保留左侧副本的比较规则。

```csharp
// file: PermissionSet.cs
using System;
using System.Collections.Generic;
using System.Linq;

var granted = new HashSet<string>(StringComparer.OrdinalIgnoreCase)
{
    "catalog.read",
    "stock.write",
    "audit.read"
};

bool firstAdd = granted.Add("CATALOG.READ");
var required = new HashSet<string>(StringComparer.OrdinalIgnoreCase)
{
    "catalog.read",
    "orders.write"
};

var available = new HashSet<string>(granted, granted.Comparer);
available.IntersectWith(required);

Console.WriteLine($"new permission added: {firstAdd}");
Console.WriteLine($"available: {string.Join(", ", available.Order())}");
Console.WriteLine($"all required: {required.IsSubsetOf(granted)}");
```

```text
new permission added: False
available: catalog.read
all required: False
```

`Add` 的布尔返回值同时完成成员测试与插入，不需要先调用 `Contains`。`IntersectWith` 会修改接收者，因此示例先复制 `granted`。若原集合属于调用方，是否允许就地修改必须写进方法契约。

输出前调用 `Order()` 只是为了得到确定文本。算法本身不依赖 `HashSet` 的枚举顺序；如果顺序属于领域要求，应单独保存顺序或选择有序结构。

### 用队列调度，用栈撤销

待处理补货请求需要先进先出，最近一次处理记录则最先撤销。队列和栈直接表达这两条规则，调用点无需手写索引约定。

```csharp
// file: RestockWorkflow.cs
using System;
using System.Collections.Generic;

var pending = new Queue<RestockRequest>();
var completed = new Stack<RestockRequest>();

pending.Enqueue(new("BK-1", 5));
pending.Enqueue(new("PN-2", 12));
pending.Enqueue(new("NB-3", 4));

while (completed.Count < 2 && pending.TryDequeue(out RestockRequest? request))
{
    completed.Push(request);
    Console.WriteLine($"restocked {request.Sku}: {request.Quantity}");
}

if (completed.TryPop(out RestockRequest? undone))
{
    Console.WriteLine($"undo {undone.Sku}");
}

Console.WriteLine($"next: {pending.Peek().Sku}");

public sealed record RestockRequest(string Sku, int Quantity);
```

```text
restocked BK-1: 5
restocked PN-2: 12
undo PN-2
next: NB-3
```

`TryDequeue` 与 `TryPop` 把空集合变成普通分支。示例最后使用 `Peek`，因为前面的流程保证队列还剩一个元素；如果这个不变量不明确，也应使用 `TryPeek`。

两个集合只保存工作顺序，不负责事务补偿。真实撤销操作还要记录足以逆转外部状态的数据，并处理撤销本身失败的情况。

### 区分只读视图与不可变快照

`AsReadOnly()` 包装现有列表，因此调用方不能通过包装器修改列表，但仍会看到拥有者之后的修改。`ToImmutableArray()` 在调用时创建不可变快照。

```csharp
// file: PublishedCatalog.cs
using System;
using System.Collections.Generic;
using System.Collections.Immutable;

var names = new List<string> { "Book" };
IReadOnlyList<string> liveView = names.AsReadOnly();
ImmutableArray<string> snapshot = names.ToImmutableArray();

names.Add("Pen");

Console.WriteLine($"view: {string.Join(", ", liveView)}");
Console.WriteLine($"snapshot: {string.Join(", ", snapshot)}");

ImmutableArray<string> revised = snapshot.Add("Notebook");
Console.WriteLine($"original snapshot count: {snapshot.Length}");
Console.WriteLine($"revised count: {revised.Length}");
```

```text
view: Book, Pen
snapshot: Book
original snapshot count: 1
revised count: 2
```

`liveView` 是只读集合（read-only collection），不是快照。`snapshot.Add` 也不会修改原值，而是返回新的不可变数组。调用方必须接住返回值，否则这次逻辑更新会被丢弃。

两种选择都不是深度不可变保证。如果元素本身是可变对象，视图和快照仍可能指向同一个元素。需要稳定发布状态时，元素类型也应具有合适的不可变契约。

## 陷阱

### 重复查找字典

> **陷阱:** 生成代码常先调用 `ContainsKey(key)`，随后再读取 `dictionary[key]`。这会做两次查找，而且若另一个线程或回调能在两步之间修改状态，第一次检查也不能保证第二次读取成功。

**修复方法：** 读取使用 `TryGetValue`，插入使用 `TryAdd`，更新则选择语义匹配的单次操作。普通 `Dictionary` 不能因此变成线程安全集合；存在并发写入时还要重新选择同步边界。

### 修改集合中的哈希键

> **陷阱:** 对象进入 `Dictionary` 或 `HashSet` 后，如果参与 `Equals` 或 `GetHashCode` 的字段改变，之后的 `Contains`、读取或删除可能无法定位仍然存在的对象。

**修复方法：** 使用不可变的标量、值对象或记录作为键，并只把稳定身份纳入相等性。必须按可变对象的一个字段索引时，另建以不可变标识为键的字典；身份改变要执行显式移除与重新插入。

### 遍历时修改普通集合

> **陷阱:** 在 `foreach` 中对同一个 `List`、`Dictionary<TKey, TValue>` 或 `HashSet` 做结构修改，通常会使枚举器失效并抛出 `InvalidOperationException`。跳过异常并不能定义哪些元素已经处理。

**修复方法：** 列表过滤使用 `RemoveAll`，或者先收集要删除的键再执行修改。确实需要边遍历边消费时，选择 `Queue`、`Stack` 或明确提供消费枚举的并发结构，而不是依赖普通枚举器的实现细节。

### 把只读接口当成不可变值

> **陷阱:** 返回 `IReadOnlyList` 只限制静态接口。调用方可能持有原列表的另一个引用，提供方也可能继续修改底层列表，所以结果既不一定是快照，也不一定能跨线程稳定读取。

**修复方法：** API 必须说明返回的是实时视图、独立副本还是不可变值。稳定快照可复制到数组或不可变集合；实时视图则要说明谁能修改、变化何时可见以及怎样同步。

### 依赖未承诺的枚举顺序

> **陷阱:** `Dictionary` 与 `HashSet` 的当前实现可能产生看似稳定的顺序，但它们的核心契约不是业务排序。重建集合、换运行时或更换比较器后，测试和序列化结果可能改变。

**修复方法：** 顺序属于输出契约时显式 `OrderBy`，属于存储契约时选择排序集合或另外维护顺序。测试比较集合内容时按集合语义断言，不要偶然比较哈希枚举的文本顺序。

### 把线程安全调用当成原子工作流

> **陷阱:** `ConcurrentDictionary.GetOrAdd` 是线程安全的，但它的值工厂可能并发执行多次；只有其中一个结果进入字典。`if (dict.TryGetValue(...))` 后再执行另一次调用，也不会自动成为一个原子业务操作。

**修复方法：** 值工厂应可重复执行且没有不可撤销副作用。需要“只收费一次”或跨多个键维护不变量时，应使用适合业务边界的锁、事务或专用协调对象，并以竞争测试验证。

<!-- deep -->

## 深入：容量与摊还成本

`List` 将 `Count` 与 `Capacity` 分开。`Count` 是可见元素数，`Capacity` 是无需重新分配即可容纳的元素数。添加元素超过当前容量时，列表会申请更大的连续存储并复制已有元素。

扩容倍率属于运行时实现细节，不能写进业务正确性。稳定的结论是：不扩容的尾部添加通常是 O(1)，扩容那次是 O(n)，一串追加操作按摊还复杂度（amortized complexity）分析。已知近似元素数时，可以在构造函数中传入容量或调用 `EnsureCapacity`，减少复制次数。

容量不是元素，也不会改变 `Count`。预留过大容量会保留更多内存，频繁调用 `TrimExcess` 又可能让下一轮增长重新分配。只有集合进入长期稳定且内存占用已被测量为问题时，才考虑收缩容量。

同样的分析方式也适用于其他可增长结构。Big O 描述输入增长趋势，不提供某台机器上的延迟数字。比较两个都为 O(1) 的操作，或者判断预分配是否值得，仍需在目标运行时和代表性数据上测量。

### 哈希查找的完整契约

哈希表不会仅凭哈希码判定键相等。它先根据哈希码找到候选位置，再调用比较器确认。不同键可以拥有同一哈希码；这叫碰撞，是正常情况，不是比较器可以把相等判断省掉的理由。

相等关系至少要保持自反、对称与传递。更关键的哈希规则是：若 `Equals(x, y)` 为 `true`，则两个值必须返回同一哈希码。反向并不成立，相同哈希码的值仍可以不相等。

比较器属于集合实例。两个 `HashSet<string>` 即使装着相同文本，也可能分别使用 ordinal、忽略大小写或区域性规则。执行集合运算前应确认两边表达同一个身份概念；结果正确性不能建立在调用方猜测默认规则上。

不要把随机或时间相关数据放进 `GetHashCode`，也不要把可变集合本身当作稳定键。若键由多个字段组成，`record`、`record struct` 或不可变元组可以生成一致的值相等性，但仍需审查选中的字段是否真是领域身份。

### 视图、快照与持久化更新

只读包装器把修改成员从公开接口移除，但通常继续引用原集合。它适合所有权仍由提供方掌握、调用方需要观察最新状态的场景。它不是并发同步机制；提供方修改时，调用方正在枚举仍可能失败或看到不适合业务的一组状态。

复制到数组或新列表会建立容器快照。之后增删原集合不会改变这个新容器，但元素引用仍然共享，所以这是浅快照。若元素可变，调用方仍可能通过元素属性观察或制造变化。

不可变集合的更新方法返回新集合，旧版本继续有效。许多不可变类型会在版本之间共享未改变的内部结构，不必把“新集合”理解成逐元素完整复制。进行大量构建操作时使用对应的 `Builder`，完成后再发布不可变结果。

冻结集合面向另一种生命周期：先构建，之后主要查找和枚举。`FrozenDictionary` 与 `FrozenSet` 会在创建阶段为读取布局数据；是否优于普通或不可变集合取决于构建次数、数据规模与读取模式，必须测量。它们也不会让可变元素深度冻结。

### 枚举是一个进行中的读取过程

`foreach` 通过枚举器逐步推进，不会自动复制整个集合。对普通可变集合的结构修改可能让枚举器记录的版本失效，并在之后的 `MoveNext` 抛出异常。异常出现时，循环可能已经处理了前面若干元素。

因此，“捕获异常后继续”不是安全修改策略。先创建明确快照、分两阶段收集修改，或者选择支持消费语义的 API。对列表按索引反向删除可以避免未访问元素左移，但这种技巧只适用于算法确实按索引处理同一个列表的情况。

并发集合允许多个线程安全调用其成员，但枚举语义因类型而异。不要把一次 `foreach` 想象成数据库事务快照。若业务要求一组键和值来自同一个逻辑时刻，需要另外建立快照或同步边界。

惰性 LINQ 查询还会把读取推迟到枚举时。创建查询后修改源集合，结果可能反映新状态，或者在枚举过程中修改时失败。需要冻结查询时点就立即物化到合适的集合，并让方法名或返回类型表达这项选择。

### 并发集合的原子边界

线程安全集合保证文档所述的成员能在并发调用下保持自身结构有效。它们不保证由多个成员调用拼成的业务条件原子化。例如“余额存在、读取余额、扣减、写回”即使每一步都用线程安全字典，整体仍可能丢失更新。

`ConcurrentDictionary<TKey, TValue>` 提供 `TryAdd`、`TryUpdate`、`AddOrUpdate` 与 `GetOrAdd`，用于表达常见的单键条件更新。但接受用户委托的方法会在内部锁之外执行这些委托，因此工厂或更新函数可能被调用多次。最终入库值与某次调用的返回值要按具体 API 契约理解。

值工厂适合纯计算，或者适合可安全重试的构造。如果构造昂贵但无副作用，可以考虑把 `Lazy` 作为字典值，并仔细选择 `LazyThreadSafetyMode` 与失败缓存策略。若操作会付款、发邮件或提交外部事务，就不应把“工厂被调用”当成唯一执行凭证。

跨键不变量、读改写序列和外部副作用通常需要集合之外的协调。锁可以保护进程内临界区，数据库事务可以保护持久状态，消息系统则可能要求幂等键。集合只解决它声明的问题，不能替代业务事务设计。

<!-- /deep -->

[检查点: csharp/collections](https://codewiki.com/zh/csharp/collections/#checkpoint)

## 延伸阅读

- [C# 集合参考](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/collections)
- [.NET 集合与数据结构](https://learn.microsoft.com/en-us/dotnet/standard/collections/)
- [`Dictionary<TKey, TValue>` API](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2?view=net-10.0)
- [`HashSet` API](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1?view=net-10.0)
- [.NET 线程安全集合](https://learn.microsoft.com/en-us/dotnet/standard/collections/thread-safe/)
- [`System.Collections.Immutable` 命名空间](https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable?view=net-10.0)