深入理解 C# 集合：接口、实现与选型

.NET 集合可以分成两个维度：接口描述能够做什么，实现决定这些操作如何完成。同一个 IEnumerable<T> 可能来自数组、哈希表、数据库查询或延迟生成器，仅凭接口不能判断它是否支持索引、修改、重复枚举或线程安全。

本文以 .NET 10 的 BCL（基础类库）API 和运行时实现为基线。正文中的类型在 .NET 10 均可使用；如果项目面向更早的目标框架，可在第 12 节查看部分较新类型的首次引入版本。

本文关注集合体系和实现原理。容量预估、CollectionsMarshal、ArrayPool<T> 等性能技巧见 C# 高性能写法（四）：集合。

1. 🧭 集合接口体系

泛型集合接口可以简化为下面几条主线：

集合接口描述能力，具体类型可以跨分支实现实线表示接口能力继承；下方虚线表示一个具体类型同时满足多种能力契约。

图中从 IEnumerable 分出可变集合和只读集合能力。List 同时连接 IList 与 IReadOnlyList，HashSet 同时连接 ISet 与 IReadOnlySet。

这是一张能力关系图，不表示每个具体类型只能位于一条分支。List<T> 同时实现 IList<T> 和 IReadOnlyList<T>，HashSet<T> 同时实现 ISet<T> 和 IReadOnlySet<T>。

接口	提供的主要能力	不保证什么
`IEnumerable<T>`	按顺序获取元素	数量、索引、修改、多次枚举成本
`ICollection<T>`	`Count`、添加、删除、清空、包含判断	按索引访问
`IList<T>`	顺序、索引读取和写入、按位置插入删除	操作复杂度
`IReadOnlyCollection<T>`	枚举和 `Count`	底层对象永远不变化
`IReadOnlyList<T>`	只读索引访问	不可变快照
`ISet<T>`	唯一元素、并集、交集、差集	稳定顺序
`IReadOnlySet<T>`	只读成员判断和集合关系判断	不可变实现
`IDictionary<TKey, TValue>`	通过唯一键读写值	键的排序或枚举顺序
`IReadOnlyDictionary<TKey, TValue>`	通过键只读访问	底层字典不会被其他引用修改

1.1 IEnumerable 只承诺枚举

接收 IEnumerable<T> 的方法只能假定数据可以被枚举：

static decimal Sum(IEnumerable<Order> orders)
{
    decimal total = 0;

    foreach (Order order in orders)
    {
        total += order.Amount;
    }

    return total;
}

传入对象可能是内存集合，也可能是执行查询或动态生成数据的迭代器。调用 Count() 后再 foreach 可能枚举两次，因此需要数量时应直接声明 IReadOnlyCollection<T>，需要索引时声明 IReadOnlyList<T>。

1.2 只读接口不等于不可变

只读接口限制的是当前引用能执行的操作，不能阻止其他引用修改原集合：

var source = new List<string> { "A" };
IReadOnlyList<string> view = source;

source.Add("B");

Console.WriteLine(view.Count); // 2

如果调用方需要不会变化的快照，应复制为数组或使用不可变集合，而不是只把 List<T> 转成 IReadOnlyList<T>。

1.3 可变接口通常不能协变

IEnumerable<out T> 和多个只读接口支持协变，因此 IEnumerable<Dog> 可以作为 IEnumerable<Animal> 使用。IList<T> 等可变接口不能这样转换，否则调用方可能向狗列表中写入其他动物，破坏元素类型约束。

1.4 延迟执行与物化：什么时候值得 ToList()

IEnumerable<T> 可能代表尚未执行的查询或计算。每次枚举都可能重新访问数据源、重新计算，甚至再次触发副作用；如果结果需要遍历多次，先物化成快照通常更清晰：

IReadOnlyList<Order> snapshot = query.ToList();

decimal total = snapshot.Sum(static order => order.Amount);
int count = snapshot.Count;

需要固定长度和紧凑存储时可用 ToArray()；后续还要在内存中增删时用 ToList()。物化只复制容器和当时的元素引用，不会自动深拷贝元素，也不应为了“保险”对所有查询无条件调用 ToList()。

2. 🗂️ 常见集合实现总览

集合	核心结构	适合场景	主要限制
`T[]`	连续定长数组	固定数量、索引和顺序遍历	长度不能改变
`List<T>`	可扩容连续数组	通用顺序集合	中间插入删除需要移动元素
`LinkedList<T>`	双向链表	已持有节点时频繁插入删除	查找慢、节点分配多、局部性较差
`Queue<T>`	循环数组	先进先出	不适合任意位置操作
`Stack<T>`	动态数组	后进先出	只高效操作栈顶
`PriorityQueue<TElement, TPriority>`	堆	反复取出当前最高优先级元素	不提供完整排序结果
`Dictionary<TKey, TValue>`	哈希表	按键快速查找	依赖稳定键和正确哈希
`HashSet<T>`	哈希表	去重、成员判断、集合运算	不保证排序
`SortedDictionary<TKey, TValue>`	平衡搜索树	持续更新且始终按键有序	单次操作通常为 O(log n)
`SortedList<TKey, TValue>`	有序数组	数据较稳定、读取和按位置访问较多	插入删除需要移动元素
`SortedSet<T>`	平衡搜索树	有序且唯一的元素	不支持按索引访问
`ImmutableList<T>` 等	持久化数据结构	快照、共享状态、函数式更新	修改会创建新版本并有额外成本
`FrozenDictionary` / `FrozenSet`	创建时针对读取优化	创建一次、长期高频查询	构建较慢且不能更新
`ConcurrentDictionary` 等	并发数据结构	多线程共享读写	有同步和协调成本

接口名称描述语义，实现类型决定时间复杂度和内存布局。例如 List<T> 和 LinkedList<T> 都是顺序集合，但“在中间插入元素”是否高效，取决于是否已经持有链表节点，而不是取决于它们都能枚举。

3. 📦 顺序集合的实现原理

3.1 数组与 List

数组长度固定，元素连续存储。按索引访问只需要根据起始位置和索引计算地址，复杂度为 O(1)，连续内存也有利于 CPU 缓存和运行时优化。

List<T> 在数组之上增加了元素数量和容量管理：

容量已经用满Count 与 Capacity 都是 4；新元素 E 暂时没有存储位置。

1 / 4

List<T> 扩容过程扩容不是每次 Add 都发生，因此尾部追加是均摊 O(1)。

当容量不足时，List<T> 需要分配更大的数组并复制已有元素，所以尾部 Add 是均摊 O(1)，不是每一次都严格 O(1)。在中间插入或删除时，后面的元素需要整体移动，复杂度为 O(n)。

不要依赖具体扩容倍数，它属于实现细节。公共语义只有 Count 表示元素数量，Capacity 表示当前内部存储无需扩容时能够容纳的数量。

数组也实现 IList<T>，但大小固定。通过接口调用 Add、Remove 等改变数量的操作会抛出 NotSupportedException。因此“实现了可变集合接口”不代表所有操作都一定可用，仍需检查 IsReadOnly 和具体类型契约。

3.2 LinkedList

LinkedList<T> 的每个节点保存值以及前后节点引用。已经持有 LinkedListNode<T> 时，插入和删除只需要修改附近引用，复杂度为 O(1)：

LinkedListNode<Job>? current = jobs.Find(target);

if (current is not null)
{
    jobs.AddAfter(current, newJob);
}

但 Find 本身仍是 O(n)。如果每次操作前都要从头查找，链表没有消除查找成本。节点对象还会增加分配、引用和缓存未命中的成本，所以在现代 .NET 代码中，List<T> 往往仍是更合适的默认顺序集合。

3.3 Queue 与 Stack

当前 Queue<T> 使用循环数组，通过头尾索引复用数组空间；Stack<T> 使用动态数组并只操作末端。它们限制了操作位置，换来了清晰语义和均摊 O(1) 的入队、出队、入栈、出栈操作。

不要用 List<T>.RemoveAt(0) 模拟队列。删除第一个元素会移动其余所有元素，而 Queue<T>.Dequeue() 不需要进行这种整体移动。

4. 🔑 哈希集合的实现原理

Dictionary<TKey, TValue> 和 HashSet<T> 的核心步骤相似：

使用比较器计算键或元素的哈希值。
根据哈希值定位桶。
在桶对应的冲突链中比较哈希值和相等性。
找到条目，或确定它不存在。

计算稳定哈希值比较器根据键 orders:42 计算哈希值；相等的键必须得到相同结果。

1 / 4

Dictionary 哈希查找路径平均 O(1) 来自缩小候选范围，不代表永远只比较一次。

哈希分布合理且冲突较少时，查找、添加和删除平均接近 O(1)。发生大量冲突时，同一个桶需要检查更多条目，最坏情况可以退化到 O(n)。因此 O(1) 是平均复杂度，不是无条件保证。

4.1 相等比较器决定键的身份

字符串键应直接提供符合业务语义的比较器：

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

哈希集合要求：如果两个值相等，它们必须产生相同的哈希值。对象加入集合后，也不能再改变参与 Equals 和 GetHashCode 的字段，否则它仍位于旧桶中，后续可能无法被找到。

4.2 Dictionary 与 HashSet 的区别

Dictionary<TKey, TValue> 保存键到值的映射，HashSet<T> 只保存唯一元素。需要去重、成员判断、交集或并集时，HashSet<T> 比“值没有意义的 Dictionary”更准确：

var permissions = new HashSet<string>(
    StringComparer.OrdinalIgnoreCase);

permissions.UnionWith(rolePermissions);
permissions.ExceptWith(disabledPermissions);

不要依赖 Dictionary 或 HashSet 的枚举顺序。即使某个运行时版本在常见情况下表现出稳定顺序，公共契约也没有把它定义为排序集合。

4.3 一键多值：`ILookup` 还是 `Dictionary<TKey, List<TValue>>`

按部门分组员工、按订单聚合明细时，一个键往往对应多个值。GroupBy 默认延迟执行，ToLookup() 则会立即构建一个只读的 ILookup<TKey, TElement>；适合“一次构建、反复查询”，查询不存在的键会得到空序列：

ILookup<int, Employee> employeesByDepartment =
    employees.ToLookup(static employee => employee.DepartmentId);

foreach (Employee employee in employeesByDepartment[departmentId])
{
    Console.WriteLine(employee.Name);
}

如果业务需要持续添加、删除或更新某个键下的成员，Dictionary<TKey, List<TValue>> 更直接，但需要自己处理缺少的键、列表初始化和空列表清理。选择的关键是“构建后只读查询”还是“运行期间持续维护”。

5. 🌳 有序集合与优先级队列

5.1 SortedDictionary 与 SortedList

两者都会按键排序，但实现和成本不同：

操作	`SortedDictionary`	`SortedList`
底层结构	平衡搜索树	排序后的键数组和值数组
按键查找	O(log n)	O(log n)，使用二分查找
中间插入删除	O(log n)	O(n)，需要移动元素
内存布局	节点和引用较多	连续、紧凑
按位置访问	不擅长	可通过 `Keys[index]`、`Values[index]` 访问

数据持续变化时通常选择 SortedDictionary；数据主要在初始化阶段写入，之后大量读取时，SortedList 的紧凑存储可能更合适。

如果既要维护键值对的顺序，又要按键快速查找，OrderedDictionary<TKey, TValue> 自 .NET 9 起可用。它的“有序”表示条目拥有可维护的顺序，并不表示会自动按键排序；需要按键持续排序时仍应选择 SortedDictionary 或 SortedList。

SortedSet<T> 同样维持排序和唯一性，适合范围查询、最小值、最大值以及有序集合运算。

5.2 PriorityQueue 不是排序列表

PriorityQueue<TElement, TPriority> 的当前实现使用四叉最小堆。默认比较器下，较小的优先级值先出队：

var jobs = new PriorityQueue<Job, int>();

jobs.Enqueue(normalJob, 10);
jobs.Enqueue(urgentJob, 1);

Job next = jobs.Dequeue(); // urgentJob

堆只维护父节点与子节点之间的局部顺序，因此：

Peek 为 O(1)。
Enqueue 和 Dequeue 为 O(log n)。
枚举内部元素不会得到完整排序结果。
相同优先级的元素不保证按插入顺序出队。

需要不断加入任务并取出当前最优项时使用 PriorityQueue；需要完整排序结果时使用排序操作或有序集合。

6. 🧊 只读、不可变与 Frozen

这三类集合都能阻止调用方直接修改，但语义和成本不同。

只读、Immutable 与 Frozen 解决不同问题只读限制入口，Immutable 保留版本，Frozen 用一次构建换取长期读取。

只读包装和原集合指向同一份数据。Immutable 修改后产生新版本并共享未变化结构。Frozen 在构建阶段分析数据，之后保持固定并优化查询。

6.1 只读接口与包装

IReadOnlyList<T>、IReadOnlyDictionary<TKey, TValue> 只描述访问能力。ReadOnlyCollection<T> 和 ReadOnlyDictionary<TKey, TValue> 则包装已有集合，底层集合变化时，包装看到的内容也会变化。

它们适合限制 API 表面，不适合表示历史快照或跨线程稳定状态。

6.2 Immutable 集合

不可变集合不能原地修改。Add、SetItem 等操作返回新集合，旧版本仍然有效：

ImmutableDictionary<string, int> first =
    ImmutableDictionary<string, int>.Empty.Add("A", 1);

ImmutableDictionary<string, int> second = first.Add("B", 2);

实现会共享未变化的内部结构，而不是每次完整复制全部元素。它适合配置快照、撤销历史和跨线程共享状态。需要批量构建时，可以使用 Builder 减少连续创建中间版本的成本。

6.3 Frozen 集合

FrozenDictionary<TKey, TValue> 和 FrozenSet<T> 在创建阶段分析数据，为后续读取构建优化结构。它们适合路由表、命令映射、协议常量等“创建一次、读取很多次”的数据：

FrozenDictionary<string, Handler> handlers = source
    .ToFrozenDictionary(
        static item => item.Name,
        static item => item.Handler,
        StringComparer.Ordinal);

Frozen 集合的构建成本通常高于普通哈希集合，而且创建后不能更新。它不是 Immutable 集合的替代品：Immutable 关注持续生成新版本，Frozen 关注冻结后的读取效率。

7. 🔒 并发集合

并发集合允许多个线程共享访问，但不同类型解决的问题不同：

集合	主要语义
`ConcurrentDictionary<TKey, TValue>`	并发键值读取、添加和更新
`ConcurrentQueue<T>`	多生产者、多消费者的先进先出队列
`ConcurrentStack<T>`	并发后进先出栈
`ConcurrentBag<T>`	无序集合，偏向同一线程放入和取回元素的场景
`BlockingCollection<T>`	在并发集合上增加阻塞、容量限制和生产消费协调

不要把“线程安全”理解为多步业务操作自动具备事务性：

if (!cache.ContainsKey(key))
{
    cache[key] = CreateValue(key);
}

即使 cache 是 ConcurrentDictionary<TKey, TValue>，检查和写入仍是两个操作。应使用 GetOrAdd、AddOrUpdate、TryUpdate 等复合 API。

两个线程分别检查线程 A 和 B 都可能在写入前观察到键不存在。

1 / 4

ConcurrentDictionary 的原子边界线程安全保护集合自身；跨多个调用的业务不变量仍需要复合 API 或外部同步。

GetOrAdd 和 AddOrUpdate 接收的委托可能在竞争中执行多次，且委托不会作为一个整体在字典锁内运行。委托中不要直接执行扣款、发送消息等只能发生一次的副作用。

并发枚举可以保证集合结构不会因同时修改而损坏，但不应一概视为事务性一致快照；具体可见内容因集合类型而异。确实需要某一时刻的稳定副本时，显式调用相应的 ToArray 或在外部建立同步边界。

如果消费者需要异步等待、背压和完成通知，通常应考虑 Channel<T>，而不是围绕 ConcurrentQueue<T> 自己编写轮询循环。

8. 🔄 枚举器与接口设计

8.1 foreach 背后是枚举器

foreach 会获取枚举器并反复调用 MoveNext()。List<T> 等集合提供结构体枚举器，直接针对具体类型遍历时通常无需为枚举器分配对象：

foreach (Order order in orders)
{
    Process(order);
}

把集合转换为接口后，结构体枚举器可能发生装箱。不过接口抽象通常比这点成本更有设计价值，只有性能分析确认它位于热路径时，才值得改用具体类型、数组或 Span。

大部分普通可变集合会记录版本号。在枚举期间修改集合，枚举器通常会抛出 InvalidOperationException，避免继续遍历已经变化的结构。需要修改时，可以先收集待处理项、反向遍历索引，或使用专门的并发集合。

8.2 参数暴露需要的最小能力

方法参数应描述方法真正需要的能力：

void Print(IEnumerable<Order> orders);
void PrintCount(IReadOnlyCollection<Order> orders);
Order GetFirst(IReadOnlyList<Order> orders);
bool TryFind(
    IReadOnlyDictionary<int, Order> orders,
    int id,
    out Order? order);

只枚举就不要要求 List<T>，只读取就不要要求可变接口。这样调用方可以传入数组、列表、不可变集合或自定义实现。

返回集合时还要表达所有权：返回内部 List<T> 会让调用方直接修改内部状态；返回只读包装只限制当前入口；返回数组副本或不可变集合才提供独立快照。应根据语义选择，而不是统一返回 IEnumerable<T> 隐藏所有细节。

9. 📊 常见操作复杂度

下表描述典型实现的常见复杂度，不包含扩容、异常哈希冲突和比较器成本等特殊情况：

集合	索引访问	查找	添加	删除	保持排序
数组	O(1)	O(n)	不支持改变长度	不支持改变长度	否
`List<T>`	O(1)	O(n)	尾部均摊 O(1)，中间 O(n)	O(n)	否
`LinkedList<T>`	O(n)	O(n)	已知节点时 O(1)	已知节点时 O(1)	否
`Dictionary<TKey, TValue>`	不适用	平均 O(1)	平均 O(1)	平均 O(1)	否
`HashSet<T>`	不适用	平均 O(1)	平均 O(1)	平均 O(1)	否
`SortedDictionary<TKey, TValue>`	不适用	O(log n)	O(log n)	O(log n)	是
`SortedList<TKey, TValue>`	按位置 O(1)	O(log n)	O(n)	O(n)	是
`SortedSet<T>`	不适用	O(log n)	O(log n)	O(log n)	是
`Queue<T>` / `Stack<T>`	仅端点 O(1)	O(n)	均摊 O(1)	均摊 O(1)	否
`PriorityQueue<TElement, TPriority>`	仅队首 O(1)	O(n)	O(log n)	队首 O(log n)	仅保证队首

复杂度不是全部。数据量很小时，连续数组的简单遍历可能比哈希或树结构更快；节点结构虽然有更好的理论插入复杂度，但可能付出更多内存和缓存成本。

10. ✅ 集合选型顺序

可以按下面的顺序缩小选择范围：

先确定语义，再匹配最频繁的操作从上到下检查需求；命中明确语义后通常无需继续寻找所谓“更快”的集合。

从固定数量、顺序访问、端点语义、按键查找、唯一性、有序性、快照、长期读取和并发写入九类问题，分别连接到对应集合。

数量是否固定？ 固定并需要索引，使用数组。
是否主要按顺序遍历和索引？ 默认使用 List<T>。
是否需要先进先出或后进先出？ 使用 Queue<T> 或 Stack<T>。
是否需要按键查找？ 使用 Dictionary<TKey, TValue>。
是否只需要唯一元素和集合运算？ 使用 HashSet<T>。
是否必须始终有序？ 根据更新频率选择 SortedDictionary、SortedList 或 SortedSet。
是否只需要不断取出当前最优元素？ 使用 PriorityQueue。
是否需要稳定快照或共享不可变状态？ 使用数组副本或 Immutable 集合。
是否创建一次后长期查询？ 测量后考虑 Frozen 集合。
是否确实存在多线程共享写入？ 再选择并发集合，并优先使用它提供的原子复合操作。

10.1 典型业务场景速查

业务场景	首选起点	关键原因
按 ID 查对象	`Dictionary<TKey, TValue>`	直接表达唯一键到对象的映射
去重且保留首次出现顺序	`HashSet<T> + List<T>`	用集合判断是否见过，再用列表保存顺序
大小写不敏感的名称或请求头	`Dictionary<string, TValue>` + `StringComparer.OrdinalIgnoreCase`	比较器决定业务上的“相同键”
配置快照或跨线程共享状态	数组副本或 `Immutable*`	明确快照边界，避免外部引用继续修改
任务按优先级取出	`PriorityQueue<TElement, TPriority>`	只维护当前最优项，不必维护完整排序
异步生产者消费者与背压	有界 `Channel<T>`	支持异步等待、容量限制和完成通知

这张表提供的是默认起点；真正的热点路径仍应结合数据规模、访问比例和基准测试确认。

集合选型的关键不是寻找“最快的集合”，而是先确定代码需要什么语义，再让数据结构匹配最频繁的操作。接口负责守住能力边界，实现负责兑现复杂度和内存成本。

11. ⚠️ 常见误区速查

误区	实际含义
`IReadOnlyList<T>` 不是不可变集合	它可能只是指向仍会变化的 `List<T>` 视图
`List<T>.RemoveAt(0)` 可以当队列	每次都会移动剩余元素，应使用 `Queue<T>`
`ContainsKey` 后再用索引器最稳妥	获取值时可能重复查找，优先使用 `TryGetValue`
可变对象适合作为哈希键	改变参与相等比较的字段后，集合可能再也找不到它
并发集合等于业务操作原子化	多步检查和写入仍需复合 API 或外部同步
`Dictionary` / `HashSet` 天然有稳定顺序	需要排序或顺序契约时应显式选择有序集合

12. 🧩 版本前置条件

本文其余内容均按 .NET 10 理解。下表列出文中几类较新集合 API 首次进入 .NET 主线版本的时间，便于维护旧项目时判断能否直接使用。

API 或类型	首次引入版本	适用说明
`IReadOnlySet<T>`	.NET 5	只读集合接口；参见官方 API
`PriorityQueue<TElement, TPriority>`	.NET 6	四叉最小堆；参见 .NET 6 新增内容
`FrozenDictionary<TKey, TValue>` / `FrozenSet<T>`	.NET 8	面向创建一次、长期读取；参见 .NET 8 运行时新增内容
`OrderedDictionary<TKey, TValue>`	.NET 9	泛型、维护条目顺序并支持按键查找；参见 .NET 9 集合新增内容
`System.Collections.Immutable`	NuGet 包 / 共享框架	.NET 10 通常无需额外引用；旧目标框架可通过同名包获得较新 API，参见 NuGet 包兼容规则

“首次引入版本”不等于最低推荐版本。本文示例以 .NET 10 为准，旧项目还应结合目标框架、包引用和实际 API 的 Applies to 信息确认兼容性。

1. 🧭 集合接口体系

1.1 IEnumerable 只承诺枚举

1.2 只读接口不等于不可变

1.3 可变接口通常不能协变

1.4 延迟执行与物化：什么时候值得 ToList()

2. 🗂️ 常见集合实现总览

3. 📦 顺序集合的实现原理

3.1 数组与 List

3.2 LinkedList

3.3 Queue 与 Stack

4. 🔑 哈希集合的实现原理

4.1 相等比较器决定键的身份

4.2 Dictionary 与 HashSet 的区别

4.3 一键多值：ILookup 还是 Dictionary<TKey, List<TValue>>

5. 🌳 有序集合与优先级队列

5.1 SortedDictionary 与 SortedList

5.2 PriorityQueue 不是排序列表

6. 🧊 只读、不可变与 Frozen

6.1 只读接口与包装

6.2 Immutable 集合

6.3 Frozen 集合

7. 🔒 并发集合

8. 🔄 枚举器与接口设计

8.1 foreach 背后是枚举器

8.2 参数暴露需要的最小能力

9. 📊 常见操作复杂度

10. ✅ 集合选型顺序

10.1 典型业务场景速查

11. ⚠️ 常见误区速查

12. 🧩 版本前置条件

13. 官方资料

4.3 一键多值：`ILookup` 还是 `Dictionary<TKey, List<TValue>>`