C# 集合

数组长度固定,实际开发绝大多数场景用泛型集合——可动态扩容、类型安全、无装箱。C# 的集合主要在 System.Collections.Generic 命名空间。这一篇我们看四个核心集合:List<T>、Dictionary、HashSet、Queue/Stack。

一、List<T> 动态数组

最常用的集合——内部是个可扩容的数组:

// List<T>:动态数组(最常用)
using System.Collections.Generic;

var nums = new List<int>();
var nums2 = new List<int> { 1, 2, 3 };     // 初始化器
var nums3 = new List<int>(capacity: 100);  // 预分配容量

// 添加
nums.Add(1);
nums.Add(2);
nums.AddRange(new[] { 3, 4, 5 });   // 批量添加
// 1 2 3 4 5

// 插入/删除
nums.Insert(0, 0);        // 在索引 0 处插入 0
nums.Remove(2);            // 删除元素 2(只删第一个)
nums.RemoveAt(0);          // 删除指定索引
nums.Clear();              // 清空

// 查询
int first = nums[0];       // 索引访问
int count = nums.Count;    // 元素个数
bool has = nums.Contains(3);
int idx = nums.IndexOf(3);

// 遍历
foreach (int n in nums2)
    Console.WriteLine(n);

// 转换为只读
var readOnly = nums2.AsReadOnly();

要点:

• 扩容机制:默认容量 4,容量满后翻倍扩容(底层是新建数组+复制)。预知大小用 new List<T>(capacity) 避免多次扩容。
• 随机访问 O(1):索引和数组一样快。
• 末尾增删 O(1)(均摊),中间增删 O(n) 需要移动元素。
• 查找 O(n):用 Contains/IndexOf 线性查找。要快用 HashSet。

二、Dictionary<K, V> 字典

键值对映射,基于哈希表。查找、添加、删除都是 O(1):

// Dictionary<K,V>:键值对映射
var ages = new Dictionary<string, int>
{
    ["Alice"] = 25,
    ["Bob"] = 30
};

// 添加/修改
ages["Charlie"] = 22;      // 不存在则添加,存在则修改
ages.TryAdd("Alice", 99);  // 已存在不修改,返回 false

// 查询
Console.WriteLine(ages["Alice"]);    // 25(不存在抛 KeyNotFoundException)
bool found = ages.TryGetValue("Bob", out int bobAge);  // 安全查询
Console.WriteLine($"{found} {bobAge}");   // True 30

// 检查键/值
ages.ContainsKey("Alice");
ages.ContainsValue(25);

// 删除
ages.Remove("Charlie");
ages.Remove("Alice", out int removed);   // 删除并取出值

// 遍历
foreach (var kv in ages)
    Console.WriteLine($"{kv.Key}: {kv.Value}");

foreach (string key in ages.Keys) { }
foreach (int val in ages.Values) { }

// 注意:Dictionary 遍历顺序不保证(用 SortedDictionary 排序)

要点:

• key 必须唯一:重复 key 抛 ArgumentException。
• key 不可为 null(引用类型):key 必须正确实现 GetHashCode/Equals。
• 安全查询用 TryGetValue:不存在返回 false,不抛异常,推荐。
• 遍历顺序不保证:如需排序用 SortedDictionary。
• 自定义 key:record 类型是理想的 key(自动实现相等比较)。

三、HashSet<T> 集合

无重复元素的集合,基于哈希表:

// HashSet<T>:集合,无重复元素
var set1 = new HashSet<int> { 1, 2, 3, 4 };
var set2 = new HashSet<int> { 3, 4, 5, 6 };

// 添加(重复返回 false,不报错)
set1.Add(5);          // True
set1.Add(1);          // False(已存在)

// 集合运算
var union = new HashSet<int>(set1);
union.UnionWith(set2);      // {1,2,3,4,5,6}

var intersect = new HashSet<int>(set1);
intersect.IntersectWith(set2);  // {3,4}

var except = new HashSet<int>(set1);
except.ExceptWith(set2);        // {1,2}

// 用途:去重、成员检查(O(1))
string[] names = { "Alice", "Bob", "Alice", "Charlie" };
var unique = new HashSet<string>(names);
// {Alice, Bob, Charlie}
bool hasAlice = unique.Contains("Alice");   // O(1),比 List 快

用途:

• 去重:从 List 取 distinct。
• 成员检查:O(1) 检查是否存在,比 List 的 O(n) 快。
• 集合运算:并集、交集、差集。

SortedSet<T> 是有序版本,基于红黑树,适合需要遍历有序的场景。

四、Queue<T> 与 Stack<T>

// Queue<T>:先进先出 FIFO
var q = new Queue<string>();
q.Enqueue("a");      // 入队
q.Enqueue("b");
q.Enqueue("c");

string head = q.Peek();    // "a"(查看队首,不移除)
string item = q.Dequeue(); // "a"(出队)
Console.WriteLine(q.Count);   // 2

// 经典用法:任务队列、BFS 广搜
void BFS()
{
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        // 处理 node
        // queue.Enqueue(子节点)
    }
}

// Stack<T>:后进先出 LIFO
var stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
int top = stack.Pop();   // 3
int peek = stack.Peek(); // 2

// 经典用法:撤销、调用栈、DFS 深搜、表达式求值

Queue 和 Stack 的对比:

• Queue(队列):FIFO 先进先出。任务调度、消息处理。
• Stack(栈):LIFO 后进先出。撤销、回溯、解析表达式。
• 两者都是泛型,无装箱。两端操作都是 O(1)。

线程安全版本:ConcurrentQueue、ConcurrentStack、ConcurrentDictionary。

五、IEnumerable 与接口层次

// IEnumerable<T>:所有集合的共同接口
IEnumerable<int> enumerable = new List<int> { 1, 2, 3 };

// 接口只保证能遍历,不保证其他能力
foreach (int n in enumerable) { }

// 方法参数推荐用 IEnumerable<T>(最宽松)
void Process(IEnumerable<int> nums)
{
    foreach (var n in nums)
        Console.WriteLine(n);
}

// 传 List、Array、HashSet 都行
Process(new List<int> { 1, 2 });
Process(new[] { 1, 2 });
Process(new HashSet<int> { 1, 2 });

// 返回类型推荐 ICollection<T> 或 IReadOnlyList<T>
// 比 IEnumerable 信息更多(有 Count、索引)

// 集合表达式(C# 12+):隐式类型推断
int[] arr = [1, 2, 3];
List<int> list = [1, 2, 3];
HashSet<int> set = [1, 2, 3];
// 同样语法,根据目标类型创建不同集合

集合接口层次(从宽到严):

• IEnumerable<T>:能遍历(最基础)。
• ICollection<T>:能遍历、能 Count、能 Add/Remove。
• IList<T>:加上索引访问。
• IDictionary<K,V>:键值对。
• IReadOnlyList<T>:只读视图。

方法参数推荐用最宽松的接口(如 IEnumerable<T>),返回值用最具体的类型(如 List<T>)。

六、不可变集合

// 只读包装(原集合改了仍可见)
var readOnly = new List<int> {1, 2, 3}.AsReadOnly();

// 真正不可变(改了返回新集合)
using System.Collections.Immutable;

var immutable = ImmutableList<int>.Empty.Add(1).Add(2);
// [1, 2]
var extended = immutable.Add(3);   // [1, 2, 3]
// immutable 还是 [1, 2](不可变)

// 不可变字典
var dict = ImmutableDictionary<string, int>.Empty
    .Add("a", 1)
    .Add("b", 2);

// 适合:多线程共享数据、函数式编程、API 返回值

注意 AsReadOnly vs Immutable 的区别:前者只是包装,改原集合可见;后者是真正不可变。

七、并发集合

// 多线程下用并发集合(无锁或细粒度锁)
using System.Collections.Concurrent;

// 线程安全队列(生产-消费模式)
var queue = new ConcurrentQueue<int>();
queue.Enqueue(1);
queue.TryDequeue(out int item);   // True

// 线程安全字典
var dict = new ConcurrentDictionary<string, int>();
dict.TryAdd("a", 1);
dict.AddOrUpdate("a", 1, (k, v) => v + 1);   // 不存在加 1,存在 v+1

// 线程安全 Bag(无序集合)
var bag = new ConcurrentBag<int>();

// 普通集合多线程用要加锁,复杂且慢
// 优先用 ConcurrentXxx 系列

八、自定义集合与 SortedDictionary

// SortedDictionary<K,V>:按键排序(红黑树)
var sorted = new SortedDictionary<string, int>
{
    ["Banana"] = 1,
    ["Apple"] = 2,
    ["Cherry"] = 3
};
foreach (var kv in sorted)
    Console.WriteLine(kv.Key);   // Apple, Banana, Cherry

// SortedList<K,V>:类似 SortedDictionary,但内部是数组
//   查找 O(log n)、插入 O(n)
//   内存更省,适合少写多查

// SortedSet<T>:有序集合(去重 + 排序)
var ss = new SortedSet<int> { 5, 1, 3, 1 };
// {1, 3, 5}

// 自定义比较器
var byLength = new SortedSet<string>(Comparer<string>.Create(
    (a, b) => a.Length.CompareTo(b.Length)));

九、集合性能对比表

• 索引访问:List O(1)、数组 O(1)、LinkedList O(n)。
• 查找:List/Array O(n)、HashSet/Dictionary O(1)、SortedSet O(log n)。
• 末尾增删:List O(1)均摊、LinkedList O(1)。
• 中间增删:List O(n) 需要移动、LinkedList O(1)(但要先找到位置)。
• 排序:List.Sort() O(n log n)。

选型建议:

• 有序、可索引:List。
• 键值映射:Dictionary。
• 去重/成员检查:HashSet。
• 有序去重:SortedSet。
• FIFO:Queue。
• LIFO:Stack。
• 并发:ConcurrentXxx。
• 不可变:ImmutableXxx。

十、迭代器 yield

自定义集合或懒加载场景,用 yield return 实现迭代器:

// 返回 IEnumerable<T>,无需手动建 List
public IEnumerable<int> EvenNumbers(int max)
{
    for (int i = 0; i <= max; i += 2)
        yield return i;
}

// 使用:延迟执行,节省内存
foreach (int n in EvenNumbers(100))
    Console.WriteLine(n);

// 无限序列也可以(因为延迟执行)
public IEnumerable<int> Naturals()
{
    int i = 1;
    while (true)
        yield return i++;
}

// 取前 10 个
foreach (int n in Naturals().Take(10))
    Console.WriteLine(n);

yield 是 LINQ 延迟执行的基石。下一篇讲 LINQ 时你会更深入体会。

小结

集合是日常用得最多的类型。记住选型表:List 排队、Dictionary 映射、HashSet 去重、Queue 排队、Stack 叠盘。方法参数用 IEnumerable,并发用 ConcurrentXxx,不可变用 ImmutableXxx。下一篇进入 LINQ——把这些集合玩出花的核心特性。

← 上一篇 C# 接口

下一篇 C# LINQ →