哈希冲突是通过链式法解决的。1. dictionary内部使用桶数组，每个桶关联一个链表结构；2. 当不同键映射到同一桶时，键值对被添加到该桶链表的尾部；3. 查找时先通过哈希码定位桶，再遍历链表用equals()方法精确匹配键；4. 这种机制确保冲突时数据不会丢失，但会降低查找效率，因此需要好的哈希函数减少冲突。
<img src="https://img.php.cn/upload/article/001/221/864/175817095498370.jpg" alt="C#的Dictionary是如何存储键值对的？”>
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号告诉你这本书应该放在哪个书架（桶）。但问题是，可能有很多本书都被分到了“历史类”的同一个书架。这时候，图书馆管理员不会把旧书扔掉，而是把这些书一本接一本地排在这个书架上。当你需要找某本书时，你先找到对应的书架，然后在这个书架上逐本查找，直到找到你想要的那一本。
在
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()
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
。
当自定义类型作为
Dictionary
的键时，务必正确重写这两个方法。否则，你可能会遇到各种难以调试的诡异行为，或者
Dictionary
的性能远低于你的预期。我个人在项目中遇到过多次因为
GetHashCode()
实现不当导致的性能瓶颈，调试起来确实让人头疼，所以这方面的投入绝对值得。
以上就是C#的Dictionary是如何存储键值对的？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1439666.html
微信扫一扫 
支付宝扫一扫 
