c# - 当字典键发生哈希冲突时会发生什么？

Question

我一生都在用 C++ 和 Java 编写代码，但在 C# 上，我觉得它是一种完全不同的动物。

如果在 C# 中的 Dictionary 容器中发生哈希冲突，它会做什么？或者它甚至检测到碰撞？

如果SDL中类似容器发生冲突，有些会像链表一样将键值部分的数据链接到键值部分，或者有些会尝试找到不同的哈希方法。

[更新 10:56 A.M. 2010 年 6 月 4 日]

我正在尝试为每个用户制作一个计数器。而set user#是没有定义的，既可以增加也可以减少。我预计数据大小会超过 1000。

所以，我想:

• 快速访问最好不是 O(n)，重要的是我有接近 O(1) 的需求，我需要确保我可以在人们能够执行一些愚蠢的事情之前强制注销他们。
• 动态增长和收缩。
• 独特的数据。

Hashmap 是我的解决方案，似乎 Dictionary 类似于 c# 中的 hashmap...

Answer 1

散列冲突由 Dictionary<> 正确处理 - 只要对象实现 GetHashCode()和 Equals()正确，将从字典中返回适当的实例。

首先，您不应该对 Dictionary<> 的方式做出任何假设。在内部工作——这是一个可能会随着时间而改变的实现细节。话虽如此……

您应该关心的是您用于键的类型是否实现了 GetHashCode()和 Equals() 基本规则是 GetHashCode()必须在对象的生命周期内返回相同的值，并且 Equals()当两个实例表示同一个对象时必须返回 true。除非你覆盖它，Equals()使用引用相等性——这意味着它仅在两个对象实际上是同一实例时才返回 true。您可以覆盖 Equals() 的方式可行，但是您必须确保两个“相等”的对象也产生相同的哈希码。

从性能的角度来看，您可能还想提供 GetHashCode() 的实现生成良好的值传播以减少哈希码冲突的频率。 哈希码冲突的主要缺点是，它会在性能方面将字典缩减为列表。每当两个不同的对象实例产生相同的哈希码时，它们就会存储在字典的同一个内部桶中。这样做的结果是必须执行线性扫描，调用 Equals()在每个实例上，直到找到匹配项。