---
title: CSharp-03-集合与LINQ
aliases:
  - C# 集合
  - CSharp LINQ
  - 语言集成查询
tags:
  - 编程语言/CSharp
  - 类型/教程
created: 2026-10-11
updated: 2026-10-11
level: 进阶
prerequisites:
  - "[[CSharp-01-环境与基础语法]]"
  - "[[CSharp-02-面向对象]]"
sources:
  - https://learn.microsoft.com/en-us/dotnet/standard/collections/commonly-used-collection-types
  - https://learn.microsoft.com/en-us/dotnet/standard/collections/selecting-a-collection-class
  - https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/generics/constraints-on-type-parameters
  - https://learn.microsoft.com/en-us/dotnet/csharp/iterators
  - https://learn.microsoft.com/en-us/dotnet/csharp/linq/
  - https://learn.microsoft.com/en-us/dotnet/standard/linq/deferred-execution-lazy-evaluation
---

# CSharp-03-集合与LINQ

> [!abstract] 这篇讲什么
> 集合决定程序的**数据组织方式**，LINQ（Language Integrated Query，语言集成查询）决定程序的**数据处理方式**。本篇先讲泛型为什么值得（类型安全、零装箱、约束表达意图），再给出集合接口层次与常用集合的复杂度对照表、`List<T>` 扩容机制的性能含义、`Dictionary` 的哈希与相等性契约；然后完整过一遍 LINQ：两套语法、操作符分类、**延迟执行（Deferred Execution）** 这个最容易出错的核心概念、`IEnumerable` 与 `IQueryable` 的分界、性能注意事项、自定义 `IComparer<T>` 与 `IEqualityComparer<T>`。
> 阅读前提：[[CSharp-01-环境与基础语法]]（泛型基础、装箱、`foreach` 原理）、[[CSharp-02-面向对象]]（接口、`Equals`/`GetHashCode`）。示例以 **.NET SDK 10.0.401 / C# 13** 为基准。

---

## 一、是什么：从非泛型集合到泛型 + LINQ

没有泛型时，集合只能存 `object`：

```csharp
// 老写法（.NET 1.x 风格）：ArrayList 的元素类型是 object
var legacy = new System.Collections.ArrayList();
legacy.Add(1);
legacy.Add("two");          // 编译通过 —— 类型错误被推迟到运行期
int n = (int)legacy[0];     // 拆箱
// int bad = (int)legacy[1];  // 运行期 InvalidCastException
```

泛型把类型参数化，让容器知道自己在装什么：

```csharp
// 现代写法：List<T> 的元素类型在编译期确定
var modern = new List<int> { 1, 2 };
// modern.Add("two");        // 编译错误 —— 错误在写代码时就被拦住
int m = modern[0];           // 无装箱、无拆箱、无强转
```

LINQ 建立在这套泛型接口之上，把"筛选、投影、分组、连接、聚合"变成类型安全的查询语法，既能作用于内存集合，也能被 EF Core 翻译成 SQL（见 [[后端-05-数据库操作与ORM]]）。

---

## 二、为什么这样设计

### 2.1 泛型的三大价值

| 价值 | 没有泛型 | 有泛型 |
|---|---|---|
| 类型安全 | `ArrayList` 里能塞任何类型，错误在运行期爆炸 | 编译期检查，`List<int>` 只能装 `int` |
| 性能 | 值类型进出都要装箱/拆箱 + 堆分配 | 运行时为每个值类型生成**专用代码**，无装箱 |
| 代码复用 | 为每种类型写一份，或用 `object` 牺牲类型 | 一份代码服务所有类型，且不牺牲类型 |
| 表达意图 | 签名里看不出约束 | `where T : IComparable<T>` 直接写在类型上 |

**泛型在 .NET 里为什么快？** 与 Java 的类型擦除不同，.NET 的泛型是**运行时具体化**的（reified generics）：

- 引用类型实参（如 `List<string>`）**共享**同一份 JIT 代码（引用大小相同，都是指针）。
- 值类型实参（如 `List<int>`）会为 `int` 生成**专属的本机代码**，字段直接是 `int`，索引器直接返回 `int` —— 全程无装箱、无类型检查。
- 编译后的 IL 里保留泛型信息，所以反射能看到真实的类型参数（`typeof(List<int>).GetGenericArguments()`）。

> [!note] 代价是什么
> 值类型的泛型实例化会增加 JIT 编译时间与代码体积（每个值类型一份代码）。这是为了消除装箱而付出的合理代价——实测中收益远大于成本。

### 2.2 为什么需要 `where` 约束

约束让泛型方法**能对 `T` 做某些操作**。没有约束时 `T` 只能当作 `object`（只有 `ToString`/`Equals`/`GetHashCode` 等）。

```csharp
// 没有约束：编译器不知道 T 支持比较，写 value > 0 会报错
// static T Max<T>(T a, T b) => a.CompareTo(b) > 0 ? a : b;   // 编译错误

// 有约束：明确告诉编译器"T 可比较"，于是可以调用 CompareTo
static T Max<T>(T a, T b) where T : IComparable<T> =>
    a.CompareTo(b) >= 0 ? a : b;

Console.WriteLine(Max(3, 7));              // 7
Console.WriteLine(Max("abc", "abd"));      // abd
```

| 约束 | 语法 | 含义 | 关键用途 |
|---|---|---|---|
| 引用类型 | `where T : class` | `T` 必须是引用类型 | 可与 `null` 比较 |
| 值类型 | `where T : struct` | `T` 必须是值类型（不含可空） | 避免装箱、可用 `default(T)` 语义 |
| 非空 | `where T : notnull` | 不能为 `null`（可空上下文） | 字典键、避免空引用警告 |
| 基类 | `where T : Base` | `T` 派生自 `Base` | 访问 `Base` 的成员 |
| 接口 | `where T : IComparable<T>` | `T` 实现该接口 | 调用接口成员 |
| 无参构造 | `where T : new()` | 有公开无参构造 | `new T()` |
| 自引用 | `where T : IComparable<T>` | F-bounded，类型与自己比较 | 通用比较算法 |
| 非空基类 | `where T : Base, new()` | 多个约束用逗号（`class`/`struct`/`notnull`/`unmanaged` 必须放最前） | — |
| 类型参数组合 | `where T : U` | `T` 派生自另一个类型参数 `U` | 泛型继承体系 |
| 枚举 | `where T : struct, Enum` | C# 7.3+ | 泛型枚举工具 |
| 委托 | `where T : Delegate` | C# 7.3+ | 泛型事件工具 |

```csharp
// 组合约束：既能 new，又能比较，还必须是非空引用类型
public static T PickLarger<T>(T? a, T b) where T : class, IComparable<T>, new()
{
    a ??= new T();
    return a.CompareTo(b) >= 0 ? a : b;
}

// 多个类型参数分别约束：注意 where 子句可以分行
public static Dictionary<TKey, TValue> BuildMap<TKey, TValue>(
    IEnumerable<KeyValuePair<TKey, TValue>> pairs)
    where TKey : notnull
{
    var map = new Dictionary<TKey, TValue>();
    foreach (var kv in pairs) map[kv.Key] = kv.Value;
    return map;
}
```

> [!warning] 约束的三条易错规则
> 1. **`new()` 必须写在所有约束的最后**（`where T : Base, IComparable<T>, new()`）。
> 2. **`class` / `struct` / `notnull` / `unmanaged` 这类"种类约束"必须写在最前**，且互斥（不能同时 `class` 和 `struct`）。
> 3. **约束会限制调用方**：给公共 API 加约束是破坏性变更（原来能传的类型可能不再满足）。

---

## 三、核心内容

### 3.1 集合接口层次

```
IEnumerable<T>                ← 只读、只能向前遍历（foreach 的最低要求）
    └── ICollection<T>        ← 增删、Count、Contains、CopyTo
            ├── IList<T>      ← 索引访问、Insert/RemoveAt、有序
            │      └── List<T>
            ├── ISet<T>       ← 集合运算（Union/Intersect/Except 的原地版本）
            │      └── HashSet<T>、SortedSet<T>
            └── IDictionary<TKey,TValue>  ← 键值对、索引器 by key、Keys/Values
                   └── Dictionary<TKey,TValue>

接口的只读孪生兄弟：
IReadOnlyCollection<T>  ← Count
IReadOnlyList<T>        ← 索引访问（返回视图，调用方无法 Add/Remove）
IReadOnlyDictionary<TKey,TValue>

非泛型遗留体系（仅用于互操作）：IEnumerable → ICollection → IList / IDictionary
```

| 接口 | 关键成员 | 什么时候用它当参数/返回类型 |
|---|---|---|
| `IEnumerable<T>` | `GetEnumerator()` | 只需遍历（最高兼容性，也最"晚绑定") |
| `ICollection<T>` | `Add`/`Remove`/`Clear`/`Count`/`Contains` | 需要数量和增删，但不关心顺序与索引 |
| `IList<T>` | `this[int]`/`Insert`/`IndexOf`/`RemoveAt` | 需要按下标访问 |
| `IReadOnlyList<T>` | `this[int]`/`Count` | **对外暴露集合的首选**：可索引但不可改 |
| `IReadOnlyCollection<T>` | `Count` | 只需暴露数量 |
| `IReadOnlyDictionary<K,V>` | `this[K]`/`Keys`/`Values`/`TryGetValue` | 对外暴露只读字典 |
| `IDictionary<K,V>` | 上述可写版本 | 需要修改字典 |
| `ISet<T>` | `Add` 返回 `bool`、`UnionWith`/`IntersectWith` | 需要集合语义（去重 + 集合运算） |

> [!important] 参数尽量宽、返回尽量窄
> - **参数**用最宽的能满足需求的接口：只遍历就用 `IEnumerable<T>`，需要 `Count` 用 `IReadOnlyCollection<T>`。
> - **返回值**用最窄的接口：返回 `IReadOnlyList<T>` 而不是 `List<T>`，避免调用方绕过你的封装修改内部状态（[[CSharp-02-面向对象]] 的封装原则）。
> - `IReadOnlyList<T>` 是**视图**不是快照：如果内部列表变了，外面看到的也变。要真快照就返回 `list.ToArray()` 或 `AsReadOnly()`。

### 3.2 常用集合对比

设 $n$ 为元素个数，均摊复杂度标注为「均摊」。

| 集合 | 底层结构 | 索引 | 查找 | 插入/删除 | 有序 | 适用场景 |
|---|---|---|---|---|---|---|
| `T[]` | 连续内存 | $O(1)$ | $O(n)$ | 定长，不可增删 | 否 | 定长、热点路径、需要 `Span<T>` |
| `List<T>` | 可扩容数组 | $O(1)$ | $O(n)$ | 尾部 $O(1)$ 均摊；中间 $O(n)$ | 否 | **默认选择**，绝大多数场景 |
| `Dictionary<K,V>` | 哈希桶 + 条目数组 | — | $O(1)$ 均摊 | $O(1)$ 均摊 | 否 | 按键快速查找/去重，键无序 |
| `HashSet<T>` | 哈希桶 | — | $O(1)$ 均摊 | $O(1)$ 均摊 | 否 | 去重、集合运算、存在性判断 |
| `Queue<T>` | 环形数组 | — | $O(n)$ | 入队/出队 $O(1)$ 均摊 | FIFO | 任务队列、BFS |
| `Stack<T>` | 数组 | — | $O(n)$ | 压栈/弹栈 $O(1)$ 均摊 | LIFO | 撤销栈、DFS、括号匹配 |
| `LinkedList<T>` | 双向链表 | — | $O(n)$ | **已知节点处** $O(1)$ | 否 | 频繁在中间增删（有节点引用时） |
| `SortedDictionary<K,V>` | 红黑树 | — | $O(\log n)$ | $O(\log n)$ | 按键排序 | 需要有序遍历 + 按范围查询 |
| `SortedSet<T>` | 红黑树 | — | $O(\log n)$ | $O(\log n)$ | 排序 | 有序去重、范围查询 |
| `SortedList<K,V>` | 两个数组（键/值） | $O(1)$ 按索引 | $O(\log n)$ 二分 | $O(n)$ | 按键排序 | 读多写少、内存紧凑 |
| `PriorityQueue<T,P>` | 数组二叉堆 | — | `Peek` $O(1)$ | 入队/出队 $O(\log n)$ | 按优先级 | 任务调度、Dijkstra、Top-K |
| `ConcurrentDictionary<K,V>` | 分段锁哈希 | — | $O(1)$ 均摊 | $O(1)$ 均摊 | 否 | 多线程读写 |
| `ImmutableList<T>` 等 | 持久化数据结构 | $O(\log n)$ | $O(\log n)$ | 返回新实例 $O(\log n)$ | 否 | 需要不可变快照（`System.Collections.Immutable` 包） |

> [!tip] 选择决策树
> 1. 只是按顺序存一堆东西 → `List<T>`。
> 2. 需要"按某个键快速找到值" → `Dictionary<K,V>`。
> 3. 只需要"这个东西在不在里面" → `HashSet<T>`。
> 4. 先进先出 → `Queue<T>`；后进先出 → `Stack<T>`。
> 5. 需要始终有序 → `SortedSet<T>`/`SortedDictionary<K,V>`（要"按插入顺序"用 `List<T>` 或 `OrderedDictionary`）。
> 6. 每次取最小/最大 → `PriorityQueue<T,P>`。
> 7. 多线程共享可变集合 → 优先考虑"不可变对象 + 每次替换"，其次才是 `Concurrent*` 集合。
> 8. **不要为了"省一次查找"而提前选复杂结构**：先用 `List<T>` + LINQ，profiling 显示瓶颈再换。

### 3.3 `List<T>` 的扩容机制与容量预设

`List<T>` 内部是一个 `T[] _items` 加一个 `int _size`。当 `_size == _items.Length` 时，`Add` 会：

1. 分配一个新数组，容量为原来的 **2 倍**（默认初始容量 4，从 0 开始的第一次 `Add` 会分配 4）；
2. 用 `Array.Copy` 把旧元素复制过去；
3. 替换 `_items`，旧的数组交给 GC。

代价分析：设最终元素数为 $n$，第 $k$ 次扩容复制 $2^{k-1}$ 个元素，总复制量为

$$
\sum_{k=1}^{\lceil \log_2 n \rceil} 2^{\,k-1} \;<\; 2n \;=\; O(n)
$$

所以**单次 `Add` 的最坏代价是 $O(n)$，但均摊代价是 $O(1)$**（这就是"均摊"的来历）。同时也说明：扩容不仅是时间成本，还有**峰值内存**（新旧数组同时存在，瞬时占用约 1.5 倍）。

```csharp
using System.Diagnostics;

// 场景一：不知道元素个数，靠自动扩容
var sw = Stopwatch.StartNew();
var a = new List<int>();
for (int i = 0; i < 1_000_000; i++) a.Add(i);
sw.Stop();
Console.WriteLine($"自动扩容：{sw.ElapsedMilliseconds} ms，Capacity={a.Capacity}");

// 场景二：已知（或能估算）元素个数，预设容量 —— 一次分配，零复制
sw.Restart();
var b = new List<int>(capacity: 1_000_000);
for (int i = 0; i < 1_000_000; i++) b.Add(i);
sw.Stop();
Console.WriteLine($"预设容量：{sw.ElapsedMilliseconds} ms，Capacity={b.Capacity}");

// 从集合构造时，容量会自动设为源的元素个数（内部走 ICollection<T>.Count 快路径）
var c = new List<int>(Enumerable.Range(0, 1_000_000));
Console.WriteLine($"从 IEnumerable：Capacity={c.Capacity}");
```

| 成员 | 语义 | 复杂度 | 备注 |
|---|---|---|---|
| `Add(item)` | 尾部追加 | 均摊 $O(1)$ | 触发扩容时单次 $O(n)$ |
| `Insert(i, item)` | 在位置 `i` 插入 | $O(n)$ | 需要把后面所有元素后移 |
| `RemoveAt(i)` | 删除位置 `i` | $O(n)$ | 后面元素前移；删尾部是 $O(1)$ |
| `Remove(item)` | 按值删除第一个匹配 | $O(n)$ | 用 `EqualityComparer<T>.Default` 比较 |
| `RemoveAll(pred)` | 删除全部匹配 | $O(n)$ | 一次遍历完成，比循环 `Remove` 快得多 |
| `Contains(item)` | 是否存在 | $O(n)$ | 频繁调用说明该换 `HashSet<T>` |
| `IndexOf(item)` | 首次出现的下标 | $O(n)$ | 找不到返回 `-1` |
| `this[i]` | 索引访问 | $O(1)$ | 越界抛 `ArgumentOutOfRangeException` |
| `BinarySearch(item)` | 二分查找 | $O(\log n)$ | **要求列表已排序**，否则结果未定义 |
| `Capacity` | 当前底层数组长度 | $O(1)$ | 设小会立刻复制；设 0 表示清空 |
| `TrimExcess()` | 收缩容量到实际大小 | $O(n)$ | 适合"构建完成后长期只读"的列表 |
| `Sort()` | 原地排序 | $O(n \log n)$ | 不稳定排序（内部 introsort） |
| `AsReadOnly()` | 返回只读包装 | $O(1)$ | 是**视图**，原列表变化会反映出来 |

```csharp
var list = new List<int> { 5, 3, 1, 4, 3 };

// RemoveAll 一次遍历删掉所有匹配：比 for + RemoveAt 快（无重复移动）
int removed = list.RemoveAll(x => x == 3);
Console.WriteLine($"删除 {removed} 个，剩余 {string.Join(",", list)}");   // 2 个，剩余 5,1,4

list.Sort();                                   // 1,4,5
Console.WriteLine(list.BinarySearch(4));       // 1（必须在排序后调用）

// 构建完成后收缩容量，降低长期内存占用
list.TrimExcess();
Console.WriteLine($"Capacity={list.Capacity}, Count={list.Count}");

// 只读视图：不复制数据，但外部改不了
var view = list.AsReadOnly();
list.Add(9);                                   // 视图会同步反映
Console.WriteLine($"视图长度 {view.Count}");    // 4
// view.Add(1);                                // 编译错误：IReadOnlyList 没有 Add
```

> [!warning] `List<T>` 的性能陷阱
> 1. **在循环里 `Remove(item)`**：每次 $O(n)$，整体 $O(n^2)$。改用 `RemoveAll` 或**倒序 `RemoveAt`**。
> 2. **在循环里 `Insert(0, item)`**：每次 $O(n)$。改为 `Add` 后 `Reverse()`，或直接用 `LinkedList<T>`/`Queue<T>`。
> 3. **`foreach` 中修改集合**：抛 `InvalidOperationException`（[[CSharp-01-环境与基础语法]] 3.11 讲了原理）。
> 4. **频繁 `Contains` 的 `List<T>`**：`O(n)` 的线性查找。元素规模上几千就该换 `HashSet<T>`。
> 5. **`List<T>` 不保证排序稳定**：要稳定排序用 `OrderBy`（LINQ 的 `OrderBy` 是稳定排序）。

### 3.4 `Dictionary` 的哈希与相等性契约

`Dictionary<TKey,TValue>` 的工作流程：

1. 计算 `key.GetHashCode()`，经哈希函数映射到桶（bucket）下标；
2. 桶里可能已有其他条目（**哈希冲突**），于是用 `EqualityComparer<TKey>.Default.Equals` 逐个比较；
3. 相同 → 命中；都不同 → 追加到桶的链上（.NET 的实现用"桶数组 + 条目数组 + 下一个条目索引"的链式结构）。

**因此键类型必须同时正确实现 `Equals` 与 `GetHashCode`**（[[CSharp-02-面向对象]] 3.15 讲了为什么）：

| 契约 | 违反后果 |
|---|---|
| `Equals` 为真 → `GetHashCode` 必须相同 | 相等的键落在不同桶 → 查不到、重复插入 |
| `GetHashCode` 在对象生命周期内不变 | 键"消失"，且旧条目永远无法被访问（幽灵条目） |
| `Equals` 自反/对称/传递 | 容器行为不可预测 |

```csharp
// 正确示范：不可变键 + 同时重写 Equals/GetHashCode + 实现 IEquatable<T>
public sealed class SkuCode : IEquatable<SkuCode>
{
    public string Code { get; }                     // 只读：保证哈希码稳定
    public SkuCode(string code) => Code = code;

    public bool Equals(SkuCode? other) =>
        other is not null && string.Equals(Code, other.Code, StringComparison.Ordinal);

    public override bool Equals(object? obj) => Equals(obj as SkuCode);

    // 用 ordinal 比较语义与 Equals 保持一致（区域性敏感的比较会与 Equals 冲突）
    public override int GetHashCode() => StringComparer.Ordinal.GetHashCode(Code);
    public override string ToString() => Code;
}

var stock = new Dictionary<SkuCode, int>
{
    [new SkuCode("A-1")] = 10,
    [new SkuCode("A-2")] = 5,
};

// 用"新的但相等的"键查询：哈希码相同 → 同桶 → Equals 命中
Console.WriteLine(stock[new SkuCode("A-1")]);                    // 10
Console.WriteLine(stock.TryGetValue(new SkuCode("A-9"), out int v));  // False, v = 0

// 现代 API：GetValueOrDefault / TryAdd / 索引器 ??= 累加
stock[new SkuCode("A-1")] = stock.GetValueOrDefault(new SkuCode("A-1")) + 1;  // 11
// 更地道的累加写法（.NET Core 2+ 的 CollectionsMarshal 之外，这是最清晰的）
stock[new SkuCode("A-1")] = stock[new SkuCode("A-1")] + 1;                    // 12

// 直接用元组作键：ValueTuple 已经正确实现了 Equals/GetHashCode
var grid = new Dictionary<(int Row, int Col), string> { [(0, 0)] = "起点", [(2, 3)] = "终点" };
Console.WriteLine(grid[(2, 3)]);                                  // 终点
```

`Dictionary` 常用成员与复杂度：

| 成员 | 复杂度 | 说明 |
|---|---|---|
| `this[key]` | $O(1)$ 均摊 | 读：不存在抛 `KeyNotFoundException`；写：不存在则新增 |
| `TryGetValue(key, out v)` | $O(1)$ 均摊 | **读取的首选**：一次查找同时完成"判存在 + 取值" |
| `GetValueOrDefault(key)` | $O(1)$ 均摊 | 不存在返回 `default(TValue)` |
| `ContainsKey(key)` | $O(1)$ 均摊 | 只判存在；若之后还要取值得用 `TryGetValue` 避免两次查找 |
| `Add(key, v)` | $O(1)$ 均摊 | 键已存在抛 `ArgumentException`（`TryAdd` 返回 `false`） |
| `TryAdd(key, v)` | $O(1)$ 均摊 | 键已存在返回 `false`，不抛异常 |
| `Remove(key)` | $O(1)$ 均摊 | 返回 `bool` |
| `ContainsValue(v)` | $O(n)$ | **遍历所有值**，热路径上要避免 |
| 遍历 `foreach` | $O(n)$ | 顺序在 .NET Core 3.0+ 是**插入顺序**，但这是实现细节，不要依赖 |
| `EnsureCapacity(n)` | $O(n)$ | 预设容量，避免多次扩容（同 `List<T>` 的逻辑） |

> [!warning] 哈希容器的常见错误
> 1. **可变对象作键**：改字段 → 哈希码变 → 查不到（见 [[CSharp-02-面向对象]] 的 `> [!danger]`）。
> 2. **重写 `Equals` 忘了 `GetHashCode`**：`ContainsKey` 静默返回 `false`。
> 3. **用 `double`/`decimal` 作键**：`0.1 + 0.2` 与 `0.3` 不是同一个值（浮点误差）。用 `decimal` 或先规范化。
> 4. **`Dictionary` 默认区分大小写**：字符串键要不区分大小写，必须显式传比较器：
>    `new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase)`。
> 5. **`Keys`/`Values` 是活视图**：遍历时增删会抛异常；需要快照就 `.ToArray()`。
> 6. **指望 `Dictionary` 排序**：它不是有序容器，要排序用 `SortedDictionary` 或在遍历前 `OrderBy`。

### 3.5 迭代器与 `yield return`

迭代器（Iterator）让编译器替你生成 `IEnumerator<T>` 实现：一个 `yield return` 的方法被编译成一个状态机，每次 `MoveNext()` 恢复执行到下一个 `yield`。

```csharp
// 手动实现枚举器：需要维护状态、实现 IEnumerator<T>、处理 Dispose —— 冗长易错
public sealed class ManualCounter : IEnumerable<int>
{
    private readonly int _max;
    public ManualCounter(int max) => _max = max;

    public IEnumerator<int> GetEnumerator()
    {
        for (int i = 0; i < _max; i++)
            yield return i;               // 编译器生成状态机，无需手写 MoveNext/Current
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
}

// 更有价值的用法：惰性、可组合、按需计算的序列
public static IEnumerable<int> Fibonacci()
{
    int a = 0, b = 1;
    while (true)                          // 无限序列也是合法的
    {
        yield return a;
        (a, b) = (b, a + b);
    }
}

// 只取前 8 个：无限序列 + Take 是安全的，因为求值是"按需拉取"
Console.WriteLine(string.Join(", ", Fibonacci().Take(8)));   // 0, 1, 1, 2, 3, 5, 8, 13

// 惰性读取大文件：不会把整个文件读进内存
static IEnumerable<string> ReadLines(string path)
{
    using var reader = new StreamReader(path);
    string? line;
    while ((line = reader.ReadLine()) is not null)
        yield return line;                // 每被请求一行才读一行
}
// foreach (var line in ReadLines("huge.log").Take(10)) Console.WriteLine(line);
```

| 特性 | 说明 |
|---|---|
| 调用时不执行 | `Fibonacci()` 只创建状态机，**不进入方法体**（延迟执行的核心机制） |
| 状态跨 `yield` 保留 | 局部变量存活在堆上的状态机对象里 |
| `yield break` | 提前结束序列 |
| 自动 `Dispose` | `foreach` 结束时会调用迭代器的 `Dispose`，`using` 里的资源因此被释放 |
| 不能有 `out`/`ref` 参数 | 迭代器方法的签名受限 |
| 不能 `yield return` 于 `try-catch` 块 | 可以有 `try-finally`（用于释放） |
| `[EnumeratorCancellation]` | 与 `async IAsyncEnumerable<T>` 配合支持取消（见 [[CSharp-05-异步编程]]） |

> [!important] 迭代器的"每调用一份状态"
> 每次调用 `Fibonacci()` 都得到**新的**状态机实例，所以多个 `foreach` 互不干扰。这也意味着：**同一份迭代器对象不能被并发枚举**——`IEnumerator<T>` 是有状态的、非线程安全的。

### 3.6 LINQ 的两套语法

| 维度 | 查询语法（Query Syntax） | 方法语法（Method Syntax） |
|---|---|---|
| 外观 | `from x in src where ... select ...` | `src.Where(...).Select(...)` |
| 编译结果 | 完全等价于方法调用（编译器翻译） | 就是方法调用 |
| 可读性 | 多子句的连接、分组更像 SQL，一眼看懂 | 单步操作、链式管道更简洁 |
| 覆盖面 | 只覆盖一部分操作符（无 `Chunk`、`Distinct` 等） | **全部**操作符 |
| 混合 | `(from x in src select x).Where(...)` 可混用 | 同左 |

```csharp
var employees = new[]
{
    new { Name = "阿伟", Dept = "研发", Salary = 18000 },
    new { Name = "小美", Dept = "研发", Salary = 22000 },
    new { Name = "老张", Dept = "销售", Salary = 15000 },
    new { Name = "小林", Dept = "销售", Salary = 16000 },
};

// 方法语法
var q1 = employees
    .Where(e => e.Salary > 15000)
    .OrderByDescending(e => e.Salary)
    .Select(e => $"{e.Name}({e.Dept})");

// 查询语法：同样的结果，多子句时更像 SQL
var q2 =
    from e in employees
    where e.Salary > 15000
    orderby e.Salary descending
    select $"{e.Name}({e.Dept})";

Console.WriteLine(string.Join(" | ", q1));
Console.WriteLine(string.Join(" | ", q2));   // 输出完全相同

// 分组：查询语法优势明显
var byDept =
    from e in employees
    group e by e.Dept into g
    select new { Dept = g.Key, Count = g.Count(), Avg = g.Average(x => x.Salary) };

foreach (var g in byDept)
    Console.WriteLine($"{g.Dept}: {g.Count} 人，平均 {g.Avg:F0}");
```

### 3.7 常用操作符分类

| 分类 | 操作符 | 作用 | 延迟执行 |
|---|---|---|---|
| 筛选 | `Where`、`OfType<T>` | 按谓词/类型过滤 | 是 |
| 投影 | `Select`、`SelectMany` | 一对一 / 一对多展开 | 是 |
| 排序 | `OrderBy`、`OrderByDescending`、`ThenBy`、`ThenByDescending`、`Reverse` | 排序（`OrderBy` 稳定） | 是（首次枚举时排序） |
| 分组 | `GroupBy`、`ToLookup` | 分组；`ToLookup` 立即执行 | `GroupBy` 延迟，`ToLookup` 立即 |
| 聚合 | `Count`、`Sum`、`Min`、`Max`、`Average`、`Aggregate` | 归约为单值 | **否（立即执行）** |
| 连接 | `Join`、`GroupJoin`、`Zip` | 内连接 / 分组连接 / 位置配对 | 是 |
| 量词 | `Any`、`All`、`Contains` | 存在性判断（短路）；`Contains(x)` 是"是否含元素 x"，不是"是否有满足条件的元素" | **否** |
| 元素 | `First`、`FirstOrDefault`、`Single`、`SingleOrDefault`、`Last`、`ElementAt` | 取个别元素 | **否** |
| 集合 | `Distinct`、`Union`、`Intersect`、`Except` | 集合运算（去重语义） | 是 |
| 分区 | `Take`、`Skip`、`TakeWhile`、`SkipWhile`、`Chunk` | 切片 | 是 |
| 生成 | `Range`、`Repeat`、`Empty` | 造序列 | 是 |
| 转换 | `ToList`、`ToArray`、`ToDictionary`、`ToHashSet`、`AsEnumerable` | **物化**为具体集合 | **否（立即执行）** |
| 相等 | `SequenceEqual` | 逐元素比较 | **否** |

#### 元素操作符：抛异常的条件是重点

| 操作符 | 序列为空 | 有多个匹配 | 无匹配 | 备注 |
|---|---|---|---|---|
| `First()` | 抛 `InvalidOperationException` | 返回第一个 | 抛 `InvalidOperationException` | |
| `First(pred)` | 抛 `InvalidOperationException` | 返回第一个匹配 | 抛 `InvalidOperationException` | |
| `FirstOrDefault()` | 返回 `default(T)` | 返回第一个 | 返回 `default(T)` | .NET 6+ 可传自定义默认值 |
| `Single()` | 抛 `InvalidOperationException` | **抛 `InvalidOperationException`** | 抛 `InvalidOperationException` | 语义是"有且仅有一个" |
| `SingleOrDefault()` | 返回 `default(T)` | **抛 `InvalidOperationException`** | 返回 `default(T)` | 空序列是合法的"零个" |
| `Last()` / `LastOrDefault()` | 同 `First` / `FirstOrDefault` | — | — | 无索引器时是 $O(n)$ |
| `ElementAt(i)` | 抛 `ArgumentOutOfRangeException` | — | — | 有索引器时 $O(1)$，否则 $O(n)$ |
| `ElementAtOrDefault(i)` | 返回 `default(T)` | — | — | 不抛越界异常 |

```csharp
var nums = new[] { 1, 2, 3, 4, 5 };
var empty = Array.Empty<int>();
var dup = new[] { 7, 7 };

// First：空序列抛异常 —— 适合"空就是 bug"的场景
try { Console.WriteLine(empty.First()); }
catch (InvalidOperationException ex) { Console.WriteLine($"First: {ex.Message}"); }

// FirstOrDefault：空序列给默认值 —— 适合"空是正常情况"
Console.WriteLine(empty.FirstOrDefault());                       // 0
Console.WriteLine(nums.FirstOrDefault(n => n > 100, -1));        // -1（.NET 6+ 支持自定义默认值）

// Single：用于"业务上唯一"的场景，重复数据立刻暴露
try { Console.WriteLine(dup.Single()); }
catch (InvalidOperationException) { Console.WriteLine("数据重复，违反唯一性假设"); }

// SingleOrDefault：空 OK，重复仍抛 —— 分清"零个合法"与"唯一"
Console.WriteLine(empty.SingleOrDefault());                     // 0
try { dup.SingleOrDefault(); }
catch (InvalidOperationException) { Console.WriteLine("SingleOrDefault 也不容忍重复"); }

// 现代判空替代：Any() 比 Count() > 0 更省（不必遍历完）
Console.WriteLine(nums.Any(n => n > 4));                        // True（短路）
Console.WriteLine(nums.All(n => n > 0));                        // True
```

> [!tip] 怎么选 `First` 还是 `Single`
> 问自己一个问题：**"多条匹配"是数据错误吗？**
> - 是（例如按业务主键查、按用户名查唯一值）→ 用 `Single`/`SingleOrDefault`，让重复数据**尽早炸出来**。
> - 不是（例如"取最近一条日志"、"取任意一个可用节点"）→ 用 `First`/`FirstOrDefault`，并**显式排序**消除不确定性：`logs.OrderByDescending(l => l.Time).First()`。

#### 分组、连接、聚合

```csharp
var orders = new[]
{
    new { Id = 1, CustomerId = "C1", Amount = 120m },
    new { Id = 2, CustomerId = "C2", Amount = 80m },
    new { Id = 3, CustomerId = "C1", Amount = 200m },
};
var customers = new[]
{
    new { Id = "C1", Name = "阿伟" },
    new { Id = "C2", Name = "小美" },
    new { Id = "C3", Name = "老张" },   // 没有订单，用来验证 GroupJoin
};

// GroupBy：等值分组，Key 是分组依据
var byCustomer = orders
    .GroupBy(o => o.CustomerId)
    .Select(g => new { g.Key, Count = g.Count(), Total = g.Sum(o => o.Amount) });

foreach (var g in byCustomer)
    Console.WriteLine($"{g.Key}: {g.Count} 单，合计 {g.Total}");

// ToLookup：与 GroupBy 类似，但立即执行，且重复查询不会重新分组
var lookup = orders.ToLookup(o => o.CustomerId);
Console.WriteLine(lookup["C1"].Count());          // 2
Console.WriteLine(lookup["CX"].Count());          // 0（不存在的键返回空序列，不抛异常）

// Join：内连接，只保留两边都有的
var inner = customers.Join(
    orders,
    c => c.Id,                                    // 左键
    o => o.CustomerId,                            // 右键
    (c, o) => $"{c.Name} 下单 {o.Amount}");

foreach (var line in inner) Console.WriteLine(line);

// GroupJoin：左外连接（保留没有订单的客户）
var leftOuter = customers.GroupJoin(
    orders,
    c => c.Id,
    o => o.CustomerId,
    (c, os) => new { c.Name, Count = os.Count(), Total = os.Sum(o => o.Amount) });

foreach (var x in leftOuter)
    Console.WriteLine($"{x.Name}: {x.Count} 单 / {x.Total}");

// Aggregate：没有专用操作符时的万能归约
decimal total = orders.Aggregate(0m, (acc, o) => acc + o.Amount);              // 求和
string csv = orders.Aggregate("", (acc, o) => acc.Length == 0 ? $"{o.Id}" : $"{acc},{o.Id}");
Console.WriteLine($"合计 {total}，订单号 {csv}");
```

| 连接方式 | LINQ 写法 | 语义 |
|---|---|---|
| 内连接 | `Join` | 两边都有才输出 |
| 左外连接 | `GroupJoin` + `SelectMany(..., (c, os) => os.DefaultIfEmpty())` | 保留左表全部 |
| 交叉连接 | `from a in A from b in B select ...` | 笛卡尔积（$|A|\times|B|$） |
| 按位置配对 | `Zip` | `a[i]` 配 `b[i]`，取较短长度 |

#### 集合运算与分区

```csharp
int[] a = [1, 2, 2, 3, 4];
int[] b = [3, 4, 5];

// Distinct：按默认相等比较去重（引用类型要看是否重写了 Equals/GetHashCode）
Console.WriteLine(string.Join(",", a.Distinct()));                 // 1,2,3,4

// Union：并集并去重
Console.WriteLine(string.Join(",", a.Union(b)));                   // 1,2,3,4,5
// Intersect：交集
Console.WriteLine(string.Join(",", a.Intersect(b)));               // 3,4
// Except：差集（在 a 不在 b）
Console.WriteLine(string.Join(",", a.Except(b)));                  // 1,2

// 分区：分页的标准写法
var page2 = a.Skip(2).Take(2);
Console.WriteLine(string.Join(",", page2));                        // 2,3

// 按条件分区：注意 TakeWhile 在遇到第一个不满足的元素时就停止
Console.WriteLine(string.Join(",", a.TakeWhile(x => x < 3)));      // 1,2,2
Console.WriteLine(string.Join(",", a.SkipWhile(x => x < 3)));      // 3,4

// Chunk（.NET 6+）：把序列切成固定大小的块，最后一块可能更短
foreach (int[] chunk in Enumerable.Range(1, 7).Chunk(3))
    Console.WriteLine($"[{string.Join(",", chunk)}]");             // [1,2,3] [4,5,6] [7]
```

> [!warning] `TakeWhile`/`SkipWhile` 不是 `Where`
> `Where(x => x < 3)` 会检查**每个**元素；`TakeWhile(x => x < 3)` 遇到第一个不满足的就**整体停止**。在乱序数据上两者结果可能天差地别。

### 3.8 延迟执行（Deferred Execution）：本篇最重要的一节

**核心结论：返回 `IEnumerable<T>` 的 LINQ 操作符在"构造时"什么都不做；只有在被枚举（`foreach`/`ToList`/`Count`/`First`…）时才逐个拉取元素。**

```csharp
var source = new List<int> { 1, 2, 3 };

// 这一步只构建了一个"查询计划"，没有任何元素被读取
IEnumerable<int> query = source.Where(x =>
{
    Console.WriteLine($"  过滤 {x}");     // 副作用演示：实际何时执行？
    return x > 1;
});

Console.WriteLine("--- 查询已定义，但还没执行 ---");

// 第一次枚举：真正开始逐个过滤
foreach (int x in query) Console.WriteLine($"得到 {x}");

Console.WriteLine("--- 第二次枚举：又从头执行了一遍 ---");
foreach (int x in query) Console.WriteLine($"得到 {x}");
```

输出（注意"过滤 1"出现了两次）：

```
--- 查询已定义，但还没执行 ---
  过滤 1
  过滤 2
得到 2
  过滤 3
得到 3
--- 第二次枚举：又从头执行了一遍 ---
  过滤 1
  过滤 2
得到 2
  过滤 3
得到 3
```

**为什么这样设计？** 三个收益：

1. **可组合**：`Where(...).OrderBy(...).Take(10)` 在编译时先拼成一条管道，运行时可优化（例如 `Take` 让上游提前停止，避免全表处理）。
2. **流式 + 大/无限序列**：`File.ReadLines(...).First()` 只读一行；`Fibonacci().Take(5)` 能处理无限序列。
3. **IQueryable 的前提**：EF Core 靠"先拿到表达式树、再翻译成 SQL"工作。如果查询立即执行，就无法整体翻译。

#### 陷阱一：多次枚举（Multiple Enumeration）

```csharp
// 反例：每次访问属性都新建查询并完整执行一遍
public static class BadUsage
{
    public static string Summarize(IEnumerable<int> data)
    {
        // Count() 遍历一次，Any() 又遍历一次，Select 在调用方再遍历一次 —— 共 3 次
        if (data.Count() == 0) return "空";
        return $"共 {data.Count()} 项，最大 {data.Max()}";
    }
}

// 更隐蔽的反例：每次枚举都重新查数据库
IEnumerable<Order> Query() => db.Orders.Where(o => o.Amount > 100);   // 模拟 EF Core

var q = Query();
Console.WriteLine($"数量 {q.Count()}");       // 生成并执行一次 SQL
Console.WriteLine($"总额 {q.Sum(o => o.Amount)}");  // 又执行一次 SQL
// 两次结果可能不一致（中间有并发写入）—— 这不是性能问题，而是正确性问题

// 正解：明确物化一次，之后复用同一份数据
var list = Query().ToList();                  // 一次查询，拿到快照
Console.WriteLine($"数量 {list.Count}，总额 {list.Sum(o => o.Amount)}");
```

> [!danger] 多次枚举的两个真实后果
> 1. **性能**：$k$ 次枚举 = $k$ 次完整计算；若每次都是一次数据库往返，延迟成倍上升。
> 2. **正确性**：源数据在两次枚举之间变化，会得到**互相矛盾**的结果（"数量 5 但列表只有 4 项"）。
> 检测手段：静态分析器 **CA1851（Avoid multiple enumerations of IEnumerable）** 会报警；还可以把参数类型收窄为 `IReadOnlyCollection<T>`/`IList<T>`，从签名上就消除"源可能被重新求值"的疑虑。

#### 陷阱二：闭包捕获的变量在枚举时才生效

```csharp
int threshold = 2;
var query = new[] { 1, 2, 3, 4 }.Where(x => x > threshold);

threshold = 3;                                // 改了被捕获的变量
Console.WriteLine(string.Join(",", query));   // 4 —— 用的是新值，因为谓词在枚举时才求值

// 想要"当时的值"，就地复制一份（或立即物化）
int snapshot = 2;
var fixedQuery = new[] { 1, 2, 3, 4 }.Where(x => x > snapshot).ToList();
snapshot = 3;
Console.WriteLine(string.Join(",", fixedQuery));   // 3,4 —— 已经是快照
```

#### 陷阱三：`foreach` 里的经典闭包 bug（已修复，但要知道原理）

```csharp
// C# 5 之前：所有委托共享同一个循环变量，输出 3 3 3
// C# 5 起（foreach）：每次迭代都是新变量，输出 0 1 2 —— 现在这是安全的
var actions = new List<Action>();
foreach (int i in new[] { 0, 1, 2 })
    actions.Add(() => Console.Write(i));
foreach (var a in actions) a();               // 012

// 但 for 循环的变量是同一个！这里仍然是 3 3 3
var bad = new List<Action>();
for (int i = 0; i < 3; i++)
    bad.Add(() => Console.Write(i));          // i 只有一个实例，循环结束时 i == 3
foreach (var a in bad) a();                   // 333

// 修正：循环体内复制一份局部变量
var good = new List<Action>();
for (int i = 0; i < 3; i++)
{
    int copy = i;
    good.Add(() => Console.Write(copy));      // 每个闭包捕获自己的 copy
}
foreach (var a in good) a();                  // 012
```

### 3.9 `IEnumerable<T>` 与 `IQueryable<T>`

| 维度 | `IEnumerable<T>` | `IQueryable<T>` |
|---|---|---|
| 所在程序集 | `System.Collections.Generic`（BCL） | `System.Linq`（`System.Linq.Queryable`） |
| 操作符接收 | `Func<T,bool>` 委托（编译好的方法） | `Expression<Func<T,bool>>` **表达式树** |
| 谁执行 | 进程内的 LINQ to Objects | 查询提供程序（EF Core、LINQ to XML 等） |
| 典型产物 | 内存中的过滤循环 | 翻译后的 SQL，在数据库执行 |
| 数据量 | 已全部在内存（或流式） | 只在数据库侧流动，只传回结果 |
| 未支持的操作 | — | 无法翻译的表达式**抛异常**（如 `InvalidOperationException`） |
| 何时使用 | 内存集合、已取回的数据 | 数据库查询的**构建阶段** |

```csharp
// 这是 EF Core 的典型用法（API 以官方最新文档为准）
IQueryable<Order> q = db.Orders;

// 关键点：以下三行只是"构建表达式树"，此时还没有任何 SQL 被执行
q = q.Where(o => o.Amount > 100);
q = q.OrderByDescending(o => o.CreatedAt);
q = q.Take(20);

// 触发执行：ToList 让提供程序把整棵表达式树翻译成一条 SQL
var result = q.ToList();

// 危险操作：过早 AsEnumerable()/ToList() 会把数据全拉到内存，再在内存里过滤
var wrong = db.Orders.ToList().Where(o => o.Amount > 100);   // 先全表拉取！性能灾难
var right = db.Orders.Where(o => o.Amount > 100).ToList();   // 过滤下推到数据库
```

> [!important] 三条铁律
> 1. **`IQueryable` 上只用能被翻译的表达式**：自定义方法、本地函数、`StringComparison` 重载常常无法翻译。要用就在 `ToList()` 之后再用。
> 2. **尽早过滤、尽晚物化**：`Where`/`Select` 放在 `ToList()` 之前，让数据库干活。
> 3. **`AsEnumerable()` 是"分界线"**：它之后的一切都在内存里执行。用它是**有意的**决定，而不是顺手写的。

### 3.10 LINQ 性能注意事项

| 建议 | 原因 | 替代写法 |
|---|---|---|
| 判断"有没有"用 `Any()` | `Count() > 0` 需要遍历完（对有 `ICollection` 的源会走 `Count` 快路径，但不能指望） | `if (list.Any())` |
| 已知是非空集合时用 `Count` 属性 | `Count()` 对 `IEnumerable<T>` 会先试 `ICollection<T>`，不行就遍历 | `list.Count`（`List<T>`/数组） |
| 避免对同一查询多次枚举 | 每次都是完整计算（见 3.8） | `ToList()` 物化一次 |
| 少用 `OrderBy` 后接 `Where` | 先排序再过滤 = 白排一遍 | 先 `Where` 后 `OrderBy` |
| `Where(...).First()` 优于 `Where(...).ToList()[0]` | `First` 短路，不遍历剩余元素 | 直接 `First`/`FirstOrDefault` |
| 需要多次按键查找时先建 `Dictionary`/`ToLookup` | 避免 $O(n^2)$ 的嵌套扫描 | `var map = list.ToDictionary(x => x.Id);` |
| 大数据量去重/包含判断用 `HashSet<T>` | `List.Contains` 是 $O(n)$；`HashSet` 是 $O(1)$ | `new HashSet<int>(list)` |
| 热路径上慎用链式 LINQ | 每个操作符可能分配一个迭代器对象（$k$ 个操作 ≈ $k$ 个分配） | 手写 `for` 循环，或合并成一个 `Where` |
| 用 `Span<T>`/`CollectionsMarshal` 处理极端热点 | 避免分配 | 见 [[CSharp-06-现代CSharp特性]] |
| 避免在循环里 `Concat`/`Union` | 每次构造新查询、重复枚举 | 先收集再合并，或 `List.AddRange` |

```csharp
// 复杂度对比：找出"在另一个列表里出现过的元素"
var ids = Enumerable.Range(0, 5_000).ToArray();
var targets = Enumerable.Range(4_000, 2_000).ToArray();

// 反例：嵌套扫描 O(n·m) —— 1.5 亿次比较量级
var slow = ids.Where(id => targets.Contains(id)).ToList();

// 正例：HashSet 先建索引 O(n + m)
var targetSet = new HashSet<int>(targets);
var fast = ids.Where(targetSet.Contains).ToList();

Console.WriteLine($"{slow.Count} / {fast.Count}");
```

### 3.11 自定义 `IComparer<T>` 与 `IEqualityComparer<T>`

| 接口 | 方法 | 被谁使用 |
|---|---|---|
| `IComparer<T>` | `Compare(x, y)` → 负数/0/正数 | `List.Sort`、`SortedSet`、`SortedDictionary`、`BinarySearch` |
| `IEqualityComparer<T>` | `Equals(x, y)` + `GetHashCode(x)` | `Dictionary`、`HashSet`、`Distinct`、`Union`、`GroupBy`、`ToLookup`、`Join` |
| `Comparison<T>` | `(x, y) => int` 委托 | `List.Sort(comparison)`、`Array.Sort` |
| `StringComparer` | 现成实现 | `StringComparer.OrdinalIgnoreCase` 等 |
| `Comparer<T>.Default` | 用 `IComparable<T>` | 默认排序 |
| `EqualityComparer<T>.Default` | 用 `Equals`/`GetHashCode` | 默认相等 |

```csharp
// IComparer<T>：定义"如何排序"
public sealed class NaturalLengthComparer : IComparer<string>
{
    public int Compare(string? x, string? y)
    {
        // 两个 null 视为相等；null 排最前（约定：null 最小）
        if (ReferenceEquals(x, y)) return 0;
        if (x is null) return -1;
        if (y is null) return 1;

        // 先按长度，再按字母序 —— 保证排序结果确定（total order）
        int byLength = x.Length.CompareTo(y.Length);
        return byLength != 0 ? byLength : string.CompareOrdinal(x, y);
    }
}

var words = new List<string> { "banana", "kiwi", "apple", "fig" };
words.Sort(new NaturalLengthComparer());
Console.WriteLine(string.Join(", ", words));        // fig, kiwi, apple, banana

// IEqualityComparer<T>：定义"何时算相同"（必须同时给 Equals 和 GetHashCode）
public sealed class OrdinalIgnoreCaseComparer : IEqualityComparer<string>
{
    public static readonly OrdinalIgnoreCaseComparer Instance = new();   // 无状态 → 单例复用

    public bool Equals(string? x, string? y) => string.Equals(x, y, StringComparison.OrdinalIgnoreCase);

    // 关键：必须与 Equals 的语义一致，否则 HashSet/Dictionary 会失效
    public int GetHashCode(string obj) => StringComparer.OrdinalIgnoreCase.GetHashCode(obj);
}

var tags = new[] { "CSharp", "csharp", "LINQ", "linq", "DotNet" };

// 不传比较器：按大小写敏感去重 → 5 个
Console.WriteLine(tags.Distinct().Count());

// 传自定义比较器：忽略大小写去重 → 3 个
Console.WriteLine(tags.Distinct(OrdinalIgnoreCaseComparer.Instance).Count());

// 分组也用它
foreach (var g in tags.GroupBy(t => t, OrdinalIgnoreCaseComparer.Instance))
    Console.WriteLine($"{g.Key}: {g.Count()}");

// 现成的 StringComparer 覆盖大多数字符串场景
var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase) { ["Content-Type"] = 1 };
Console.WriteLine(dict.ContainsKey("content-type"));    // True
```

> [!warning] 比较器的三个坑
> 1. **`IEqualityComparer<T>` 的 `GetHashCode` 与 `Equals` 语义必须一致**：`Equals` 忽略大小写而 `GetHashCode` 区分大小写，会导致"相等的键进了不同的桶"。
> 2. **比较器必须是"全序"**：`Compare` 要满足自反、反对称、传递。违反传递性会让排序算法行为不可预测（.NET 会抛 `InvalidOperationException: IComparer.Compare() method returns inconsistent results`）。
> 3. **`List<T>.Sort` 是不稳定排序**：需要稳定就用 LINQ 的 `OrderBy`（`Enumerable.OrderBy` 是稳定的），或加上能唯一区分的次级比较键。
> 4. **`string.Compare` 的区域性依赖**：默认 `string.Compare(a, b)` 与 `string.CompareOrdinal` 结果可能不同。**排序用区域性（给人看）、相等判断用序数（给程序判断）**，别混。

---

## 四、怎么用：一个完整的销售分析示例

需求：给定订单与客户数据，输出（1）每个客户的订单数与总额，按总额降序；（2）金额 Top-3 的订单；（3）找出"有订单但客户表中不存在"的孤儿订单；（4）把订单按每 2 条一批处理。

```csharp
using System.Text;

namespace Demo.Analytics;

public sealed record Customer(string Id, string Name, string Region);
public sealed record Order(int Id, string CustomerId, decimal Amount, DateOnly Date);

public static class SalesReport
{
    public static string Build(IEnumerable<Customer> customers, IEnumerable<Order> orders)
    {
        // 关键：入口处物化一次，避免后续多次枚举（多次枚举既慢又可能结果不一致）
        var customerList = customers as IReadOnlyCollection<Customer> ?? customers.ToList();
        var orderList = orders as IReadOnlyCollection<Order> ?? orders.ToList();

        // 建立索引：把后续的 O(n·m) 嵌套查找降为 O(n + m)
        var byId = customerList.ToDictionary(c => c.Id, StringComparer.Ordinal);

        var sb = new StringBuilder();

        // (1) 按客户汇总：用 GroupJoin 保留"没有订单的客户"
        sb.AppendLine("== 客户汇总（按总额降序） ==");
        var summary = byId.Values
            .GroupJoin(orderList, c => c.Id, o => o.CustomerId, (c, os) => new
            {
                c.Name,
                Count = os.Count(),
                Total = os.Sum(o => o.Amount),      // 空序列的 Sum 是 0，不会抛异常
                Max = os.Select(o => (decimal?)o.Amount).Max() ?? 0m,  // 空序列的 Max 会抛，先转可空
            })
            .OrderByDescending(x => x.Total)
            .ThenBy(x => x.Name, StringComparer.Ordinal);   // 次级键保证结果稳定

        foreach (var x in summary)
            sb.AppendLine($"  {x.Name,-6} {x.Count,2} 单  合计 {x.Total,10:0.00}  最大 {x.Max,8:0.00}");

        // (2) Top-3 大额订单：先排序再取，Take 会短路上游
        sb.AppendLine("== 金额 Top 3 ==");
        foreach (var o in orderList.OrderByDescending(o => o.Amount).ThenBy(o => o.Id).Take(3))
            sb.AppendLine($"  #{o.Id} {o.Amount,8:0.00} ({o.CustomerId})");

        // (3) 孤儿订单：用 HashSet 做 O(1) 存在性判断
        sb.AppendLine("== 孤儿订单 ==");
        var knownIds = byId.Keys.ToHashSet(StringComparer.Ordinal);
        var orphans = orderList.Where(o => !knownIds.Contains(o.CustomerId)).ToList();
        sb.AppendLine(orphans.Count == 0
            ? "  无"
            : string.Join(Environment.NewLine, orphans.Select(o => $"  #{o.Id} → 未知客户 {o.CustomerId}")));

        // (4) 分批处理（Chunk，.NET 6+）：适合批量写库、分批调用外部 API
        sb.AppendLine("== 分批（每批 2 条） ==");
        foreach (var batch in orderList.OrderBy(o => o.Id).Chunk(2))
            sb.AppendLine($"  批：{string.Join(", ", batch.Select(o => $"#{o.Id}"))}");

        return sb.ToString();
    }
}
```

调用并验证：

```csharp
var customers = new[]
{
    new Customer("C1", "阿伟", "华东"),
    new Customer("C2", "小美", "华南"),
    new Customer("C3", "老张", "华北"),      // 无订单
};
var orders = new[]
{
    new Order(1, "C1", 120m, new DateOnly(2026, 1, 5)),
    new Order(2, "C2", 80m, new DateOnly(2026, 1, 6)),
    new Order(3, "C1", 200m, new DateOnly(2026, 1, 7)),
    new Order(4, "C9", 50m, new DateOnly(2026, 1, 8)),   // 孤儿：客户不存在
};

Console.WriteLine(SalesReport.Build(customers, orders));
```

预期输出（节选）：

```
== 客户汇总（按总额降序） ==
  阿伟      2 单  合计     320.00  最大   200.00
  小美      1 单  合计      80.00  最大    80.00
  老张      0 单  合计       0.00  最大     0.00
== 金额 Top 3 ==
  #3   200.00 (C1)
  #1   120.00 (C1)
  #2    80.00 (C2)
== 孤儿订单 ==
  #4 → 未知客户 C9
== 分批（每批 2 条） ==
  批：#1, #2
  批：#3, #4
```

设计要点：入口 `ToList()` 一次，消除多次枚举；`ToDictionary`/`ToHashSet` 把嵌套查找降为 $O(1)$；`GroupJoin` 保留零订单客户；`Empty` 序列上的 `Max` 会抛异常，所以先用 `Select(o => (decimal?)o.Amount)` 提升为可空再 `?? 0m`。

---

## 五、注意事项与常见坑

> [!warning] 集合与 LINQ 的十四大坑
> 1. **多次枚举 `IEnumerable<T>`**：$k$ 次枚举 = $k$ 次计算，且可能读到不同数据。物化一次。
> 2. **把 `IQueryable` 过早 `ToList()`**：全表拉到内存再过滤。保持 `IQueryable` 直到需要结果。
> 3. **在 `IQueryable` 上用自定义方法**：无法翻译成 SQL，运行期抛异常。用 `ToList()` 之后再用。
> 4. **重写 `Equals` 忘了 `GetHashCode`**：`HashSet`/`Dictionary`/`Distinct`/`GroupBy` 全部静默失效。
> 5. **可变对象作字典键**：键"消失" + 幽灵条目。
> 6. **返回内部 `List<T>`**：调用方能改你的内部状态。返回 `IReadOnlyList<T>` 或 `AsReadOnly()`。
> 7. **误以为 `IReadOnlyList<T>` 是不可变的**：它只是只读**视图**，底层变了它也跟着变；要快照就复制。
> 8. **在 `foreach` 里增删集合**：抛 `InvalidOperationException`。用倒序 `for` 或 `RemoveAll`。
> 9. **循环里 `List.Remove`/`Insert(0, ...)`**：$O(n^2)$。
> 10. **`Count() > 0`**：用 `Any()`；有 `Count` 属性就用属性。
> 11. **`Single` 与 `First` 混用**：`Single` 在"多条匹配"时抛异常——这可能是你想要的，也可能是线上事故。
> 12. **`for` 循环里创建闭包**：`for` 的循环变量只有一个实例，全部闭包共享（`foreach` 从 C# 5 起已修复）。
> 13. **`GroupBy` 的结果被多次枚举**：`GroupBy` 是延迟执行且**每次枚举都重新分组**；需要重复访问就 `ToLookup` 或 `ToList`。
> 14. **`Dictionary` 遍历顺序**：当前实现是插入顺序，但**这是实现细节**，不要写依赖它的逻辑。

> [!tip] 工程实践建议
> - **公开 API 的参数类型尽量宽、返回类型尽量窄**（参数 `IEnumerable<T>`，返回 `IReadOnlyList<T>`）。
> - **一次物化，多次使用**：进入计算核心前 `ToList()`/`ToArray()`，之后按 `Count`/索引访问。
> - **先建索引再循环**：`ToDictionary`/`ToLookup`/`ToHashSet` 是把 $O(n^2)$ 降为 $O(n)$ 最常用的手段。
> - **开启静态分析**：`<AnalysisLevel>latest</AnalysisLevel>` + `<TreatWarningsAsErrors>true</TreatWarningsAsErrors>`，CA1851（多次枚举）、CA1860（用 `Any` 而非 `Count`）能提前拦住大部分坑。
> - **热路径手写循环**：`for`/`foreach` + 简单判断往往比链式 LINQ 快数倍（少了迭代器分配与委托调用）。
> - **别把 LINQ 当 SQL 用在大表上**：内存里跑 $O(n \log n)$ 排序几百万条数据是可行的，但 $O(n^2)$ 的连接绝对不行。

---

## 六、练习题

1. **基础题**：给定 `int[] data = { 5, 3, 9, 3, 7, 5, 1 }`，用 LINQ 一行得到：去重后的升序序列、最大值与最小值的差、以及每个数字出现的次数（`Dictionary<int,int>`）。再说明哪几个操作符是延迟执行的。
2. **基础题**：实现 `static IEnumerable<int> Primes()` 生成无限素数序列（用迭代器 + `yield return`），然后打印前 20 个素数。要求说明为什么这个写法不会死循环。
3. **进阶题**：下面的代码存在"多次枚举"与"性能"两个问题，请指出并改写：
   ```csharp
   public static string Report(IEnumerable<Order> orders)
   {
       if (orders.Count() == 0) return "空";
       var big = orders.Where(o => o.Amount > 1000);
       return $"总数 {orders.Count()}，大额 {big.Count()}，最大 {big.Max(o => o.Amount)}";
   }
   ```
   要求改写后每个 `IEnumerable` 只枚举一次，并给出改写前后的枚举次数对比。
4. **进阶题**：实现 `IEqualityComparer<Order>`，规则："金额相差在 $0.01$ 以内、且客户相同"视为同一张订单（用于去重）。要求 `GetHashCode` 与 `Equals` 语义一致，并用 `Distinct` 与 `GroupBy` 各验证一次。提示：把所有参与比较的字段**量化**（例如金额四舍五入到分）后再算哈希码。
5. **思考题**：为什么 `Enumerable.OrderBy` 是稳定排序，而 `List<T>.Sort` 不稳定？请从**实现方式**（延迟执行 vs 原地排序）和 **API 契约**（返回新序列 vs 修改自身）两个角度解释。再举一个"排序不稳定会导致线上问题"的具体场景。

---

## 七、常见问题（FAQ）

**Q1：`IEnumerable<T>` 和 `List<T>` 该用哪个当方法参数？**
A：默认用 `IEnumerable<T>`——它兼容数组、`List<T>`、`HashSet<T>`、LINQ 查询结果，给调用方最大自由。但如果你**会枚举两次以上**，就该用 `IReadOnlyCollection<T>`（有 `Count`）或明确在方法入口 `ToList()`。反过来，如果方法内部会修改集合，就用 `ICollection<T>`/`IList<T>` 把需求写在签名上。**签名是给调用方看的契约，要如实反映你真正需要的能力。**

**Q2：`Where(...).ToList()` 和 `Where(...).ToArray()` 怎么选？**
A：`ToList()` 通常略快（`List<T>` 的扩容策略比 `ToArray` 的"先数再分配"更省一次遍历），而且返回的 `List<T>` 还能继续 `Add`。`ToArray()` 的收益是固定长度、内存略紧凑、可以安全地对外共享（别人无法 `Add` 破坏你的数据），而且数组能配合 `Span<T>`。**对外暴露用 `ToArray()`，内部继续处理用 `ToList()`。**

**Q3：LINQ 会不会很慢？什么时候该放弃 LINQ 手写循环？**
A：多数业务代码里 LINQ 的开销可以忽略——瓶颈通常在 IO 和数据库，而不是几纳秒的委托调用。真正需要警惕的是三类情况：（1）**算法复杂度错了**（`List.Contains` 嵌套 = $O(n^2)$）；（2）**多次枚举**（把 $O(n)$ 变成 $k \cdot O(n)$）；（3）**热路径上每秒百万次**的链式查询（每层迭代器分配会带来 GC 压力）。前两类改写法就能解决，第三类才考虑手写 `for`。**先用 profiler 定位，再优化。**

**Q4：`Dictionary` 遍历顺序稳定吗？我能依赖它吗？**
A：**不能依赖。** .NET Core 3.0 起 `Dictionary` 的内部实现确实按插入顺序遍历（移除后再插入会排到末尾），但官方文档没有承诺这一点——它是实现细节，未来版本可能改变（.NET Framework 时代就是另一套顺序）。需要确定性顺序就用 `SortedDictionary<K,V>`（按键排序）或 `List<KeyValuePair<K,V>>`/`OrderedDictionary`（按插入顺序）。

---

## 相关笔记

- [[CSharp-01-环境与基础语法]]：泛型基础、装箱与拆箱、`foreach` 的实现原理
- [[CSharp-02-面向对象]]：`Equals`/`GetHashCode` 契约、接口设计与 `IReadOnlyList<T>` 的封装价值
- [[CSharp-04-委托事件与Lambda]]：LINQ 之所以能写成链式，靠的是委托与 Lambda
- [[CSharp-05-异步编程]]：`IAsyncEnumerable<T>` 与流式异步数据处理
- [[后端-05-数据库操作与ORM]]：`IQueryable` 与 EF Core 的查询翻译、N+1 问题
- [[数据结构-哈希表]]：哈希函数、冲突解决与装载因子
- [[算法-复杂度分析]]：均摊分析与渐进记号

## 参考来源

- [Commonly used collection types](https://learn.microsoft.com/en-us/dotnet/standard/collections/commonly-used-collection-types)
- [Selecting a collection class](https://learn.microsoft.com/en-us/dotnet/standard/collections/selecting-a-collection-class)
- [Hashtable and dictionary collection types](https://learn.microsoft.com/en-us/dotnet/standard/collections/hashtable-and-dictionary-collection-types)
- [Constraints on type parameters](https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/generics/constraints-on-type-parameters)
- [Iterators](https://learn.microsoft.com/en-us/dotnet/csharp/iterators)
- [`yield` statement](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/yield)
- [LINQ (Language Integrated Query)](https://learn.microsoft.com/en-us/dotnet/csharp/linq/)
- [Introduction to LINQ queries](https://learn.microsoft.com/en-us/dotnet/csharp/linq/get-started/introduction-to-linq-queries)
- [Deferred execution and lazy evaluation](https://learn.microsoft.com/en-us/dotnet/standard/linq/deferred-execution-lazy-evaluation)
- [`Enumerable` class](https://learn.microsoft.com/en-us/dotnet/api/system.linq.enumerable)
- [`Queryable` class](https://learn.microsoft.com/en-us/dotnet/api/system.linq.queryable)
- [`Enumerable.Chunk`](https://learn.microsoft.com/en-us/dotnet/api/system.linq.enumerable.chunk)
- [`List<T>`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1)
- [`Dictionary<TKey,TValue>`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2)
- [`PriorityQueue<TElement,TPriority>`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.priorityqueue-2)
- [`IEqualityComparer<T>`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.iequalitycomparer-1)
- 说明：集合的内部实现（扩容倍数、遍历顺序）与 LINQ API 的可用版本随运行时版本变化，以官方最新文档为准。
