在Dictionary键中发生哈希冲突会发生什么？

Question

我一直用c ++和java编写我的生活,但在C#上,我觉得这是一个完全不同的动物.

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

在SDL中类似容器中发生冲突的情况下,有些会使键值部分将数据链接到键值部分,如链表,或者有些人会尝试找到不同的哈希方法.

[2010年6月4日上午10:56更新]

我试图为每个用户制作一个计数器.并且设置用户#没有定义,它可以增加或减少.我期待数据的大小超过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()在每个实例上调用,直到找到匹配为止.

Answer 2

根据MSDN上的这篇文章,在哈希冲突的情况下,Dictionary类将桶转换为链表.HashTable另一方面,较旧的班级使用rehashing.

Answer 3

我提供了一个替代的面向代码的答案,它演示了当添加了两个具有不同键的项但键产生相同的哈希码时,Dictionary将表现出无异常和功能正确的行为.

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

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

以下代码演示了.Net Dictionary接受导致哈希冲突的不同键.不会抛出异常,字典键查找返回预期的对象.

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" );