C#的Dictionary是如何存储键值对的？-C#.Net教程-PHP中文网

哈希冲突是通过链式法解决的。1. dictionary内部使用桶数组，每个桶关联一个链表结构；2. 当不同键映射到同一桶时，键值对被添加到该桶链表的尾部；3. 查找时先通过哈希码定位桶，再遍历链表用equals()方法精确匹配键；4. 这种机制确保冲突时数据不会丢失，但会降低查找效率，因此需要好的哈希函数减少冲突。

C#的Dictionary<TKey, TValue>是如何存储键值对的？

C#的

Dictionary<TKey, TValue>

登录后复制

，在它的核心，其实是一个高度优化的哈希表（Hash Table）实现。它通过将键（Key）映射到内部存储数组的特定位置来高效地存储和检索键值对（Key-Value Pair），这种映射过程主要依赖于键的哈希码。

Dictionary

登录后复制

的内部存储机制，可以概括为以下几个关键步骤和组件：

当你向

Dictionary

登录后复制

添加一个键值对时，它会做的第一件事是调用你提供的键（

TKey

登录后复制

类型）的

GetHashCode()

登录后复制

方法。这个方法会返回一个整数，也就是该键的哈希码。这个哈希码并不直接是数据在内存中的地址，而是一个用于计算存储位置的“指纹”。

接着，

Dictionary

登录后复制

会利用这个哈希码，通过一个内部算法（通常是取模运算），将其映射到内部数组的一个特定索引，这个数组就是我们常说的“桶”（Bucket）数组。每个桶可能存储一个或多个键值对。

这里就引出了一个核心问题：不同的键可能会生成相同的哈希码（哈希冲突），或者即使哈希码不同，它们也可能被映射到同一个桶里。

Dictionary

登录后复制

处理这种情况的方式是“链式法”（Chaining）。它不会直接覆盖掉旧的数据。相反，每个桶实际上是一个链表（或类似链表的数据结构，比如一个内部的

Entry

登录后复制

结构数组，通过索引链接起来），当发生冲突时，新的键值对会被添加到该桶的链尾。

当你尝试通过键来查找值时，

Dictionary

登录后复制

会再次计算该键的哈希码，找到对应的桶。然后，它会遍历该桶内的所有键值对。在这个遍历过程中，它不仅仅是比较哈希码，更重要的是会调用键的

Equals()

登录后复制

方法来逐一比对，以确保找到的是完全匹配的那个键。只有当哈希码相同且

Equals()

登录后复制

方法返回

true

登录后复制

时，才认为找到了目标键。

当

Dictionary

登录后复制

中存储的元素数量达到一定阈值（通常是内部容量的某个比例，即“负载因子”），为了保持查询效率，它会自动进行扩容操作。这意味着它会创建一个更大的内部数组，并将所有现有的键值对重新计算哈希码并重新分配到新的桶中。这个过程被称为“重新哈希”（Rehashing），它虽然会带来一定的性能开销，但却是确保

Dictionary

登录后复制

长期高效运行的关键。

哈希冲突是如何解决的？

哈希冲突是任何基于哈希表的数据结构都无法避免的现象，毕竟哈希码的范围是有限的（

int

登录后复制

的范围），而可能的键值组合是无限的。C#的

Dictionary

登录后复制

解决哈希冲突的主要策略是“链式法”（Chaining）。

具体来说，

Dictionary

登录后复制

内部维护了一个桶（bucket）数组。每个桶可以看作是一个“槽位”。当多个键经过哈希函数计算后，被映射到同一个桶索引时，这些键值对并不会互相覆盖。相反，它们会被存储在与该桶关联的一个“链”上。这个链并不是传统意义上的

LinkedList<T>

登录后复制

，而是在

Dictionary

登录后复制

内部实现中，通过在

Entry

登录后复制

结构体中存储下一个冲突项的索引来模拟链表行为。

想象一下，你有一个巨大的图书馆，每本书都有一个唯一的ISBN号（键）。哈希函数就像是图书馆的分类系统，它根据ISBN号告诉你这本书应该放在哪个书架（桶）。但问题是，可能有很多本书都被分到了“历史类”的同一个书架。这时候，图书馆管理员不会把旧书扔掉，而是把这些书一本接一本地排在这个书架上。当你需要找某本书时，你先找到对应的书架，然后在这个书架上逐本查找，直到找到你想要的那一本。

存了个图

视频图片解析/字幕/剪辑，视频高清保存/图片源图提取

查看详情

在

Dictionary

登录后复制

中，当查找一个键时，它会先根据哈希码定位到对应的桶，然后遍历这个桶里所有的“链”上的键值对，逐一调用键的

Equals()

登录后复制

方法进行精确比较。只有哈希码和

Equals()

登录后复制

都匹配，才算真正找到了目标。这种机制保证了即使哈希冲突发生，所有键值对也能被正确存储和检索，只不过在冲突严重的桶里，查找效率会从O(1)接近O(N)，其中N是该桶中的元素数量。这也就是为什么设计良好的

GetHashCode()

登录后复制

方法如此重要——它能尽量减少冲突，让桶里的链短一些。

为什么选择哈希表而不是其他数据结构？

这是一个很好的问题，它触及了数据结构选择的核心。

Dictionary

登录后复制

之所以选择哈希表作为其底层实现，根本原因在于它能在平均O(1)的时间复杂度内完成插入、删除和查找操作。这个“平均O(1)”是其最大的魅力和优势，对于大多数应用场景来说，这种近乎即时的数据访问速度是无与伦比的。

我们来对比一下其他常见的数据结构：

数组（Array）/列表（List）： 查找特定元素通常需要O(N)的时间复杂度（线性扫描），除非是有序数组并使用二分查找（O(logN)）。插入和删除在中间位置更是O(N)。虽然内存连续，访问速度快，但键值对的随机访问效率远不如哈希表。
链表（LinkedList）： 插入和删除操作在已知节点位置时是O(1)，但查找特定元素仍是O(N)。它不适合需要快速随机访问的场景。
平衡二叉搜索树（如
SortedDictionary
登录后复制
使用的红黑树）：插入、删除和查找操作的时间复杂度都是O(logN)。这比哈希表在最坏情况下的O(N)要稳定，因为它保证了树的高度是平衡的。然而，O(logN)仍然不如平均O(1)快，尤其是在数据量非常大的时候，
```
logN
```
登录后复制
的开销累积起来也相当可观。此外，树结构需要键是可比较的，并且维护树的平衡也需要额外的开销。

哈希表的优势在于，它试图通过哈希函数将键直接“映射”到存储位置，从而跳过大量的比较和遍历。当然，这依赖于一个好的哈希函数和合理的负载因子来最小化冲突。在我看来，这种“空间换时间”的策略（为了哈希表可能需要预留一些空桶或在扩容时复制数据）在现代计算机内存充足的情况下，是非常划算的。它提供了一种极佳的平衡，既能快速访问数据，又能灵活地处理动态变化的键值对集合。

键的

GetHashCode()

登录后复制

和

Equals()

登录后复制

方法对Dictionary性能有何影响？

这绝对是使用

Dictionary

登录后复制

时最容易被忽视，但又至关重要的一点。

GetHashCode()

登录后复制

和

Equals()

登录后复制

方法的正确实现，直接决定了

Dictionary

登录后复制

的性能和行为是否符合预期。

首先，

GetHashCode()

登录后复制

方法。它的主要职责是为对象生成一个尽可能唯一且分布均匀的哈希码。当

GetHashCode()

登录后复制

实现得不好时，比如：

生成大量重复的哈希码： 如果很多不同的键都返回相同的哈希码，那么它们都会被映射到同一个桶中，导致该桶的链变得非常长。这使得查找操作从理想的O(1)退化到接近O(N)，因为
```
Dictionary
```
登录后复制
需要遍历这个长链来找到正确的键。这就像图书馆里所有书都被分到了同一个书架，找书就变得极其困难。
哈希码分布不均匀： 如果哈希码集中在少数几个值上，也会导致某些桶过于拥挤，而其他桶则空空如也，同样影响效率。
哈希码随时间变化： 如果一个对象的哈希码在其作为
```
Dictionary
```
登录后复制
的键期间发生了变化（比如你把一个可变对象的某个属性作为哈希码的计算依据，然后又修改了这个属性），那么
```
Dictionary
```
登录后复制
将无法正确找到或删除这个键值对，因为它的哈希码和对应的桶位置已经“变”了。这是非常危险的，会导致数据丢失或不一致。

其次，

Equals()

登录后复制

方法。它的作用是在哈希冲突发生时，以及在定位到特定桶后，用于精确比较两个键是否逻辑相等。如果

Equals()

登录后复制

实现不正确：

返回错误结果： 如果
```
Equals()
```
登录后复制
错误地认为两个不相等的对象相等，或者两个相等的对象不相等，那么
```
Dictionary
```
登录后复制
可能会返回错误的值，或者无法找到本应存在的键。
性能开销过大： 如果
```
Equals()
```
登录后复制
方法执行了复杂的计算或I/O操作，那么在冲突严重的桶中，频繁调用
```
Equals()
```
登录后复制
会显著降低性能。

总结来说，一个理想的

GetHashCode()

登录后复制

应该满足以下条件：

对于相等的对象（即
```
Equals()
```
登录后复制
返回
```
true
```
登录后复制
的对象），
```
GetHashCode()
```
登录后复制
必须返回相同的哈希码。
对于不相等的对象，
```
GetHashCode()
```
登录后复制
应尽量返回不同的哈希码，以减少冲突。
哈希码的计算应该快速且稳定（对于不可变对象，哈希码一旦计算就不应改变）。

而

Equals()

登录后复制

方法则应保证：

自反性：
```
x.Equals(x)
```
登录后复制
为
```
true
```
登录后复制
。
对称性：
```
x.Equals(y)
```
登录后复制
为
```
true
```
登录后复制
当且仅当
```
y.Equals(x)
```
登录后复制
为
```
true
```
登录后复制
。
传递性：如果
```
x.Equals(y)
```
登录后复制
为
```
true
```
登录后复制
且
```
y.Equals(z)
```
登录后复制
为
```
true
```
登录后复制
，那么
```
x.Equals(z)
```
登录后复制
也为
```
true
```
登录后复制
。
一致性：只要对象不被修改，多次调用
```
Equals()
```
登录后复制
应返回相同结果。
```
x.Equals(null)
```
登录后复制
为
```
false
```
登录后复制
。