.NET 数据结构大杂烩：键值对

在工程场景中，我们经常会借助键值对 (Key-Value Pair) 和哈希 (Hash) 的机制来操作数据，尤其是面对关系映射、缓存、对象池等场景中，它们的存在十分必要。

在 .NET 的历史中，该数据结构也经历了多次演进。它们的实现原理很简单，但随着性能、内存、多线程等方面的需求不断提升，.NET 也在不断优化和改进这些数据结构的实现。

本文寻找的源代码均为最新，比如曾经的object可能变成了object?，但这并不影响我们对其设计和实现的理解。

Hashtable

在 .NET 平台的初期，C# 1.0 的规范中指定System.Collections.Hashtable是处理键值对映射的唯一官方组件。虽然它通常情况下时间复杂度为 O(1)，但局限于当时的设计和实现，对比于接下来的 Dictionary<TKey, TValue>，它存在以下显著的缺点。

类型安全问题

找到Hashtable源代码的Add方法，会发现它接受的参数类型为 object。

public virtual void Add(object key, object? value)
{
    Insert(key, value, true);
}

因为你可以将任何类型的对象放入同一个Hashtable中，这就导致在尝试取出其数据时，必须进行显式类型转换，如果转换失败，就会抛出运行时错误。

所以Hashtable无法保证编译时类型安全，容易引发运行时错误，但这并不是它本身的问题，因为泛型是在 C# 2.0 引入的，这个问题在当时确实无法避免。

不建议使用

现如今，新项目建议直接使用Dictionary<TKey, TValue>，因为Hashtable缺少泛型带来的好处，详见DE0006: Non-generic collections shouldn’t be used

装箱与拆箱的性能问题

上述的类型安全问题同时引入了object类型的装箱和拆箱操作，尤其是对于值类型（如int、double等）来说，这些操作会导致性能下降和 GC 压力增加。

尽管在如今的 .NET 版本中，JIT 编译器已经对装箱和拆箱进行了优化，但在当时的环境中，这确实是一个显著的性能问题（现在同样也强烈建议避免装箱和拆箱操作）。

可读性和维护性问题

同上，缺乏泛型约束的Hashtable使得代码的意图不够明确。对比Dictionary<TKey, TValue>，它的类型参数明确了键和值的类型，而Hashtable则需要开发者在使用前确认其内容的类型，且在使用过程中也需要频繁进行类型检查和转换。

如果你尝试在Hashtable访问一个不存在的键，返回的结果是null，虽然谈不上是缺点，但是需要在约定上总是检查返回值是否为null，否则可能会引发NullReferenceException。

底层实现

Hashtable采用了开放寻址法 (Open Addressing) 中的双重散列 (Double Hashing) 来实现。

观察它的存储结构，其内部维护了一个bucket结构体数组，包含三个字段。

private struct Bucket
{
    public object? key;   // 键
    public object? val;   // 值
    public int hash_coll; // 存储哈希值的同时记录是否发生过碰撞，详解见后文
}

private Bucket[] _buckets = null!;

计算过程

当我们向Hashtable添加一个键值对时，它会按照以下步骤进行：

Hashtable的核心探测公式是：

h(key, n) = h_1(key) + n \cdot h_2(key)

$h_1(key)$ ：初始落点（基准位置）
$h_2(key)$ ：每次发生碰撞时，计算新的探测位置的增量（步长）
$n$ ：当前是第几次碰撞探测（循环次数）

这里其实引出了一个数学表达和工程实现的差异。

站在数学的角度看，第n次探测的绝对位置公式是 $P(n) = (h_1(key) + n \cdot h_2(key)) \pmod m$ ，因为连续的加法就是乘法，每次迭代都会增加一个步长 $h_2(key)$ ，所以我们可以直接用乘法来表达。

但是从工程实现的角度，我们不能简单地将这个迭代改成循环，然后每次循环都执行一次 n * h2 的乘法运算，在极高频调用场景中，这么做的性能开销很大。

实际上，每次循环之后的位置是上一次位置加上步长，所以我们可以直接在循环中维护一个当前探测位置的变量，每次发生碰撞时直接加上步长，这样就避免了每次都进行乘法运算。

注释中提到：

We previously used a different h2(key, n) that was not constant. That is ahorrifically bad idea …

有可能在更早期的实现中，h2是一个非恒定的函数，可能会根据n的值进行变化，比如二次探测 (Quadratic Probing)，尽管更复杂的公式能够让哈希散布更均匀，但性能开销也会更大，不如退回到一个恒定的步长来得高效。

回到这个公式本身，先计算 $h_1(key) = GetHash(key)$ ，来决定该元素在理想情况下应当存储的位置。

但如果此时该位置被占用，就需要进行第二步，计算步长，尝试寻找下一个位置。计算公式如下：

h_2(key) = 1 + (((h_1(key) \gg 5) + 1) \pmod{\text{hashsize} - 1})

其中：

右移5位的意图在于将原哈希值较高位的部分参与到这一轮计算中，以保证即使 $h_1(key)$ 碰撞，它们的 $h_2(key)$ 也大概率不同，从而减少连续碰撞的可能性。
取模的目的在于确保步长的最大值不会超出数组总长度。
加1是为了确保步长至少为1，避免原地踏步。

这里的hashsize藏了一个小巧思，源码注释提到：

2 must return a number between 1 and hashsize - 1 that is relatively prime to hashsize (not a problem if hashsize is prime).
(Knuth’s Art of Computer Programming, Vol. 3, p. 528-9)

假设hashsize为10，步长为2，探测序列将是：0, 2, 4, 6, 8, 0, 2, ...，另一半空间将永远无法被访问到，这就导致了内存浪费。因此，hashsize必须是一个质数，以确保步长与数组长度互质，从而能够访问到数组中的每一个位置。

还记得Bucket结构体中的hash_coll字段吗？

第一个问题是为什么要标记碰撞，因为在开放寻址法中，如果发生碰撞，我们需要继续探测下一个位置，直到找到一个空位或者找到目标键。如果没有标记碰撞的信息，我们就无法区分当前桶是空的还是被占用但发生了碰撞，这会导致探测过程中的错误判断。

同样，在查找的探测过程中，如果在某个位置发现这个键不匹配的同时没有发生冲突，就意味着这个键根本不存在于哈希表中，可以直接返回未找到的结果；如果发生了碰撞，就需要继续探测下一个位置，直到找到匹配的键或者遇到一个没有发生碰撞的空桶。

其次，可能会疑惑为什么要将哈希值和碰撞信息存储在同一个字段中？不拆开放，一个int hashCode和一个bool hasCollision不就好了。

首先是内存占用优化。一个int有32位，但哈希值不需要用满32位，最高位可以用来标记是否发生过碰撞，这样就节省了一个bool的内存空间，同时保证哈希值为正数即可。

部分源代码和注释如下：

1
2
3

// Hashcode must be positive.  Also, we must not use the sign bit, since
// that is used for the collision bit.
uint hashcode = (uint)GetHash(key) & 0x7FFFFFFF;

最后就是保证删除元素后哈希表的完整性问题了。开放寻址法中，如果直接将一个桶标记为删除，那么在后续的探测过程中，如果遇到这个被标记为删除的桶，就会误以为这个键不存在，从而导致查找失败。

因此，Hashtable在删除元素时，并不是直接将桶标记为删除，而是将其标记为发生过碰撞的状态，这样在后续的探测过程中就会继续探测下一个位置，直到找到匹配的键或者遇到一个没有发生碰撞的空桶。

Dictionary

2005年，随着 .NET Framework 2.0 的发布，微软引入了泛型 (Generics)，并基于此推出了Dictionary<TKey, TValue>，它在设计上解决了Hashtable的诸多问题，成为了新的键值对数据结构的标准实现。直到现在，Dictionary<TKey, TValue>仍然是 .NET 中最常用的键值对数据结构之一。

后文将使用Dictionary来指代Dictionary<TKey, TValue>，以简化表述。

与Hashtable不同，Dictionary采用了链式地址法 (Chaining) 的方式来处理碰撞问题。同时，为了避免传统链表在堆上离散分配内存锁导致的内存碎片化和性能问题，工程师改用了数组+索引的方式来实现链表结构。

观察Dictionary的存储结构，其内部维护了一个Entry结构体数组，包含四个字段。

private Entry[]? _entries;

private struct Entry
{
    public uint hashCode;  // 哈希值
    public int next;       // 下一个元素在数组中的索引
    public TKey key;       // 键
    public TValue value;   // 值
}

这种数据结构的设计使得其自身在内存布局上更为紧凑。当哈希碰撞发生时，元素之间也不是通过对象引用连接，而是通过next字段在数组内部形成一个基于索引的单向链表。对于 CPU 来说，读取相邻的内存块总是更快的。

优势

Dictionary是一个泛型类，定义了类型参数TKey和TValue，这使得它在编译时就能够保证类型安全。开发者在使用Dictionary时必须指定键和值的类型，这样在编译阶段就能捕获类型错误，避免了运行时错误的风险。

由于泛型参数在运行时会被实例化为对应的内存布局，当使用int等值类型作为键时，entries数组中的key字段会直接存储int的值，这个过程中不会出现堆内存分配，也就不存在装箱和拆箱的性能问题了。

在两年后的 C# 3.0 中，微软引入了 LINQ (Language-Integrated Query)，Dictionary也实现了IEnumerable<KeyValuePair<TKey, TValue>>接口，使得我们可以使用 LINQ 来查询和操作字典中的数据。

空安全设计

TryXXX 方法一直是我喜欢的设计模式，Dictionary提供了TryGetValue方法来安全地尝试获取一个键对应的值，而不会抛出异常。这种设计使得代码更加健壮和易于维护。

对于以下示例：

var dict = new Dictionary<string, int>();
dict["a"] = 1;
if (dict.TryGetValue("b", out var value))  // 尝试获取键 "b" 的值，如果存在则设置 value 并返回 true，否则返回 false
    Console.WriteLine(value);
else
    Console.WriteLine("Key not found.");

局限性

泛型字典的卓越性能和类型安全性使得它成为了 .NET 中的主流键值对数据结构，但它在面对多线程并发读写时并不安全。

随着多核 CPU 普及，软件架构逐渐需要能够处理高并发需求。在这个时候，开发者可以简单地借助lock关键字来保护对Dictionary的并发访问，但这个锁过于粗粒度，在任何时候只能有一个线程访问字典，这会导致性能瓶颈。

为了解决这个问题，微软在 .NET 4.0 中引入了ConcurrentDictionary<TKey, TValue>。

ConcurrentDictionary

ConcurrentDictionary表示可同时由多个线程访问的键/值对的线程安全集合。

依然管中窥豹，完整的源代码比较长，这里我们只关注它的核心设计和实现。

传统的Dictionary采用的双数组结构（buckets和entries）在多线程环境下底层的索引和链表结构很容易被破坏，从而出现预期之外的数据丢失等问题。

从源代码的TryAddInternal方法我们能发现ConcurrentDictionary采用了分段锁 (Segmented Locking) 和无锁读取的设计。

分段锁机制

在该方法的while循环中，存在这段代码结构：

object[] locks = tables._locks;
ref Node? bucket = ref GetBucketAndLock(tables, hashcode, out uint lockNo);
// ...
Monitor.Enter(locks[lockNo], ref lockTaken);

不像lock关键字那样直接锁住整个字典，而是内部维护了一个_locks数组，当计算出键的哈希值后，会根据哈希值计算出一个锁的索引 lockNo，然后只锁住这个特定的锁对象。

这样，如果两个线程分别访问不同的键，并且这两个键的哈希值映射到不同的锁，那么它们就可以同时进行操作，而不会互相阻塞，从而提高了并发性能。在默认情况下，锁的数量等于 CPU 的逻辑核心数。

1 2	/// <summary>The number of concurrent writes for which to optimize by default.</summary> private static int DefaultConcurrencyLevel => Environment.ProcessorCount;

放弃连续数组

之前提到Dictionary采用了数组+索引的方式来实现链表结构，而ConcurrentDictionary则完全放弃了连续数组的设计，转而回退了链表节点 (Node) 的方式来存储键值对。

1 2	var resultNode = new Node(key, value, hashcode, bucket); Volatile.Write(ref bucket, resultNode);

在并发环境下，修改一个连续数组既危险又难以做到无锁安全。而每个Node对象在内存中是分散的，从而可以通过更新引用来安全地替换节点。

无锁读取

在ConcurrentDictionary中，读取操作是无锁的，这意味着多个线程可以同时读取数据而不会互相阻塞。这个特性是通过使用volatile关键字和内存屏障来实现的，确保了读取操作能够看到最新的写入结果。从源代码的this[key]索引器的get方法中，我们可以看到它直接访问了底层的链表节点，而没有使用任何锁机制。

ConcurrentDictionary中有个字段，volatile Tables _tables，它是一个包含了所有桶和锁的结构体。从这个类的注释可知，Tables保存了ConcurrentDictionary的内部状态，通过将所有可变状态封装到一个单独的对象中，并将其声明为volatile，可以确保在多线程环境下对这个状态的访问是安全的。

保证原子写入

这个方法中同样存在这段逻辑：

if (!typeof(TValue).IsValueType || ConcurrentDictionaryTypeProps<TValue>.IsWriteAtomic)
{
    node._value = value;
}
else
{
    var newNode = new Node(node._key, value, hashcode, node._next);
    if (prev is null)
    {
        Volatile.Write(ref bucket, newNode);
    }
    else
    {
        prev._next = newNode;
    }
}
resultingValue = value;

如果TValue不是值类型，或者是一个值类型但其写入操作是原子的（比如int、long等），那么直接更新节点的值即可；否则，为了保证写入操作的原子性，需要创建一个新的节点来替换旧节点。这样无锁的读线程也不会读到一个不完整的值，从而保证了线程安全。

ImmutableDictionary

后来，函数式编程再次流行起来，其核心理念之一的不可变性 (Immutability)，即数据一旦创建，就永远不能被修改的特性，受到了开发者的欢迎。

与此同时，在多线程环境中传递字典，为了保证传输过程中的防篡改，通常需要复制（深拷贝）整个哈希表，这样的性能开销是非常大的。

在 .NET Framework 4.5，微软发布了一个独立的System.Collections.Immutable Nuget 包，其中包含了不可变集合的实现，包括ImmutableDictionary<TKey, TValue>。

该数据结构的设计目标是提供一个线程安全的、不可变的键值对集合。可用于全局配置、只读缓存等一些需要共享但不允许修改的场景。

转进 AVL 树

ImmutableDictionary的底层实现并不是上述的哈希表，而是基于 AVL 树 (Adelson-Velsky and Landis Tree) 的一种自平衡二叉搜索树。与哈希表不同，AVL 树通过维护节点之间的高度平衡（左右子树的深度差不超过1）来保证在最坏情况下的 O(log n) 时间复杂度。

所以 ImmutableDictionary 的访问速度在平均情况下是不如哈希表的

AVL 树的设计使其支持更高效的版本控制和状态不变性。在处理哈希碰撞时，节点也不再是简单的链表，而是变成另一棵子树。

结构共享

当我们对ImmutableDictionary进行修改（比如添加、删除或更新一个键值对）时，并不会创建一个全新的字典，而是通过结构共享 (Structural Sharing) 的方式来实现。这意味着新旧字典会共享大部分的内部结构，只有被修改的路径上的节点会被复制和修改。

当我们向ImmutableDictionary中添加一个新的键值对时，算法会沿着根节点到新节点插入位置的路径，实例化新的分支节点。其他未被修改波及的子树，其引用将直接被旧实例共同持有与共享。同样，这样的一次添加操作的时间复杂度从 O(n) 降低到了 O(log n)，因为只需要复制路径上的节点，而不是整个树。

局限性

很显然，ImmutableDictionary的访问速度在平均情况下是不如哈希表的，因为它需要进行树的遍历来查找键值对，而哈希表通过计算哈希值可以直接定位到桶的位置。

同时，它的内存访问模式并不友好，因为树结构的节点在内存中是分散的，这会导致更多的 GC 压力，从而影响性能。

OrderedDictionary

在实际业务开发中，有可能遇到一个需求：既需要哈希表那种极速键值查找，又必须保持元素的插入顺序。

在很长一段时间里，.NET 只提供了一个非泛型的 System.Collections.Specialized.OrderedDictionary。正如前文对早期 Hashtable 的分析一样，它同样面临着 object 带来的装箱与拆箱性能损耗以及类型安全问题。为了规避这些问题，开发者们往往不得不自己去造轮子，比如在内部同时维护一个 List<T>（用于保序）和一个 Dictionary<TKey, TValue>（用于查找），但这无疑带来了双倍的内存开销和状态同步的复杂性。

在 .NET 9 中，微软终于在 System.Collections.Generic 命名空间下引入了它的泛型版本 OrderedDictionary<TKey, TValue>。

兼顾索引与哈希

OrderedDictionary 最大的特点是它同时支持通过键和通过索引来访问元素：

OrderedDictionary<string, int> dict = new()
{
    ["a"] = 1,
    ["b"] = 2,
    ["c"] = 3
};
dict.Add("d", 4);
dict.Insert(0, "e", 5);        // 支持在特定索引处插入

Console.WriteLine(dict[0]);    // 通过索引访问，输出 5
Console.WriteLine(dict["b"]);  // 通过键访问，输出 2

底层实现与权衡

普通的 Dictionary 在刚开始追加插入时其实也是有顺序的，但一旦发生 Remove 操作，它会通过 _freeList（空闲链表）将原位置的值去掉，后续再 Add 元素时会优先填补这些空缺。这就导致常规字典在经历过增删后，遍历顺序会与插入顺序完全脱节。

而 OrderedDictionary<TKey, TValue> 为了保证任何时候的严格连续和保序，它的底层在维护哈希桶的同时，内部存储键值的数组是始终保持紧凑且按顺序排列的。

当你从OrderedDictionary删除或插入一个元素时，为了维护内部数组的连续性和顺序，它必须进行数组元素的块移动（Shifting）。这意味着它的删除和特定位置插入操作的时间复杂度退化成了 O(n)。

因此，OrderedDictionary 非常适合于需要保持严格顺序、高频读取和追加，但极少在中间进行删除的场景（例如解析保序的 JSON 对象、维护 UI 渲染列表的数据源等），但如果你需要在中间频繁地进行删除操作，它的性能表现会受到明显限制。

FrozenDictionary

在经历了字典、并发字典和不可变字典的演进后，微服务架构的兴起带来了新的需求：在某些场景下，我们需要一个只读的、线程安全的字典。

考虑一个业务场景，一个 ASP.NET App 启动时，需要从数据库和配置文件中加载一个带有国际化、路由表什么的巨型字典，这个字典在运行时是不会被修改的，但需要频繁地被访问。

相对于普通的Dictionary总是要处理潜在的冲突，而FrozenDictionary在设计上就假设了它的内容在创建后是不会被修改的，因此它可以将每个键都放在哈希表中，由于位置可以立即确定，无需要处理碰撞问题，这样就提升了访问性能。

反着想，既然FrozenDictionary需要在一开始最优地处理键值对，那么它的构建过程就会非常慢，因为它需要对所有的键进行哈希计算和位置调整，以确保没有碰撞发生。

那么，FrozenDictionary的核心在于它在初始化的时候发生了什么。

根据键来初筛

我们可以借助.ToFrozenDictionary()方法来创建一个FrozenDictionary实例。观察源代码的第一个if注释：

Optimize for value types when the default comparer is being used. In such a case, the implementation may use {Equality}Comparer.Default.Compare/Equals/GetHashCode directly, with generic specialization enabling the Equals/GetHashCode methods to be devirtualized and possibly inlined.

如果TKey是一个值类型，并且使用了默认的比较器，那么在构建FrozenDictionary时，可以直接使用EqualityComparer<TKey>.Default来进行比较和哈希计算，这样就可以利用泛型的特性来实现方法的去虚化和内联，从而提升性能。

其中，对于int类型，我们可以直接将键的存储位置和哈希值的存储位置合并，因为int类型的键本身就是一个哈希值，这样就避免了额外的内存开销和访问层级。

第二个if注释提到：

Optimize for string keys with the default, Ordinal, or OrdinalIgnoreCase comparers. If the key is a string and the comparer is known to provide ordinal (case-sensitive or case-insensitive) semantics, we can use an implementation that’s able to examine and optimize based on lengths and/or subsequences within those strings.

如果TKey是一个字符串，并且使用了默认的比较器或者是Ordinal、OrdinalIgnoreCase比较器，那么在构建FrozenDictionary时，可以利用字符串的特性来进行优化，比如根据字符串的长度或者子序列来快速定位键的位置，从而提升访问性能。

构建策略

整个类藏了很多不同的底层实现类，根据上一个步骤的分析结果，FrozenDictionary会选择不同的构建策略来创建内部的数据结构，以确保在访问时能够达到最佳性能。比如SmallValueTypeComparableFrozenDictionary、Int32FrozenDictionary、ValueTypeDefaultComparerFrozenDictionary等等。

这些类都是internal的，意味着它们是FrozenDictionary的内部实现细节，外部用户并不需要关心它们的存在，只需要通过FrozenDictionary提供的接口来使用即可。如果你对它们的实现细节感兴趣，可以直接查看源代码来了解它们是如何根据不同的键类型和比较器来优化访问性能的。

如果哪个优化都没有命中，那么就会退回到一个通用的实现（DefaultFrozenDictionary -> KeysAndValuesFrozenDictionary）。

总结

从Hashtable到Dictionary的优化，再到ConcurrentDictionary、ImmutableDictionary、OrderedDictionary和FrozenDictionary对不同场景的适配。随着 .NET 10 的到来，JIT 介入、逃逸分析、零拷贝 Span 等技术的引入，我们应当继续关注这些数据结构在性能和内存方面的优化，选择最适合我们业务场景的实现来使用。