C# 泛型与集合

学习目标

完成本章学习后，读者应当能够达到以下认知层级（参照 Bloom 分类法）：

• 记忆（Remembering）：复述 C# 泛型的核心概念（类型参数、约束、实例化、类型擦除对比），列举 System.Collections.Generic 命名空间下的主要集合类型（List<T>、Dictionary<TKey,TValue>、HashSet<T>、Queue<T>、Stack<T>、LinkedList<T>、PriorityQueue<TElement,TPriority>、SortedDictionary<TKey,TValue>、SortedSet<T>）。
• 理解（Understanding）：解释泛型在 CLR 中的实例化机制（值类型各自实例化、引用类型共享实例化），阐述协变（out）与逆变（in）的类型安全保证；说明 List<T> 的动态扩容策略、Dictionary<TKey,TValue> 的哈希桶结构、HashSet<T> 的位图优化。
• 应用（Applying）：编写带有多重约束的泛型类与方法，实现自定义 IComparer<T>、IEqualityComparer<T>、IEnumerable<T>；使用 yield return 构建惰性迭代器；选择合适的集合类型满足性能与语义需求。
• 分析（Analyzing）：解构泛型类型的类型推断与重载解析过程；分析 List<T>.Add 的均摊复杂度、Dictionary 哈希冲突的解决策略；对比 List<T>、LinkedList<T>、Array 在不同访问模式下的缓存局部性。
• 评价（Evaluating）：评估泛型约束设计的合理性（避免过紧耦合），审查自定义集合类型的线程安全与不变量保护；对比 ImmutableArray<T>、ImmutableList<T>、FrozenDictionary<TKey,TValue> 在只读场景下的性能权衡。
• 创造（Creating）：基于泛型设计领域特定的集合类型（如 BoundedQueue<T>、LruCache<TKey,TValue>、CircularBuffer<T>）；构建支持 LINQ 与异步遍历的自定义集合；为高吞吐场景设计无锁并发集合。

历史动机与背景

泛型的诞生：类型安全的复用

在泛型出现之前，复用容器代码只能依赖 System.Object 与装箱拆箱（boxing/unboxing）。.NET 1.x 的 ArrayList、Hashtable、Queue、Stack 接收 object，存在三类严重问题：

1. 类型安全丧失：ArrayList 可同时装入 string、int、DateTime，运行时才会暴露类型错误。
2. 性能损耗：值类型装入 ArrayList 需装箱为 object，读取时拆箱，伴随堆分配与类型检查。int 装箱在 32 位系统上从 4 字节膨胀为 12 字节（对象头 + 方法表指针 + 数据）。
3. 代码可读性差：开发者需手动类型转换，编译期无法保证正确性。

2005 年，Don Syme 等人在 .NET 2.0 中引入泛型（Generics），同时由 C# 2.0、CLR 2.0 提供语言与运行时支持。设计目标：

• 编译期类型检查：错误前置到编译阶段，避免运行时 InvalidCastException。
• 零装箱开销：值类型实例化为专用代码，无 object 转换。
• 代码复用：一份算法实现可适用于多种类型，保留类型信息。

CLR 泛型 vs Java 泛型

C# 泛型与 Java 泛型（2004 年 Java 5 引入）走出了两条截然不同的路径：

• CLR 泛型（reified generics）：类型参数在运行时存在，typeof(List<int>) 与 typeof(List<string>) 是不同的 Type 对象。值类型泛型由 CLR 为每种值类型生成专用代码（如 List<int> 与 List<double> 是两个不同的 JIT 编译产物）；引用类型泛型共享同一份代码（List<string> 与 List<object> 共用方法实现，因引用都是 8 字节指针）。
• Java 泛型（type erasure）：类型参数仅存在于编译期，编译后被擦除为 Object。List<String> 与 List<Integer> 在运行时是同一个 List 类型。这导致无法 new T()、无法 instanceof List<String>、基本类型必须装箱（List<Integer> 而非 List<int>）。

CLR 选择 reified 的代价是元数据膨胀与潜在的代码膨胀，但获得了运行时类型信息与值类型零装箱的关键优势。

集合库的演进

• .NET 1.0（2002）：System.Collections 命名空间，非泛型 ArrayList、Hashtable、Queue、Stack、SortedList，基于 object。
• .NET 2.0（2005）：System.Collections.Generic，泛型 List<T>、Dictionary<TKey,TValue>、Queue<T>、Stack<T>、LinkedList<T>、SortedDictionary<TKey,TValue>、SortedList<TKey,TValue>、HashSet<T>（3.5 后）。
• .NET 3.5（2007）：HashSet<T>、Lookup<TKey,TElement>、扩展方法与 LINQ。
• .NET 4.0（2010）：System.Collections.Concurrent，ConcurrentDictionary<TKey,TValue>、ConcurrentQueue<T>、ConcurrentBag<T>、BlockingCollection<T>。
• .NET 4.5（2012）：IReadOnlyList<T>、IReadOnlyDictionary<TKey,TValue>、IReadOnlyCollection<T>。
• .NET 4.6（2015）：Array.Empty<T>()、Span<T> 萌芽。
• .NET Core 2.0（2017）：Span<T>、Memory<T>、ReadOnlySpan<T>。
• .NET Core 3.0（2019）：Stack<T> 内部优化为基于数组的紧凑布局。
• .NET 5（2020）：集合性能大幅优化，List<T>.AddRange 改进、Dictionary 内部结构升级。
• .NET 6（2021）：PriorityQueue<TElement,TPriority> 引入，基于最小堆。
• .NET 8（2023）：FrozenDictionary<TKey,TValue>、FrozenSet<T>，针对只读场景优化查询性能；CollectionView、SortedDictionary 改进。
• .NET 9（2024）：OrderedDictionary<TKey,TValue>（泛型版）、ReadOnlySet<T>、集合表达式（[] 与 ..）增强。

C# 12（2023）引入集合表达式（Collection Expressions），统一了数组、List<T>、Span<T>、IEnumerable<T> 的初始化语法，消除了历史遗留的多套初始化风格。

形式化定义

泛型类型的形式化模型

泛型类型可形式化为类型构造器（type constructor）。设类型宇宙 $\mathcal{U}$，泛型类型 $G$ 是从类型参数到具体类型的函数：

其中 $n$ 是类型参数个数。例如 List<T> 是 $n=1$ 的类型构造器，Dictionary<TKey, TValue> 是 $n=2$。

实例化：给定类型实参 $T_1, T_2, \ldots, T_n \in \mathcal{U}$，实例化类型为 $G\langle T_1, \ldots, T_n \rangle \in \mathcal{U}$。CLR 在运行时为每个不同的实例化创建独立的 Type 对象：

子类型化与协变逆变

设 $F$ 是类型构造器，$S \preceq T$ 表示子类型关系。

• 协变（Covariant）：$F$ 协变当且仅当 $S \preceq T \Rightarrow F\langle S \rangle \preceq F\langle T \rangle$
• 逆变（Contravariant）：$F$ 逆变当且仅当 $S \preceq T \Rightarrow F\langle T \rangle \preceq F\langle S \rangle$
• 不变（Invariant）：既不协变也不逆变

C# 使用 out 标记协变类型参数（仅出现在输出位置），in 标记逆变类型参数（仅出现在输入位置）：

类型安全证明（协变）：设 IProducer<out T> 有方法 T Produce()。若 StringProducer : IProducer<string>，则 string Produce() 满足。将 IProducer<string> 视为 IProducer<object> 调用 Produce() 返回 string，可安全转为 object。类型安全成立。

类型安全反例（若 List<T> 协变）：若 List<string> 可视为 List<object>，则 list.Add(42) 会向 string 数组写入 int，运行时崩溃。故 List<T> 必须不变。

集合的代数结构

集合类型可视为代数结构 $(S, \oplus, \ominus, \cap, \cup)$，其中 $S$ 是元素集合，运算定义为：

• 插入 $\oplus : S \times E \to S$
• 删除 $\ominus : S \times E \to S$
• 并集 $\cup : S \times S \to S$
• 交集 $\cap : S \times S \to S$
• 差集 $\setminus : S \times S \to S$

不同集合类型对运算的实现复杂度差异显著：

哈希函数的形式化

Dictionary<TKey, TValue> 与 HashSet<T> 基于哈希表。哈希函数 $h : K \to \mathbb{Z}_m$，其中 $m$ 是桶数。理想哈希函数满足：

1. 均匀分布：$\forall i, P(h(k) = i) \approx 1/m$
2. 雪崩效应：输入微小变化导致输出大幅变化
3. 确定性：相同输入恒定输出

冲突解决：CLR 采用链地址法（separate chaining），每个桶维护一个链表。装载因子 $\alpha = n/m$，查找复杂度为 $O(1 + \alpha)$。当 $\alpha$ 超过阈值（默认 0.72 或 1.0 视集合而定）时触发扩容：$m \to 2m + 1$（质数），重新哈希所有元素，均摊 $O(1)$。

理论推导

List<T> 动态扩容的均摊分析

List<T> 内部维护数组 _items，初始容量为 0 或构造时指定。Add 操作：

1. 若 Count < Capacity，直接写入 _items[Count++]，$O(1)$。
2. 若 Count == Capacity，扩容：Array.Resize 分配新数组（容量翻倍 + 1），复制旧元素，再写入。扩容代价 $O(n)$。

均摊复杂度：设扩容序列为 $c_0 = 0, c_1 = 1, c_2 = 2, c_3 = 4, \ldots, c_k = 2^{k-1}$。前 $n$ 次插入的总代价：

均摊每次插入：$T(n) / n = O(1)$。

容量预分配优化：若已知最终元素数 $n$，构造时使用 new List<T>(n) 或调用 EnsureCapacity(n)，避免 $O(\log n)$ 次扩容与复制，总代价降至 $O(n)$（系数减半）。

Dictionary 哈希冲突的概率分析

设哈希表桶数 $m$，元素数 $n$，哈希函数均匀分布。生日问题给出至少一对冲突的概率：

当 $n \approx \sqrt{m}$ 时，冲突概率约 50%。链地址法下，单桶链表长度的期望为 $\alpha = n/m$，查找复杂度 $O(1 + \alpha)$。

.NET 实现：Dictionary 在装载因子超过 0.72（默认）时扩容至下一个质数。质数选择避免哈希值与桶数的公约数导致的聚集（clustering）。CLR 维护质数表 HashHelpers.primes，扩容时查找下一个质数。

哈希碰撞攻击：若攻击者能构造大量哈希相同的键，将 Dictionary 退化为 $O(n)$ 查找的链表，引发 DoS。.NET 4.5+ 引入随机化字符串哈希（UseRandomizedStringHashAlgorithm），每次应用启动使用不同种子。

SortedDictionary 的红黑树复杂度

SortedDictionary<TKey, TValue> 基于红黑树（Red-Black Tree），保证：

• 树高 $h \leq 2 \log_2(n+1)$
• 插入、删除、查找均为 $O(\log n)$
• 有序遍历 $O(n)$

红黑树通过五条不变量维护平衡：

1. 节点是红色或黑色
2. 根节点是黑色
3. 叶子（NIL）是黑色
4. 红色节点的子节点必须是黑色（不能连续两个红）
5. 从任一节点到其所有叶子节点的路径包含相同数量的黑色节点

这些约束保证最长路径不超过最短路径的两倍，确保 $O(\log n)$ 高度。

协变逆变的类型推断

C# 编译器在方法调用时进行类型推断。设方法签名：

TResult Select<TSource, TResult>(IEnumerable<TSource> source, Func<TSource, TResult> selector)

调用 Select(list, x => x.ToString()) 时，编译器推断：

1. list 类型为 List<int>，List<int> 实现 IEnumerable<int>，推断 TSource = int
2. Lambda x => x.ToString() 中 x : int，返回 string，推断 TResult = string
3. 实例化为 Select<int, string>

类型推断算法基于约束求解，复杂度 $O(n)$（$n$ 为类型参数数）。

Span<T> 与 Memory<T> 的内存零拷贝

Span<T> 是对连续内存区域的类型安全视图，定义为：

• ref T 是托管指针，指向内存起始
• length 是元素数

Span<T> 可覆盖托管数组、栈分配 stackalloc、非托管内存 NativeMemory，无运行时装箱。但其必须 ref struct（不能装箱、不能作为字段、不能跨 await），保证生命周期局限于栈帧。

Memory<T> 是 Span<T> 的堆可存储版本，可用于异步方法字段，通过 MemoryMarshal.TryGetArray 获取底层 ArraySegment<T>。

切片 span.Slice(start, length) 仅需 $O(1)$ 修改指针与长度，无需复制数据，是零拷贝算法的关键。

代码示例

示例 1：泛型类与多约束

using System;
using System.Collections.Generic;

/// <summary>
/// 泛型缓存：支持带 TTL 的键值存储。
/// 多约束：TKey 必须 implements IComparable<TKey> 且有无参构造，
/// TValue 必须是 class（引用类型）。
/// </summary>
public class TtlCache<TKey, TValue>
    where TKey : notnull, IComparable<TKey>, IEquatable<TKey>
    where TValue : class
{
    // 内部条目：存储值与过期时间
    private readonly Dictionary<TKey, Entry> _store = new();
    private readonly TimeSpan _ttl;
    private readonly object _lock = new();

    public TtlCache(TimeSpan ttl) => _ttl = ttl;

    /// <summary>设置键值对，过期时间为当前时间 + TTL。</summary>
    public void Set(TKey key, TValue value)
    {
        lock (_lock)
        {
            _store[key] = new Entry(value, DateTime.UtcNow + _ttl);
        }
    }

    /// <summary>
    /// 尝试获取值。若已过期则移除并返回 false。
    /// 使用 ref 局部变量避免两次哈希查找。
    /// </summary>
    public bool TryGet(TKey key, out TValue? value)
    {
        lock (_lock)
        {
            ref var entry = ref CollectionsMarshal.GetValueRefOrNullRef(_store, key);
            if (!Unsafe.IsNullRef(ref entry))
            {
                if (entry.ExpiresAt > DateTime.UtcNow)
                {
                    value = entry.Value;
                    return true;
                }
                _store.Remove(key);
            }
        }
        value = default;
        return false;
    }

    /// <summary>清理所有过期条目。</summary>
    public int Cleanup()
    {
        lock (_lock)
        {
            var now = DateTime.UtcNow;
            var expired = new List<TKey>();
            foreach (var kv in _store)
            {
                if (kv.Value.ExpiresAt <= now)
                    expired.Add(kv.Key);
            }
            expired.ForEach(k => _store.Remove(k));
            return expired.Count;
        }
    }

    private readonly record struct Entry(TValue Value, DateTime ExpiresAt);
}

示例 2：协变逆变与自定义集合

using System;
using System.Collections;
using System.Collections.Generic;

/// <summary>协变生产者接口：仅输出 T，不消费 T。</summary>
public interface IProducer<out T>
{
    T Produce();
    IEnumerable<T> ProduceMany(int count);
}

/// <summary>逆变消费者接口：仅消费 T，不输出 T。</summary>
public interface IConsumer<in T>
{
    void Consume(T item);
    void ConsumeAll(IEnumerable<T> items);
}

/// <summary>具体生产者：字符串工厂。</summary>
public sealed class StringFactory : IProducer<string>
{
    private int _counter = 0;

    public string Produce() => $"item-{++_counter}";

    public IEnumerable<string> ProduceMany(int count)
    {
        for (int i = 0; i < count; i++)
            yield return Produce();
    }
}

/// <summary>具体消费者：日志记录器，能消费任意 object。</summary>
public sealed class Logger : IConsumer<object>
{
    public void Consume(object item) =>
        Console.WriteLine($"[Log] {item}");

    public void ConsumeAll(IEnumerable<object> items)
    {
        foreach (var item in items)
            Consume(item);
    }
}

public class CovarianceDemo
{
    public static void Run()
    {
        IProducer<string> stringProducer = new StringFactory();
        // 协变：IProducer<string> 可视为 IProducer<object>
        IProducer<object> objectProducer = stringProducer;
        object val = objectProducer.Produce(); // 返回 string，安全转为 object

        IConsumer<object> objectConsumer = new Logger();
        // 逆变：IConsumer<object> 可视为 IConsumer<string>
        IConsumer<string> stringConsumer = objectConsumer;
        stringConsumer.Consume("hello"); // 调用接收 object 的方法，string 是 object
    }
}

示例 3：自定义可枚举集合（环形缓冲区）

using System;
using System.Collections;
using System.Collections.Generic;

/// <summary>
/// 环形缓冲区：固定容量的 FIFO 队列，满时覆盖最旧元素。
/// 实现 IEnumerable<T> 支持 LINQ 与 foreach。
/// </summary>
public sealed class CircularBuffer<T> : IEnumerable<T>, IReadOnlyCollection<T>
{
    private readonly T[] _buffer;
    private int _head; // 下一个写入位置
    private int _count;

    public CircularBuffer(int capacity)
    {
        if (capacity <= 0)
            throw new ArgumentOutOfRangeException(nameof(capacity));
        _buffer = new T[capacity];
        _head = 0;
        _count = 0;
    }

    public int Capacity => _buffer.Length;
    public int Count => _count;

    /// <summary>添加元素。若已满，覆盖最旧元素并返回被覆盖的值。</summary>
    public bool TryAdd(T item, out T? overwritten)
    {
        overwritten = default;
        bool wasFull = _count == _buffer.Length;

        if (wasFull)
            overwritten = _buffer[_head]; // 即将被覆盖

        _buffer[_head] = item;
        _head = (_head + 1) % _buffer.Length;
        if (!wasFull) _count++;

        return wasFull;
    }

    /// <summary>按写入顺序返回元素（最旧到最新）。</summary>
    public IEnumerator<T> GetEnumerator()
    {
        int start = _count == _buffer.Length ? _head : 0;
        for (int i = 0; i < _count; i++)
        {
            yield return _buffer[(start + i) % _buffer.Length];
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

public class CircularBufferDemo
{
    public static void Run()
    {
        var buf = new CircularBuffer<int>(3);
        for (int i = 1; i <= 5; i++)
        {
            buf.TryAdd(i, out var overwritten);
            if (overwritten != default)
                Console.WriteLine($"覆盖: {overwritten}");
        }
        // 输出: 覆盖: 1, 覆盖: 2
        Console.WriteLine(string.Join(", ", buf)); // 3, 4, 5
        Console.WriteLine($"Sum: {buf.Sum()}, Max: {buf.Max()}"); // 12, 5
    }
}

示例 4：迭代器组合与惰性求值

using System;
using System.Collections.Generic;

/// <summary>惰性序列生成器：基于 yield 的函数式风格。</summary>
public static class Seq
{
    /// <summary>无限自然数序列（从 1 开始）。</summary>
    public static IEnumerable<int> Naturals()
    {
        int n = 1;
        while (true) yield return n++;
    }

    /// <summary>斐波那契数列。</summary>
    public static IEnumerable<long> Fibonacci()
    {
        long a = 0, b = 1;
        while (true)
        {
            yield return b;
            (a, b) = (b, a + b);
        }
    }

    /// <summary>素数序列（埃拉托色尼筛法变种）。</summary>
    public static IEnumerable<int> Primes()
    {
        yield return 2;
        var primes = new List<int> { 2 };
        int candidate = 3;
        while (true)
        {
            bool isPrime = true;
            int sqrt = (int)Math.Sqrt(candidate);
            foreach (var p in primes)
            {
                if (p > sqrt) break;
                if (candidate % p == 0) { isPrime = false; break; }
            }
            if (isPrime)
            {
                primes.Add(candidate);
                yield return candidate;
            }
            candidate += 2;
        }
    }

    /// <summary>通用过滤：惰性迭代器组合的核心。</summary>
    public static IEnumerable<T> Where<T>(
        this IEnumerable<T> source, Func<T, bool> predicate)
    {
        foreach (var item in source)
            if (predicate(item))
                yield return item;
    }

    /// <summary>通用映射。</summary>
    public static IEnumerable<TResult> Select<T, TResult>(
        this IEnumerable<T> source, Func<T, TResult> selector)
    {
        foreach (var item in source)
            yield return selector(item);
    }

    /// <summary>取前 n 个。</summary>
    public static IEnumerable<T> Take<T>(
        this IEnumerable<T> source, int count)
    {
        int i = 0;
        foreach (var item in source)
        {
            if (i++ >= count) yield break;
            yield return item;
        }
    }
}

public class IteratorDemo
{
    public static void Run()
    {
        // 前 10 个偶斐波那契数的平方
        var result = Seq.Fibonacci()
            .Where(n => n % 2 == 0)
            .Select(n => n * n)
            .Take(10)
            .ToList();

        Console.WriteLine(string.Join(", ", result));
        // 1, 9, 64, 1764, 16641, 93025, 113569, 4356, 116964, 278784
        // （具体值取决于是否从 1 开始）
    }
}

示例 5：Dictionary 性能优化与并发场景

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Threading.Tasks;

public class DictionaryPerformance
{
    /// <summary>统计词频：使用 GetValueRefOrNullRef 优化重复查找。</summary>
    public static Dictionary<string, int> CountWords(IEnumerable<string> words)
    {
        var counts = new Dictionary<string, int>();
        foreach (var word in words)
        {
            // .NET 6+: 获取引用避免两次哈希查找
            ref int count = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, word, out _);
            count++;
        }
        return counts;
    }

    /// <summary>并发词频统计：使用 ConcurrentDictionary + 多线程。</summary>
    public static ConcurrentDictionary<string, int> CountWordsParallel(IEnumerable<string> words)
    {
        var counts = new ConcurrentDictionary<string, int>();
        var batches = words.Chunk(10_000);
        Parallel.ForEach(batches, batch =>
        {
            foreach (var word in batch)
                counts.AddOrUpdate(word, 1, (_, old) => old + 1);
        });
        return counts;
    }

    /// <summary>对比不同字典在只读场景下的查询性能。</summary>
    public static void BenchmarkReadOnlyLookup()
    {
        var keys = Enumerable.Range(0, 100_000).Select(i => i.ToString()).ToArray();
        var dict = keys.ToDictionary(k => k, k => k);
        var frozen = dict.ToFrozenDictionary();
        var immutable = dict.ToImmutableDictionary();

        // 预热
        for (int i = 0; i < 1000; i++)
        {
            _ = dict[keys[i]];
            _ = frozen[keys[i]];
            _ = immutable[keys[i]];
        }

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < keys.Length; i++) _ = dict[keys[i]];
        sw.Stop();
        Console.WriteLine($"Dictionary: {sw.ElapsedMilliseconds} ms");

        sw.Restart();
        for (int i = 0; i < keys.Length; i++) _ = frozen[keys[i]];
        sw.Stop();
        Console.WriteLine($"FrozenDictionary: {sw.ElapsedMilliseconds} ms");

        sw.Restart();
        for (int i = 0; i < keys.Length; i++) _ = immutable[keys[i]];
        sw.Stop();
        Console.WriteLine($"ImmutableDictionary: {sw.ElapsedMilliseconds} ms");
    }
}

示例 6：不可变集合与函数式更新

using System;
using System.Collections.Generic;
using System.Collections.Immutable;

/// <summary>不可变配置树：演示 ImmutableDictionary 的函数式更新。</summary>
public sealed class AppConfig
{
    public ImmutableDictionary<string, string> Settings { get; }
    public ImmutableList<string> AllowedOrigins { get; }
    public ImmutableDictionary<string, int> RateLimits { get; }

    public AppConfig()
        : this(ImmutableDictionary<string, string>.Empty,
               ImmutableList<string>.Empty,
               ImmutableDictionary<string, int>.Empty)
    { }

    private AppConfig(
        ImmutableDictionary<string, string> settings,
        ImmutableList<string> origins,
        ImmutableDictionary<string, int> limits)
    {
        Settings = settings;
        AllowedOrigins = origins;
        RateLimits = limits;
    }

    /// <summary>更新设置：返回新的 AppConfig，原对象不变。</summary>
    public AppConfig WithSetting(string key, string value) =>
        new(Settings.SetItem(key, value), AllowedOrigins, RateLimits);

    /// <summary>添加允许的源。</summary>
    public AppConfig WithOrigin(string origin) =>
        new(Settings, AllowedOrigins.Add(origin), RateLimits);

    /// <summary>更新速率限制。</summary>
    public AppConfig WithRateLimit(string endpoint, int limit) =>
        new(Settings, AllowedOrigins, RateLimits.SetItem(endpoint, limit));

    /// <summary>快照：所有集合已经是不可变的，可直接返回。</summary>
    public AppConfig Snapshot() => this;
}

public class ImmutableDemo
{
    public static void Run()
    {
        var config = new AppConfig()
            .WithSetting("app.name", "FANDEX")
            .WithSetting("env", "production")
            .WithOrigin("https://fandex.example.com")
            .WithRateLimit("/api/search", 100);

        var updated = config.WithSetting("env", "staging");
        Console.WriteLine(config.Settings["env"]);       // production（原对象未变）
        Console.WriteLine(updated.Settings["env"]);      // staging
    }
}

示例 7：PriorityQueue 实现任务调度

using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;

/// <summary>
/// 优先级任务调度器：使用 PriorityQueue 按优先级出队。
/// 演示 .NET 6+ PriorityQueue 的典型用法。
/// </summary>
public sealed class PriorityScheduler : IDisposable
{
    private readonly PriorityQueue<Func<Task>, (int Priority, long Sequence)> _queue = new();
    private readonly object _lock = new();
    private readonly SemaphoreSlim _signal = new(0);
    private readonly CancellationTokenSource _cts = new();
    private long _sequence;
    private readonly Task _worker;

    public PriorityScheduler()
    {
        _worker = Task.Run(WorkerLoop);
    }

    /// <summary>提交任务：优先级数值越小越优先执行。</summary>
    public void Submit(Func<Task> task, int priority)
    {
        lock (_lock)
        {
            // 使用 (Priority, Sequence) 作为复合优先级，保证相同优先级 FIFO
            _queue.Enqueue(task, (priority, ++_sequence));
        }
        _signal.Release();
    }

    private async Task WorkerLoop()
    {
        await _signal.WaitAsync(_cts.Token);
        while (!_cts.IsCancellationRequested)
        {
            Func<Task> task;
            lock (_lock)
            {
                if (_queue.Count == 0)
                {
                    Monitor.Exit(_lock);
                    await _signal.WaitAsync(_cts.Token);
                    Monitor.Enter(_lock);
                    if (_queue.Count == 0) continue;
                }
                task = _queue.Dequeue();
            }

            try
            {
                await task();
            }
            catch (Exception ex)
            {
                Console.WriteLine($"任务执行失败: {ex.Message}");
            }
        }
    }

    public void Dispose()
    {
        _cts.Cancel();
        _signal.Release();
        _worker.Wait(TimeSpan.FromSeconds(5));
        _cts.Dispose();
        _signal.Dispose();
    }
}

public class SchedulerDemo
{
    public static async Task Run()
    {
        using var scheduler = new PriorityScheduler();

        scheduler.Submit(async () =>
        {
            Console.WriteLine("低优先级任务");
            await Task.Delay(100);
        }, priority: 10);

        scheduler.Submit(async () =>
        {
            Console.WriteLine("高优先级任务");
            await Task.Delay(100);
        }, priority: 1);

        scheduler.Submit(async () =>
        {
            Console.WriteLine("中优先级任务");
            await Task.Delay(100);
        }, priority: 5);

        await Task.Delay(1000);
        // 输出顺序：高 -> 中 -> 低
    }
}

示例 8：自定义相等比较器与排序

using System;
using System.Collections.Generic;
using System.Linq;

/// <summary>不区分大小写的字符串比较器。</summary>
public sealed class CaseInsensitiveComparer : IEqualityComparer<string>, IComparer<string>
{
    public static readonly CaseInsensitiveComparer Instance = new();

    public bool Equals(string? x, string? y) =>
        string.Equals(x, y, StringComparison.OrdinalIgnoreCase);

    public int GetHashCode(string obj) =>
        StringComparer.OrdinalIgnoreCase.GetHashCode(obj);

    public int Compare(string? x, string? y) =>
        string.Compare(x, y, StringComparison.OrdinalIgnoreCase);
}

/// <summary>多字段排序器：链式比较。</summary>
public sealed class ChainedComparer<T> : IComparer<T>
{
    private readonly List<(Func<T, T, int> Compare, bool Descending)> _comparisons = new();

    public static ChainedComparer<T> Create() => new();

    public ChainedComparer<T> ThenBy<TKey>(Func<T, TKey> keySelector, bool descending = false)
        where TKey : IComparable<TKey>
    {
        _comparisons.Add((a, b =>
        {
            int r = keySelector(a).CompareTo(keySelector(b));
            return descending ? -r : r;
        }, false));
        return this;
    }

    public int Compare(T? x, T? y)
    {
        if (x is null && y is null) return 0;
        if (x is null) return -1;
        if (y is null) return 1;

        foreach (var (cmp, _) in _comparisons)
        {
            int r = cmp(x, y);
            if (r != 0) return r;
        }
        return 0;
    }
}

public class Person
{
    public string Name { get; set; } = "";
    public int Age { get; set; }
    public string City { get; set; } = "";

    public override string ToString() => $"{Name} ({Age}, {City})";
}

public class ComparerDemo
{
    public static void Run()
    {
        var people = new List<Person>
        {
            new() { Name = "Alice", Age = 30, City = "Beijing" },
            new() { Name = "Bob", Age = 25, City = "Shanghai" },
            new() { Name = "alice", Age = 28, City = "Beijing" },
            new() { Name = "Charlie", Age = 30, City = "Shenzhen" },
        };

        // 使用不区分大小写的比较器去重（按 Name）
        var byName = new Dictionary<string, Person>(CaseInsensitiveComparer.Instance);
        foreach (var p in people)
            byName[p.Name] = p;
        Console.WriteLine($"按 Name 去重后剩余: {byName.Count}"); // 3（Alice 与 alice 合并）

        // 链式排序：先按 City，再按 Age 降序
        var sorted = people
            .OrderBy(p => p.City)
            .ThenByDescending(p => p.Age)
            .ToList();
        sorted.ForEach(Console.WriteLine);
    }
}

示例 9：Span<T> 零拷贝切片

using System;
using System.Linq;
using System.Text;

public class SpanDemo
{
    /// <summary>统计字节数组中等于目标值的元素个数，零分配。</summary>
    public static int Count(byte[] source, byte target)
    {
        var span = source.AsSpan();
        int count = 0;
        foreach (var b in span)
            if (b == target) count++;
        return count;
    }

    /// <summary>反转字符串中的字符顺序，无需中间字符串。</summary>
    public static string ReverseString(string input)
    {
        if (string.IsNullOrEmpty(input)) return input;
        // 借助 Span<char> 避免多次字符串分配
        Span<char> buffer = input.Length <= 256
            ? stackalloc char[input.Length]
            : new char[input.Length];
        input.AsSpan().CopyTo(buffer);
        buffer.Reverse();
        return new string(buffer);
    }

    /// <summary>解析整数行：基于 ReadOnlySpan 的零拷贝解析。</summary>
    public static int[] ParseNumbers(ReadOnlySpan<char> input, char separator = ',')
    {
        var result = new List<int>();
        while (!input.IsEmpty)
        {
            int idx = input.IndexOf(separator);
            ReadOnlySpan<char> token = idx < 0 ? input : input[..idx];
            if (!token.IsEmpty && int.TryParse(token, out int n))
                result.Add(n);
            if (idx < 0) break;
            input = input[(idx + 1)..];
        }
        return result.ToArray();
    }

    /// <summary>base64 编码：使用 Span 避免中间 byte[] 分配。</summary>
    public static string ToBase64(ReadOnlySpan<byte> data)
    {
        // 预分配精确大小，避免 Convert.ToBase64String 内部缓冲区扩容
        Span<char> chars = stackalloc char[4 * ((data.Length + 2) / 3)];
        if (Convert.TryToBase64Chars(data, chars, out int written))
            return new string(chars[..written]);
        throw new InvalidOperationException("base64 编码失败");
    }

    public static void Run()
    {
        Console.WriteLine(ReverseString("hello")); // olleh
        var nums = ParseNumbers("1, 22, 333, 4444");
        Console.WriteLine(string.Join(", ", nums)); // 1, 22, 333, 4444

        var bytes = Encoding.UTF8.GetBytes("hello world");
        Console.WriteLine(ToBase64(bytes)); // aGVsbG8gd29ybGQ=
    }
}

示例 10：集合表达式（C# 12）与展开运算符

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;

public class CollectionExpressionDemo
{
    public static void Run()
    {
        // 统一初始化语法
        int[] array = [1, 2, 3];
        List<string> list = ["a", "b", "c"];
        Span<int> span = [1, 2, 3];
        HashSet<string> set = ["x", "y", "z"];
        ImmutableArray<int> immutable = [1, 2, 3];

        // 展开运算符 ..
        int[] a = [1, 2, 3];
        int[] b = [4, 5, 6];
        int[] combined = [..a, ..b, 7, 8, 9];
        Console.WriteLine(string.Join(", ", combined)); // 1,2,3,4,5,6,7,8,9

        // 作为方法参数
        Process([1, 2, 3, 4, 5]);
        Process([..a, ..b]);
    }

    /// <summary>方法接受 ReadOnlySpan，调用方可传集合表达式。</summary>
    static void Process(ReadOnlySpan<int> values)
    {
        Console.WriteLine($"处理 {values.Length} 个值: {string.Join(", ", values.ToArray())}");
    }

    /// <summary>返回集合表达式：编译器自动选择合适的目标类型。</summary>
    static IEnumerable<int> GenerateNumbers()
    {
        return [1, 2, 3, 4, 5];
    }

    /// <summary>泛型方法中的集合表达式（需指定目标类型）。</summary>
    static List<T> AppendDefault<T>(List<T> source)
    {
        // 此处不能直接用 [..source, default]，编译器需明确目标类型
        var result = new List<T>(source) { default! };
        return result;
    }
}

对比分析

C# 泛型与其他语言泛型对比

讨论：C# 泛型在类型安全、性能、表达力之间取得了良好平衡。Java 通过类型擦除简化实现，但牺牲了运行时类型信息与值类型效率；C++ 模板是最强大的元编程工具，但缺乏约束导致错误信息难读、代码膨胀严重；Rust 通过 trait bound 与单态化实现了零开销抽象，但学习曲线陡峭。

集合类型选择决策矩阵

不可变集合对比

哈希集合与排序集合复杂度对比

常见陷阱与反模式

陷阱 1：在 foreach 中修改集合

// 反模式：迭代时修改集合，抛出 InvalidOperationException
var list = new List<int> { 1, 2, 3, 4, 5 };
foreach (var n in list)
{
    if (n % 2 == 0)
        list.Remove(n); // 抛出异常：集合已修改
}

// 正确：使用 RemoveAll 一次性删除
list.RemoveAll(n => n % 2 == 0);

// 或：先收集要删除的，再倒序删除
var toRemove = list.Where(n => n % 2 == 0).ToList();
foreach (var n in toRemove)
    list.Remove(n);

// 或：迭代时使用 for 循环倒序
for (int i = list.Count - 1; i >= 0; i--)
{
    if (list[i] % 2 == 0)
        list.RemoveAt(i);
}

原因：List<T>.Enumerator 维护版本号，Add/Remove/Clear 递增版本号，迭代时检查不一致则抛异常。

陷阱 2：Dictionary 键的可变性

// 反模式：使用可变对象作为 Dictionary 键，修改后丢失
var dict = new Dictionary<Person, string>();
var p = new Person { Name = "Alice", Age = 30 };
dict[p] = "engineer";
p.Age = 31; // 修改了影响哈希码的字段
_ = dict[p]; // KeyNotFoundException，哈希码已变，找不到桶

// 正确：使用不可变对象作为键
public sealed record PersonKey(string Name, int Age);
var key = new PersonKey("Alice", 30);
dict[key] = "engineer";
// PersonKey 是 record，无法修改，键永远稳定

原则：作为字典键的对象必须不可变，或至少影响 GetHashCode 与 Equals 的字段不可变。

陷阱 3：值类型集合的装箱

// 反模式：非泛型 ArrayList 装箱值类型，性能极差
var list = new ArrayList();
for (int i = 0; i < 1_000_000; i++)
    list.Add(i); // 每次装箱：4 字节 int -> 12 字节 boxed object
// 总内存：12 MB 而非 4 MB，且装箱耗时

// 正确：使用泛型 List<int>
var list = new List<int>();
for (int i = 0; i < 1_000_000; i++)
    list.Add(i); // 直接写入 int[]，无装箱

性能差距：在 .NET 8 实测，相同操作 List<int> 比 ArrayList 快约 5-10 倍，内存占用少 3 倍。

陷阱 4：误解协变只读安全

// 误以为 IEnumerable<object> 可以写入
IEnumerable<object> objects = new List<string> { "a", "b" };
// objects.Add("c"); // 编译错误：IEnumerable<object> 没有 Add
// 但若强制转换为 List<object>：
var list = (List<object>)objects; // InvalidCastException

// 正确：使用 IEnumerable<T> 仅读取
foreach (object o in objects)
    Console.WriteLine(o);

// 需要写入：创建新集合
var writable = objects.ToList(); // List<object>
writable.Add("c");

陷阱 5：迭代器的延迟执行副作用

// 反模式：多次枚举 yield 迭代器触发重复计算
IEnumerable<int> Generate()
{
    Console.WriteLine("generating...");
    for (int i = 0; i < 5; i++) yield return i;
}

var nums = Generate();
var sum = nums.Sum();      // 输出 "generating..."，计算
var count = nums.Count();  // 再次输出 "generating..."，重新计算
var list = nums.ToList();  // 第三次输出 "generating..."

// 正确：缓存结果
var cached = nums.ToList(); // 仅迭代一次
var sum = cached.Sum();
var count = cached.Count;

原则：IEnumerable<T> 可能是延迟序列，多次遍历会重复执行。需要多次访问时先 ToList() 或 ToArray() 物化。

陷阱 6：线程安全的误解

// 反模式：多个线程同时向 List<T> 添加，数据竞争
var list = new List<int>();
Parallel.For(0, 10000, i => list.Add(i)); // 可能丢失元素、抛异常、数据损坏

// 正确：使用 ConcurrentBag 或加锁
var bag = new ConcurrentBag<int>();
Parallel.For(0, 10000, i => bag.Add(i));

// 或：使用锁
var list2 = new List<int>();
var lockObj = new object();
Parallel.For(0, 10000, i =>
{
    lock (lockObj) list2.Add(i);
});

// 或：先分区后合并
var results = Enumerable.Range(0, 10000)
    .AsParallel()
    .Select(i => i)
    .ToList(); // PLINQ 自动处理

陷阱 7：HashSet 性能因哈希函数退化

// 反模式：自定义类型未重写 GetHashCode/Equals，使用默认引用相等
public class Item
{
    public int Id { get; set; }
    // 未重写 Equals 与 GetHashCode
}

var set = new HashSet<Item>();
set.Add(new Item { Id = 1 });
set.Add(new Item { Id = 1 }); // 不同对象，被加入，去重失败
Console.WriteLine(set.Count); // 2，预期 1

// 正确：重写 Equals 与 GetHashCode，或使用 record
public sealed record Item(int Id);

var set2 = new HashSet<Item>();
set2.Add(new Item(1));
set2.Add(new Item(1)); // Equals 返回 true，被去重
Console.WriteLine(set2.Count); // 1

原则：放入 HashSet<T> 或作为 Dictionary 键的类型必须正确实现 Equals 与 GetHashCode，保证相等对象有相同哈希码。record 自动实现结构化相等。

陷阱 8：List 容量未预分配导致扩容开销

// 反模式：知道最终大小但未预分配，触发多次扩容
var list = new List<int>();
for (int i = 0; i < 1_000_000; i++)
    list.Add(i); // 触发约 20 次扩容与复制

// 正确：构造时指定容量
var list2 = new List<int>(1_000_000);
for (int i = 0; i < 1_000_000; i++)
    list2.Add(i); // 无扩容

// 或：使用 EnsureCapacity
var list3 = new List<int>();
list3.EnsureCapacity(1_000_000);
for (int i = 0; i < 1_000_000; i++)
    list3.Add(i);

性能差距：1 百万元素插入，预分配版本快约 2 倍，内存碎片更少。

陷阱 9：误用 LINQ 多次枚举数据库查询

// 反模式：EF Core 查询作为 IEnumerable 多次遍历，每次访问数据库
using var db = new AppDbContext();
var query = db.Users.Where(u => u.Age > 18); // IQueryable<User>

// 第一次：执行 SQL
var first = query.FirstOrDefault();
// 第二次：再次执行 SQL
var count = query.Count();
// 第三次：再次执行 SQL
var all = query.ToList();

// 正确：一次性加载到内存
var users = db.Users.Where(u => u.Age > 18).ToList();
var first = users.FirstOrDefault();
var count = users.Count;

// 或：根据需要分别构造不同 SQL
var first = db.Users.Where(u => u.Age > 18).FirstOrDefault();
var count = db.Users.Where(u => u.Age > 18).Count();

陷阱 10：Span<T> 错误的栈分配

// 反模式：stackalloc 大量数据导致栈溢出
public static string Process(string input)
{
    Span<char> buffer = stackalloc char[input.Length]; // 输入 100MB 时栈溢出
    // ...
    return new string(buffer);
}

// 正确：根据大小选择栈分配或堆分配
public static string Process(string input)
{
    if (input.Length > 256)
    {
        Span<char> buffer = new char[input.Length]; // 堆分配
        input.AsSpan().CopyTo(buffer);
        // ... 处理
        return new string(buffer);
    }
    else
    {
        Span<char> buffer = stackalloc char[input.Length]; // 栈分配
        input.AsSpan().CopyTo(buffer);
        // ... 处理
        return new string(buffer);
    }
}

// 反模式：将 Span 存储为字段
public class Bad
{
    private Span<int> _data; // 编译错误：Span<T> 是 ref struct，不能作为字段
}

// 反模式：跨 await 使用 Span
public async Task BadAsync()
{
    Span<byte> buffer = stackalloc byte[1024];
    await SomeAsyncMethod(); // 编译错误：Span 不能跨 await
}

工程实践

实践 1：选择正确的集合类型

决策流程：

1. 是否需要键值映射？
   • 是 → 是否需要有序？是 → SortedDictionary；否 → Dictionary
   • 否 → 继续
2. 是否需要去重？
   • 是 → 是否需要有序？是 → SortedSet；否 → HashSet
   • 否 → 继续
3. 是否需要随机索引访问？
   • 是 → List<T> 或 T[]
   • 否 → 继续
4. 访问模式？
   • FIFO → Queue<T>
   • LIFO → Stack<T>
   • 优先级 → PriorityQueue<TElement, TPriority>
   • 双端频繁增删 → LinkedList<T>
5. 是否线程安全？
   • 是 → ConcurrentDictionary / ConcurrentQueue / ConcurrentBag
   • 否 → 上述选择
6. 是否只读且长期使用？
   • 是 → FrozenDictionary / FrozenSet（启动时构建）
   • 否 → 上述选择

实践 2：性能优化的 7 个技巧

// 1. 预分配容量
var list = new List<int>(knownSize);
var dict = new Dictionary<string, int>(expectedCount);

// 2. 使用 CollectionsMarshal 避免重复哈希查找
ref int value = ref CollectionsMarshal.GetValueRefOrAddDefault(dict, key, out _);
value++;

// 3. 只读查询使用 AsReadOnly 或 FrozenSet
var readOnly = list.AsReadOnly();
var frozen = dict.ToFrozenDictionary();

// 4. 大集合分批处理使用 Chunk
foreach (var batch in largeList.Chunk(1000))
    ProcessBatch(batch);

// 5. 使用 Array.Empty<T>() 代替 new T[0]
static IEnumerable<T> EmptyIfNull<T>(IEnumerable<T>? source) =>
    source ?? Array.Empty<T>();

// 6. 字符串键使用 StringComparer 而非默认
var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

// 7. 使用 Span 切片避免 LINQ 在性能敏感路径的开销
public static int SumRange(int[] data, int start, int length)
{
    var slice = data.AsSpan(start, length);
    int sum = 0;
    foreach (var n in slice) sum += n;
    return sum; // 比 data.Skip(start).Take(length).Sum() 快 10 倍以上
}

实践 3：实现自定义可枚举类型

using System;
using System.Collections;
using System.Collections.Generic;

/// <summary>
/// 自定义分页序列：支持延迟求值与多次遍历。
/// 实现 IEnumerable<T> 使其与 LINQ 兼容。
/// </summary>
public sealed class PagedSequence<T> : IEnumerable<IEnumerable<T>>
{
    private readonly IEnumerable<T> _source;
    private readonly int _pageSize;

    public PagedSequence(IEnumerable<T> source, int pageSize)
    {
        if (pageSize <= 0)
            throw new ArgumentOutOfRangeException(nameof(pageSize));
        _source = source;
        _pageSize = pageSize;
    }

    public IEnumerator<IEnumerable<T>> GetEnumerator()
    {
        var page = new List<T>(_pageSize);
        foreach (var item in _source)
        {
            page.Add(item);
            if (page.Count == _pageSize)
            {
                yield return page;
                page = new List<T>(_pageSize);
            }
        }
        if (page.Count > 0)
            yield return page;
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

public class PaginationDemo
{
    public static void Run()
    {
        var numbers = Enumerable.Range(1, 25);
        var paged = new PagedSequence<int>(numbers, 10);

        foreach (var page in paged)
        {
            Console.WriteLine($"页 ({page.Count()}): {string.Join(", ", page)}");
        }
    }
}

实践 4：领域特定的泛型仓储

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Threading.Tasks;

/// <summary>泛型仓储接口：定义标准 CRUD 与查询。</summary>
public interface IRepository<T, in TKey> where T : class
{
    Task<T?> GetByIdAsync(TKey id);
    Task<IReadOnlyList<T>> FindAsync(Expression<Func<T, bool>> predicate);
    Task<IReadOnlyList<T>> GetAllAsync();
    Task<T> AddAsync(T entity);
    Task UpdateAsync(T entity);
    Task DeleteAsync(TKey id);
    Task<int> CountAsync(Expression<Func<T, bool>>? predicate = null);
}

/// <summary>内存仓储：用于单元测试与原型开发。</summary>
public class InMemoryRepository<T, TKey> : IRepository<T, TKey>
    where T : class
    where TKey : notnull
{
    private readonly Dictionary<TKey, T> _store = new();

    private readonly Func<T, TKey> _keySelector;

    public InMemoryRepository(Func<T, TKey> keySelector) => _keySelector = keySelector;

    public Task<T?> GetByIdAsync(TKey id) =>
        Task.FromResult(_store.TryGetValue(id, out var t) ? t : null);

    public Task<IReadOnlyList<T>> FindAsync(Expression<Func<T, bool>> predicate)
    {
        var compiled = predicate.Compile();
        var results = _store.Values.Where(compiled).ToList();
        return Task.FromResult<IReadOnlyList<T>>(results);
    }

    public Task<IReadOnlyList<T>> GetAllAsync() =>
        Task.FromResult<IReadOnlyList<T>>(_store.Values.ToList());

    public Task<T> AddAsync(T entity)
    {
        var key = _keySelector(entity);
        _store[key] = entity;
        return Task.FromResult(entity);
    }

    public Task UpdateAsync(T entity)
    {
        _store[_keySelector(entity)] = entity;
        return Task.CompletedTask;
    }

    public Task DeleteAsync(TKey id)
    {
        _store.Remove(id);
        return Task.CompletedTask;
    }

    public Task<int> CountAsync(Expression<Func<T, bool>>? predicate = null)
    {
        var count = predicate is null
            ? _store.Count
            : _store.Values.Count(predicate.Compile());
        return Task.FromResult(count);
    }
}