LINQ 源码剖析（下）：GroupBy、Join 与 Aggregate
系列：C# 与常用数据结构源码剖析 · 高级特性篇
阅读时间：约 80 分钟
源码基线：.NET 8.0.0，dotnet/runtime的System.Linq：Grouping.cs、Join.cs、Aggregate.cs及相关 Iterator 实现
版本边界：本文只讨论 LINQ to Objects 的Enumerable。Queryable、PLINQ 与第三方 provider 有不同执行模型；后续 .NET 的专用优化可能改变内部路径。
代码约定：代码均明确为业务示例、教学伪代码或结构化节选，不冒充逐字源码。
一、先区分三种“延迟”
LINQ 查询常被笼统称为延迟执行，但至少要拆成三件事：
- 调用方法时是否遍历源：
GroupBy(...)、Join(...)通常只返回查询对象，调用瞬间不枚举。 - 第一次 MoveNext 前是否必须缓冲：GroupBy 在产出第一个分组前要完整读取源；Join 在产出第一个结果前要完整建立 inner 的索引。
- 结果是否流式产生：Join 建完 inner Lookup 后可逐个读取 outer 并产出结果；GroupBy 则已把全部元素放入分组。
Aggregate不返回IEnumerable。调用它就立即枚举源并返回一个最终值，属于终结操作。把这三者都归为“延迟”或“立即”会掩盖首项延迟、无限序列和内存峰值。
本篇固定.NET 8源码解释 Lookup/Grouping，而不是用Dictionary<TKey,List<T>>冒充真实结构；简化代码仅用于展现语义。
二、Lookup 与 Grouping 的实际职责
2.1 Lookup 不是一层 Dictionary 包装
基线Lookup<TKey,TElement>管理一个 Grouping 桶数组、比较器、分组数量，以及连接所有分组的循环链。概念结构如下：
// 结构化概念，不是逐字源码。 sealed class Lookup<TKey, TElement> { IEqualityComparer<TKey> _comparer; Grouping<TKey, TElement>?[] _groupings; // 哈希桶头 Grouping<TKey, TElement>? _lastGrouping; // 插入顺序循环链尾 int _count; } sealed class Grouping<TKey, TElement> : IGrouping<TKey, TElement>, IList<TElement> { TKey _key; int _hashCode; TElement[] _elements; int _count; Grouping<TKey, TElement>? _hashNext; // 同桶冲突链 Grouping<TKey, TElement>? _next; // 分组插入顺序链 }字段可见性和辅助接口按 tag 有更多细节。关键点是 Grouping 本身既是某个键的动态元素数组，又是哈希桶冲突链节点，并参与分组顺序链。它不是额外Dictionary<TKey,List<T>>中的一对对象。
2.2 哈希与分组等价类
每个源元素经 keySelector 得到 key，Lookup 使用传入的IEqualityComparer<TKey>或默认比较器计算哈希和相等性。比较器认为相等的 key 进入同一 Grouping；第一个创建该组的 key 通常成为IGrouping.Key对外值。
相等键必须产生相同哈希，且键参与相等/哈希的状态在分组建立期间必须稳定。可变引用 key 若在 keySelector 返回后被其他线程改动，会破坏 Lookup 查询；GroupBy 本身也不赋予源或元素并发安全。
.NET 8Lookup 对 null key 有实现支持路径，具体由内部哈希/比较逻辑处理。自定义 comparer 必须也能按它声明的契约处理可能输入；不要把 Dictionary 的notnull约束或某一数据库 provider 的 null 语义直接套到 Enumerable.GroupBy。
2.3 两种顺序
在稳定、未并行的 LINQ to Objects 基线中，外部分组按各键首次出现的顺序枚举；每个组内元素按源中出现顺序保存。因此：
// 业务示例。 string[] source = { "b1", "a1", "b2", "c1", "a2" }; var groups = source.GroupBy(x => x[0]); // 组顺序：b, a, c // b 组：b1, b2；a 组：a1, a2这是 Enumerable GroupBy 的可观察行为，不应误归因于哈希桶物理顺序；Lookup 用独立的_next链维护分组创建顺序。换到 PLINQ 或远程 provider 时顺序规则不同，除非明确排序。
Grouping 的_elements按需扩容。某个热点键包含绝大多数元素时，会形成一个很大的数组；多个小组则产生许多 Grouping 和小数组。总元素量相同，分布不同也会有不同对象数量、扩容复制和局部性。
三、GroupBy：返回延迟对象，首枚举全量缓冲
3.1 执行时序
// 业务示例。 IEnumerable<IGrouping<char, string>> query = source.GroupBy(x => x[0]); // 到这里通常没有读取 source。 using IEnumerator<IGrouping<char, string>> e = query.GetEnumerator(); bool hasFirstGroup = e.MoveNext(); // 第一次 MoveNext 为产出第一个组，需要先把 source 完整读入 Lookup。所以最准确的说法是：GroupBy 具有延迟调用语义，但在枚举时是全缓冲操作。若源在构建 query 与枚举之间变化，枚举看到的是枚举时的源状态；再次枚举 query 通常会再次读取源并新建 Lookup，而不是自动缓存上次结果。
如果需要复用同一分组快照，可显式ToLookup。ToLookup是立即执行：调用时遍历源并返回可多次查询的 Lookup。它仍只是元素引用/值的浅快照，元素对象内部可继续变化。
3.2 elementSelector 与 resultSelector
GroupBy(source,keySelector,elementSelector)在缓冲时就对每个源项运行 elementSelector，把结果放入组。带 resultSelector 的重载在分组完成后把 key 与组元素枚举交给结果转换。用户委托异常会终止枚举；已创建的内部缓冲随后等待回收。
resultSelector 若对同一 group 多次枚举，通常会多次遍历已缓冲数组，但不会重新枚举原 source。若内部又调用ToArray、OrderBy等，会产生额外缓冲。
3.3 复杂度和无限源
对 n 个源项，在哈希分布正常、比较器成本合理时，构建期望 O(n)，额外存储 O(n + 分组数)。最坏哈希碰撞可让比较成本显著上升，不能只写绝对 O(n)。每个元素至少进入某个分组数组，GroupBy 不适合真正无限且不结束的源：首个组永远无法产出。
若需求是流式处理连续相同键，可自己做相邻分段（类似 chunk by），但它只在输入已按键聚集时等价；全局 GroupBy 必须知道后面是否还会出现旧键。无限事件流通常需要窗口、时间桶、容量上限与过期策略，而不是裸 GroupBy。
四、Join：先完整索引 inner，再流式扫描 outer
4.1 构建哪一侧
.NET 8的Enumerable.Join(outer, inner, ...)在枚举时首先从inner构建Lookup<TKey,TInner>，随后遍历 outer：
// 教学伪代码：表达执行方向和结果顺序。 Lookup<TKey, TInner> lookup = BuildLookupForJoin(inner, innerKeySelector, comparer); foreach (TOuter outerItem in outer) { TKey key = outerKeySelector(outerItem); if (lookup.TryGetGrouping(key, out Grouping<TKey, TInner> matches)) { foreach (TInner innerItem in matches) yield return resultSelector(outerItem, innerItem); } }这意味着参数顺序影响缓冲侧：无论哪边更小，标准 Join 的 inner 都被全量索引。若两边角色可交换且 resultSelector 能调整，把更适合缓冲的一侧放 inner 可能降低内存；但必须同时维护期望结果顺序与重复项笛卡尔语义。
实现有针对空 inner 的快速结果路径，具体 iterator 代码按 tag 阅读。普通语义仍是调用 Join 时不枚举，第一次 MoveNext 先消费 inner，再按需消费 outer。
4.2 null 键边界
Join 使用面向连接的 Lookup 创建路径；在.NET 8LINQ to Objects 实现中，innerKeySelector 产生 null 的项不会建立可匹配分组，因此 outer 的 null 键也不会与之生成结果。这个边界与普通ToLookup可存 null 组、以及 SQL provider 的 null 语义都可能不同，必须按基线测试，不凭 GroupBy 经验推断。
4.3 结果顺序和重复项
Join 结果首先按 outer 枚举顺序；对某个 outer，匹配 inner 按它们在 inner 中的出现顺序。若 outer 某键出现 a 次、inner 同键出现 b 次，就产生 a×b 个结果。高重复键可能造成输出爆炸，即使 Lookup 本身只有 O(inner.Count) 存储。
// 业务示例：每个玩家与其同 ID 的所有记录匹配。 var result = players.Join( records, p => p.Id, r => r.PlayerId, (p, r) => new { p.Name, r.Score });若业务期望 inner 每键唯一，应在建索引前验证，或使用 Dictionary 并对重复 Add 失败；不要让 Join 静默把重复数据扩成多结果。
4.4 空间和生命周期
Join 的 Lookup 保持所有 inner 元素，直到该 Join 枚举器释放或不可达。即使调用.Take(1)，也必须先完整读取 inner 才能产出第一个结果。若 inner 很大、outer 很小，这个首项成本尤其重要。
outer 是无限序列时，Join 在有限 inner 建表后可以持续输出；inner 是无限序列时永远无法开始 outer。若两边都超出内存，需要数据库/外部排序合并/分区哈希连接或流式窗口连接，不能期待 Enumerable.Join 自动溢写磁盘。
五、GroupJoin：每个 outer 获得一个匹配序列
GroupJoin同样先为 inner 建 Lookup，但对每个 outer 只调用一次 resultSelector，并传入该键的匹配IEnumerable<TInner>；无匹配时传入空序列。它返回的是IEnumerable<TResult>，不是固定的IEnumerable<IGrouping<...>>。
// 业务示例：每个部门得到成员序列，包括零成员部门。 var departmentsWithMembers = departments.GroupJoin( employees, d => d.Id, e => e.DepartmentId, (department, members) => new { department.Name, Count = members.Count(), Members = members });结果按 outer 顺序，每个匹配序列按 inner 顺序。members 指向已建立 Lookup 中的组或空序列，不会为每个 outer 重新扫描 inner。多个具有同键的 outer 可能接收同一底层组视图；调用者应把它当只读 IEnumerable，不依赖内部引用身份。
常见“左外连接”查询语法会在 GroupJoin 后SelectMany(group.DefaultIfEmpty(), ...)。这会把无匹配 outer 展开为一条带默认 inner 的结果；默认值可能是 null/零值，领域上应显式处理，不把缺失与合法默认对象混淆。
GroupJoin 仍会完整缓冲 inner，且 resultSelector 中保存 members 到长期对象会让整个 Lookup/相关元素的生命周期延长。需要物化小快照时可明确 ToArray，但会增加复制。
六、Aggregate：立即、单遍、按严格顺序折叠
6.1 无 seed 重载
source.Aggregate(func)取第一个元素作为 accumulator，再从第二个开始调用 func。空序列没有初始值，会抛InvalidOperationException：
// 教学伪代码。 using var e = source.GetEnumerator(); if (!e.MoveNext()) throw new InvalidOperationException("Sequence contains no elements"); T acc = e.Current; while (e.MoveNext()) acc = func(acc, e.Current); return acc;它与数学上需要单位元的操作不同。若空序列有合理结果，使用 seed 重载并选择正确单位元，例如加法 0、乘法 1；不要捕获异常充当正常空分支。
6.2 seed 重载
Aggregate(seed, func)从 seed 开始，对每个源元素按枚举顺序更新累加器。空序列直接返回 seed。TAccumulate 可与 TSource 不同，适合构建统计状态：
// 业务示例：值元组作为小型累加器。 var summary = values.Aggregate( seed: (sum: 0L, count: 0), func: (acc, value) => (acc.sum + value, acc.count + 1));这段仍可能发生溢出，取决于数据与 checked 上下文；Aggregate 不自动提供数值稳定性。浮点加法非结合，顺序改变会改变舍入结果。
6.3 resultSelector 重载
第三类重载在完整折叠后调用一次 resultSelector，把内部累加状态转换为最终结果：
double average = values.Aggregate( seed: (sum: 0.0, count: 0), func: (acc, value) => (acc.sum + value, acc.count + 1), resultSelector: acc => acc.count == 0 ? double.NaN : acc.sum / acc.count);resultSelector 只在正常完成折叠后调用。source、func 或 resultSelector 抛异常会传播；枚举器由实现按协议释放。
6.4 “无中间集合”不等于“无分配”
Aggregate 本身不需要像 GroupBy 一样建立 O(n) Lookup，但 func 可以每步创建新字符串、List、不可变集合或闭包对象。用Aggregate("", (s,x) => s+x)拼接大量字符串会反复创建中间字符串，常用string.Join、StringBuilder 或专用 API 更合适。
若 accumulator 是大值类型，每次acc = func(acc,item)可能复制它；引用类型 accumulator 可原地修改，但异常后可能留下部分状态，且不再是纯函数。复杂度应包含用户委托。
七、比较器、键稳定性和可变元素
GroupBy、Join、GroupJoin 均允许IEqualityComparer<TKey>。契约是相等键哈希相同、Equals 稳定且为等价关系。比较器选择直接定义组与匹配：大小写不敏感 comparer 会把"A"与"a"归为同组；文化 comparer 的语义也要显式记录。
keySelector 返回大型结构体会产生哈希、比较和复制成本。返回可变引用对象更危险：Lookup 建好后修改参与哈希的状态，随后按该对象查组可能失败。最稳妥的是不可变、紧凑键，或在 keySelector 中提取稳定 ID。
分组元素是浅保存。源中 class 对象进入 Grouping 后，对象字段仍可被修改；GroupBy 不产生深快照。若要求历史一致性，应在 elementSelector 投影成不可变值。
用户委托还可能有副作用。多次枚举 GroupBy/Join 查询会重新枚举源并再次调用 selector；不能把扣款、发消息、随机 ID 等副作用藏在 selector 中。即便当前只枚举一次，调试器、Count/ToList 和日志也可能触发额外枚举。
八、内存、GC 与大组/高基数模型
GroupBy 的内存不仅是 n 个元素引用：还有 Lookup 桶数组、每个不同键的 Grouping 对象、每组动态数组的未使用容量、碰撞/顺序链接。值类型 TElement 内联在组数组中，大值会放大扩容复制；引用类型保存引用并延长对象生命周期。
两种极端分布：
- 单个大组：Grouping 数少，但一个
_elements数组持续扩容，可能形成大连续分配。 - 每项不同键：大量 Grouping 和小数组，对象数与哈希开销高。
Join/GroupJoin 只缓冲 inner，但重复匹配会使下游结果数量远大于输入；若紧接ToList，输出物化可能成为真正内存峰值。使用流式下游可以避免一次保存全部结果，却不能消除 inner Lookup。
.NET大对象策略、对象头与阈值依运行时/版本变化，不能把 CoreCLR 数字直接套 Unity。用分配追踪、存活堆、键基数和最大组大小测量，不编造“int 键固定比 string 快几倍”。
缓存ToLookup可避免重复建表，但也让所有源元素持续可达。明确缓存失效与生命周期；不要为节省 CPU 造成无界内存缓存。
九、无限序列和资源型枚举器
| 操作 | 有限 source/inner 要求 | 无限输入结果 |
|---|---|---|
| GroupBy / ToLookup | source 必须结束才能产出完整组 | 永不产出第一个分组 |
| Join / GroupJoin | inner 必须结束；outer 可按需继续 | inner 无限则卡在建表；outer 无限可持续输出 |
| Aggregate | source 必须结束才返回最终值 | 永不返回（除非取消/异常终止） |
IEnumerable<T>自身没有统一取消参数。无限/慢速源应把 CancellationToken 纳入枚举器实现或 selector 外层协议，或改用IAsyncEnumerable<T>对应操作库。标准 Enumerable GroupBy 也不自动实现时间窗口。
文件、数据库游标等资源型源会在查询枚举器生命周期内保持资源。GroupBy 读取完整源后才开始返回组；Join 则先读完 inner，再逐步持有 outer 枚举器。调用方应及时 Dispose 查询枚举器，避免只取部分结果后长期持有资源。
十、PLINQ 不是同一个顺序与聚合模型
source.AsParallel()转入 PLINQ。它会分区、并行构建/合并状态，内存、调度和顺序与 Enumerable 不同。默认 unordered 查询不承诺原始顺序；AsOrdered()增加顺序约束和合并成本。
并行 Aggregate 通常需要分区 accumulator、分区内更新函数、分区结果合并函数和最终 selector。合并函数应具备适当结合性；普通左折叠中依赖严格顺序的减法、字符串拼接或浮点结果，平行重组可能产生不同答案。带副作用的 accumulator 更危险。
PLINQ 也不是自动解决大 Lookup 内存或哈希攻击。小输入、廉价 selector 和高合并成本时，并行调度可能得不偿失。结论必须以目标 CPU、输入规模、键分布和顺序要求测量。
不要把本文.NET 8 Enumerable的分组首现顺序、inner Lookup 字段和单线程迭代细节直接作为 PLINQ 契约。
十一、Unity 热路径边界
Unity 支持的 LINQ 类库与运行时实现随版本、API Compatibility Level、Mono/IL2CPP 后端变化。本文内部字段只能解释桌面.NET 8基线；目标 Player 应重新 profile。
GroupBy/Join 在每帧热路径会创建 Lookup、Grouping 和数组，并保持输入元素到枚举结束。典型替代策略不是“永远禁用 LINQ”，而是：
- 配置加载/关卡初始化时预建 Dictionary 或 Lookup，并明确失效；
- 每帧计数只需 Dictionary<TKey,int>，无需保存所有组元素；
- 已有稳定 ID 的实体直接维护索引，避免每帧 Join；
- 短生命周期临时数据使用可复用缓冲时，定义清理和容量上限；
- 先在 IL2CPP 真机用代表数据测 GC Alloc、CPU 和尾帧，而非只测编辑器。
缓存 Lookup 的元素若是UnityEngine.Object包装，原生对象销毁后包装引用仍在组内，并有 Unity 特殊 null 语义。用稳定 ID 和生命周期事件更新索引，比周期性 GroupBy 更可控。
Aggregate 用值累加器可能不分配 Lookup，但 lambda 捕获、接口枚举、字符串构建和 async/协程边界仍可产生分配。检查具体调用形态。
十二、典型失败反例
- 认为调用 GroupBy 就立即读取源，或反过来认为首组能流式产出。
- 对无限事件流直接 GroupBy，等待永远不会出现的第一组。
- 把 Lookup 写成 Dictionary+List 并依赖 Dictionary 枚举顺序解释组顺序。
- 认为 GroupJoin 返回固定 IGrouping，而忽略 resultSelector。
- 让 Join 的 inner 是巨大/无限源，却只准备 Take(1)。
- 假定 Join 自动选择较小一侧建表。
- 忽略重复键的 a×b 输出，ToList 后内存爆增。
- 在 selector 中执行副作用，多次枚举时重复发生。
- 修改作为 key 的对象状态，破坏 Lookup 后续查询。
- 对空序列调用无 seed Aggregate，拿异常当正常流程。
- 用字符串 Aggregate 反复连接，误称“无中间分配”。
- 把顺序敏感 Aggregate 直接并行化，结果因重组改变。
- 在 Unity 每帧 GroupBy/Join，却只看平均 FPS 不看分配和尾帧。
- 引用脱离环境的键类型固定倍率或伪基准。
十三、差分、执行时序和基准实验
13.1 可观察枚举源
实现记录GetEnumerator、每次 MoveNext、Current 与 Dispose 的源。分别只创建 GroupBy/Join 查询、调用 GetEnumerator、第一次 MoveNext、Take(1)、完整枚举，断言调用时序。对 Join 分别记录 outer/inner，证明第一次结果前 inner 完整枚举，而 outer 随结果推进。
13.2 GroupBy 差分
用参考模型按同一 comparer 保存“键首次出现列表 + 每键元素列表”。随机生成 null（若 TKey 允许）、重复、高基数和恒定哈希键，与 GroupBy 比较组 Key、组顺序、组内顺序和 resultSelector。query 枚举两次，验证源也读取两次；ToLookup 则创建时读取一次。
13.3 Join/GroupJoin 差分
用双重循环建立语义参考：按 outer 顺序，对每个 outer 按 inner 顺序输出所有相等匹配。随机输入重复键、无匹配、空侧和 null key，分别与 Join/GroupJoin 比较；null 预期固定到.NET 8 Enumerable实测。验证结果数量包含重复项乘积。
13.4 Aggregate 属性
无 seed：空序列应抛，单元素不调用 func 并返回该元素；有 seed：空序列返回 seed；resultSelector 正常时只调用一次。用非结合运算记录严格左折叠顺序；让 func 在第 k 项抛错，确认后续源不再读取且枚举器被释放。
13.5 内存分布实验
固定 n，比较单大组、均匀少数组和每项一组；记录总分配、对象数、最大数组、首项延迟、完整吞吐和枚举后存活。Join 固定输入量改变 inner/outer 参数位置与重复率，分开记录 Lookup 和结果物化。测试代码、运行时、CPU、比较器、预热和 GC 配置一并发布，不给普适倍数。
13.6 Unity Player 实验
同一数据在编辑器 Mono、目标平台 Mono/IL2CPP（实际支持项）与 Development/Release Player 测量。Profiler 标记查询构建、首 MoveNext、完整消费和 ToList，记录 GC Alloc、主线程时间、帧分位数和存活引用。避免日志和随机数据生成污染测量区。
十四、选型与源码阅读清单
需要一次遍历按键计数时，手写 Dictionary 计数器比 GroupBy 保存全部组更节省；需要重复查询多个键时，ToLookup 可表达只读一对多索引；需要 inner 每键唯一时 Dictionary 更能暴露重复；需要两侧超大时考虑让数据库执行、分区或排序合并；需要无限流分组时设计窗口和过期；只需总和/最值优先专用 Sum/Min/Max，复杂状态才使用 Aggregate。
阅读.NET 8源码建议按顺序：GroupBy重载如何返回 Iterator；Iterator 的 MoveNext 何时Lookup.Create；Lookup 的 GetGrouping、Resize 和 Grouping.Add；分组_next与_hashNext的不同用途；JoinIterator 如何CreateForJoin(inner)；GroupJoin 如何把组传给 resultSelector；Aggregate 三类重载如何处理空、seed 与 resultSelector。
审查代码则问：源何时枚举、会枚举几次？哪侧全量缓冲？首项延迟是否可接受？键 comparer 和 null 语义是什么？最大组和重复笛卡尔积有上界吗？selector 是否纯且可重放？历史对象会不会因 Lookup 缓存长期存活？Unity/PLINQ/provider 是否改变执行模型？
十五、总结：把查询写法还原为消费与缓冲
.NET 8GroupBy 调用时返回延迟对象，但第一次枚举会完整消费 source，构建 Lookup。Grouping 同时保存键、动态元素数组、哈希冲突链和分组插入顺序链，因此外组按键首次出现顺序、组内按源顺序输出。ToLookup 则在调用时立即完成同类缓冲。
Join 和 GroupJoin 固定先缓冲 inner。Join 随 outer 流式产生每对匹配，顺序为 outer 后 inner；GroupJoin 对每个 outer 把完整匹配序列交给 resultSelector。重复键会放大输出，inner 无限则永远无法开始。
Aggregate 是立即单遍左折叠：无 seed 空序列抛异常，有 seed 空序列返回 seed，resultSelector 在成功折叠后调用一次。它不建立 Lookup，却不能约束用户 func 的分配、复制和副作用。
理解 LINQ 性能不需要背虚构数字，只需把每个算子还原成：何时消费、缓冲哪一侧、保存多少对象、调用几次委托、结果按何种顺序产生。再用真实键分布、组大小和目标运行时验证，才能决定查询表达式是否适合当前路径。
下一篇：async/await 的编译器重写：状态机、上下文与资源边界
