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

Question

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

在c#的Dictionary容器中发生哈希冲突的情况下，它会怎样处理？它甚至能够检测到冲突吗？

在SDL中类似容器发生冲突的情况下，有些会使键值部分链接数据到键值部分，例如链表，而有些则会尝试找到不同的哈希方法。

[更新时间 10:56 上午 6/4/2010]

我正在尝试制作每个用户的计数器。并且设置用户号未定义，可以增加或减少。我预计数据大小将超过1000。

所以，这是我的要求：

• 快速访问，最好不要是O(n)，因为要求很重要，我需要确保在人们执行某些愚蠢的操作之前可以强制注销他们，因此接近O(1)非常重要。
• 动态增长和缩小。
• 唯一的数据。

哈希映射是我的解决方案，似乎在C#中，Dictionary与哈希映射类似...

- Anatoli

---

你能否提供更多关于为什么需要了解这个的信息？Dictionary<TKey,TValue> 只被定义为在冲突的哈希码值面前能够正确地运行。任何关于它如何实现的信息都是实现细节，可能会在不同版本之间发生变化。 - JaredPar

从.NET 3.5开始，您最好使用HashSet<T>（https://msdn.microsoft.com/en-us/library/bb359438(v=vs.110).aspx）。如果发生哈希冲突，则对象将进入下一个可用的桶中。有关完整详细信息，请参见参考源（http://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs,2d265edc718b158b），例如“容量始终是质数；因此，在调整大小期间，容量被选择为大于上一容量两倍的下一个质数。”不幸的是，没有构造函数接受容量，但是您可以在填充集后调用TrimExcess。 - yoyo

Answer 1

哈希碰撞被Dictionary<>正确处理了- 只要一个对象正确实现了 GetHashCode() 和 Equals()，字典将返回相应的实例。

首先，您不应该对 Dictionary<> 的内部工作方式做任何假设 - 这是可能随时间变化而更改的实现细节。话虽如此....

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

从性能的角度来看，您还可能需要提供一个实现 GetHashCode() 生成良好散布值的方法，以减少哈希碰撞的频率。哈希碰撞的主要缺点是将字典转换为列表，性能下降。每当两个不同的对象实例产生相同的哈希码时，它们被存储在字典的同一个内部桶中。这将导致必须进行线性扫描，在每个实例上调用 Equals() 直到找到匹配项。

- LBushkin

---

顺便提一下，你可以使用Redgate .NET Reflector查看实际实现，但LBushkin是正确的，它很可能随着时间的推移而改变，所以不要指望它。 - Aren

但是你知道在哈希冲突的情况下它是否会将哈希表容量加倍吗？因为这对我来说可能太昂贵了。 - Anatoli

从代码来看，似乎只有在整个字典已满时才会调用.Resize()函数。当前的实现似乎是在发生冲突时找到下一个桶，但这只是我对反向工程IL的解释，所以您可以自行理解。 - Aren

@Ankiov：你使用哪种运行时环境，有哪些数据负载，让你感到担忧？你是否在使用.NET Compact框架？实现方式可能与客户端版本不同（例如，在Windows Phone上，BCL和CLR有略微不同的版本）。 - LBushkin

它是在普通的.NET框架上，而不是移动或任何紧凑型框架上。但让我担心的是数据大小可能会显著增长。@Aren B：非常感谢！ - Anatoli

Answer 2

根据MSDN上的这篇文章，在哈希冲突的情况下，Dictionary类会将桶(bucket)转换为链表。另一方面，旧的HashTable类则使用rehashing(再哈希)。

- JSBձոգչ

Answer 3

我提供了一种替代方案，演示了一个字典在添加具有不同键但哈希码相同的两个项时将表现出无异常且功能上正确的行为。

在 .Net 4.6 中，字符串 "699391" 和 "1241308" 产生相同的哈希码。下面的代码会发生什么？

myDictionary.Add( "699391", "abc" );
myDictionary.Add( "1241308", "def" );

以下代码演示了 .Net 字典接受不同的键值，导致哈希冲突。没有抛出异常，并且字典键查找返回了预期的对象。

代码演示 .Net 字典可接受不同键发生哈希冲突，无异常抛出，键查找仍符合预期。

var hashes = new Dictionary<int, string>();
var collisions = new List<string>();

for (int i = 0; ; ++i)
{
    string st = i.ToString();
    int hash = st.GetHashCode();

    if (hashes.TryGetValue( hash, out string collision ))
    {
        // On .Net 4.6 we find "699391" and "1241308".
        collisions.Add( collision );
        collisions.Add( st );
        break;
    }
    else
        hashes.Add( hash, st );
}
Debug.Assert( collisions[0] != collisions[1], "Check we have produced two different strings" );
Debug.Assert( collisions[0].GetHashCode() == collisions[1].GetHashCode(), "Prove we have different strings producing the same hashcode" );

var newDictionary = new Dictionary<string, string>();
newDictionary.Add( collisions[0], "abc" );
newDictionary.Add( collisions[1], "def" );

Console.Write( "If we get here without an exception being thrown, it demonstrates a dictionary accepts multiple items with different keys that produce the same hash value." );

Debug.Assert( newDictionary[collisions[0]] == "abc" );
Debug.Assert( newDictionary[collisions[1]] == "def" );

- camelCase

Answer 4

请查看此链接以获取良好的解释：使用 C# 2.0 进行数据结构广泛研究

基本上，.NET 泛型字典将具有相同哈希值的项链接在一起。

- vgru