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

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

1. 🧭 集合接口体系

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

IEnumerable<T>
├─ ICollection<T>
│  ├─ IList<T>
│  └─ ISet<T>
└─ IReadOnlyCollection<T>
   ├─ IReadOnlyList<T>
   └─ IReadOnlySet<T>

IEnumerable<KeyValuePair<TKey, TValue>>
├─ ICollection<KeyValuePair<TKey, TValue>>
│  └─ IDictionary<TKey, TValue>
└─ IReadOnlyCollection<KeyValuePair<TKey, TValue>>
   └─ IReadOnlyDictionary<TKey, TValue>

这是一张能力关系图，不表示每个具体类型只能位于一条分支。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> 等可变接口不能这样转换，否则调用方可能向狗列表中写入其他动物，破坏元素类型约束。

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:    3
Capacity: 8

[A][B][C][ ][ ][ ][ ][ ]

当容量不足时，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> 的核心步骤相似：

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

哈希分布合理且冲突较少时，查找、添加和删除平均接近 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 的枚举顺序。即使某个运行时版本在常见情况下表现出稳定顺序，公共契约也没有把它定义为排序集合。

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

5.1 SortedDictionary 与 SortedList

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

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

数据持续变化时通常选择 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

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

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。

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. ✅ 集合选型顺序

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

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

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

11. 官方资料