3.2 集合类型与选型

3.2 集合类型与选型

本节摘要：集合的性能差异全部来自底层数据结构。本节拆开 List、Dictionary、HashSet、队列栈与链表的内部机制，给出按读写模式选型的决策方法，并补上线程安全集合与并发字典的适用边界。

List 的两副面孔

List<T> 内部就是一个数组加一个计数器。了解它的扩容机制是用好它的前提：

var list = new List<int>();        // 容量从 0 开始
list.Add(1);                        // 容量跳到 4，之后倍增 4→8→16→...
​

每次容量不够，内部分配一个翻倍的新数组并整体拷贝。均摊下来 Add 是常数级，但单次扩容是 O(n) 拷贝，且旧数组立刻变垃圾。两个工程习惯：大小可预估时用构造函数给初始容量（new List<int>(10_000)），一次到位零扩容；频繁在头部插入删除别用 List——数组搬移是 O(n)，这是链表或双端队列的领地。索引访问 O(1)、尾部追加均摊 O(1)、中间插删 O(n)，这三条复杂度就是 List 的能力边界。

数组本身（T[]）与 List 的分工：固定长度、高性能、跨互操作边界用数组；动态长度用 List。多维数组 T[,] 是真正的矩形内存块，交错数组 T[][] 是数组的数组——前者适合固定网格（棋盘、矩阵），后者每行长度可以不同且更省内存（不规则数据）。

Dictionary：哈希的代价与红利

Dictionary<TKey, TValue> 的世界观是"键即地址"：对键调用 GetHashCode 得到散列值，映射到内部桶数组，冲突时桶内挂链。三个复杂度结论：查、插、删均摊 O(1)，与元素总数无关。代价是必须遵守哈希合同：

public readonly struct Money : IEquatable<Money>
{
    public decimal Amount { get; }
    public string Currency { get; }
    public bool Equals(Money other) => Amount == other.Amount && Currency == other.Currency;
    public override int GetHashCode() => HashCode.Combine(Amount, Currency);
}
​

Equals 与 GetHashCode 必须成对实现且逻辑一致：相等的两个对象必须返回相同哈希码，否则字典把它们放进不同的桶，先存后取就"丢失"了——运行时没有任何报错，纯粹是数据进了黑洞。用 record 或 readonly record struct 声明会自动生成正确配对，这是能用 record 就别手写的又一个理由。另一个暗坑：键放进字典后不能再改哈希相关的字段（可变键），改了等于把钥匙换了锁却没搬桶。字符串作键最常见也最安全：不可变、哈希已缓存（第一章伏笔回收）。

字典扩容同样是桶数组倍增加全部重新散列，大字典扩容瞬间的卡顿在高频服务里可测，预估容量同样有效。

HashSet 与 Queue/Stack

HashSet<T> 是"只关心存在性"的字典：去重、集合运算（交并差）、存在性检查 O(1)。对一个大集合反复问"在不在"，List 的 Contains 是 O(n)，HashSet 是 O(1)——万级数据下这是秒与瞬间的差别。Queue<T>（先进先出）与 Stack<T>（后进先出）语义直白：任务调度、广度优先用队列，撤销栈、深度优先用栈。

LinkedList<T> 在 C# 里存在感稀薄：真正的双向链表，头尾插删 O(1)，但随机访问 O(n) 且每个节点都是独立堆对象（GC 压力、缓存不友好）。多数"想用链表"的场景，List 加索引或 Deque 思路都更优。这是选型的重要一课：教科书复杂度相同的结构，在真实硬件上差距悬殊，连续内存的缓存红利经常碾压理论优势。

选型决策表

线程安全：普通集合的雷区

List<T> 与 Dictionary 不是线程安全的：并发写会损坏内部状态，字典在特定并发序列下甚至会死循环（扩容竞争的经典症状是 CPU 打满而不是异常）。并发场景用 System.Collections.Concurrent 家族：ConcurrentDictionary 用细粒度锁（桶级）替代全表锁，读写高并发下吞吐远好于自己包一把大锁；ConcurrentQueue/ConcurrentBag 覆盖常见生产消费模型。读多写少的场景还有一条路：不可变集合（ImmutableList 等）以"每次修改返回新集合 + 结构共享"换取天然的线程安全，代价是写路径的分配。这些并发原语的调度背景在第四章任务并行一节继续展开。

💡 关键直觉：选集合先画读写模式——随机访问还是按键定位？头部插删还是尾部追加？单线程还是共享？三个问题答完，表格里自然只剩一行。

本节要点回顾

• List 是数组：倍增扩容，预估容量免拷贝，头部插删是禁区；
• 字典的哈希合同：Equals 与 GetHashCode 成对实现、键不可变，record 自动达标；
• HashSet 管"在不在"：去重与存在性检查的 O(1) 正解；
• 链表在 C# 里多为错选：缓存不友好加 GC 压力，连续结构常胜；
• 并发必须换家族：Concurrent 系列或不可变集合，普通集合并发写会损坏甚至死循环。

下一节在集合之上架起查询层：LINQ 的延迟执行与表达式树双引擎。