C#的Dictionary是如何存储键值对的？

星降

发布时间：2025-09-18 12:49:01

396人浏览过

来源于php中文网

原创

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

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

C#的

Dictionary

，在它的核心，其实是一个高度优化的哈希表（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

，而是在

Dictionary

内部实现中，通过在

Entry

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

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

Android 本地数据存储中文WORD版

本文档主要讲述的是Android 本地数据存储；对于需要跨应用程序执行期间或生命期而维护重要信息的应用程序来说，能够在移动设备上本地存储数据是一种非常关键的功能。作为一名开发人员，您经常需要存储诸如用户首选项或应用程序配置之类的信息。您还必须根据一些特征（比如访问可见性）决定是否需要涉及内部或外部存储器，或者是否需要处理更复杂的、结构化的数据类型。跟随本文学习 Android 数据存储 API，具体来讲就是首选项、SQLite 和内部及外部内存 API。希望本文档会给有需要的朋友带来帮助；感兴趣的朋友可以

下载

在

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()
```
应尽量返回不同的哈希码，以减少冲突。
哈希码的计算应该快速且稳定（对于不可变对象，哈希码一旦计算就不应改变）。

而