.NET字典如何解决冲突？

Question

我有一个需要键入表的自定义对象的问题.我需要生成一个唯一的数字键.我有碰撞问题,我想知道我是否可以利用字典来帮助我.假设我有一个这样的对象:

class Thingy
{
    public string Foo;
    public string Bar;
    public string Others;
}

等等有更多领域.让我们说Foo和Bar是我的关键字段 - 如果它们在两个Thingys之间相等,那么这两个对象应该被认为是相等的(一个可能代表对另一个的更新,其他字段正在更新.)所以我有这些:

public override bool Equals(object obj)
{
    Thingy thing = (Thingy)obj; // yes I do type check first
    return (this.Foo == thing.Foo && this.Bar == thing.Bar);
}

public override int GetHashCode()
{
    return (this.Foo + this.Bar).GetHashCode(); // using default string impl
}

所以这在很大程度上是有效的,但是在极少数情况下,两个实际上不同的Thing具有相同的哈希码.

我的问题是:我可以使用词典<Thingy, int>我放在我的Thingys中,并使用字典中的顺序值作为我的实际键吗？我想知道,当检测到罕见的哈希代码冲突时,字典是否会调用我的Equals方法,确定对象实际上是不同的,并以不同方式存储它们.我在查找时进行成像,它会看到该哈希的桶并搜索正确的Thingy,再次使用Equals进行比较.

这是字典的情况,还是仅解决哈希码不同的冲突,但(哈希值大小)是否相同？如果这不起作用,可能会怎样？

Answer 1

散列冲突只影响性能,而不影响完整性.

一个简单的测试是将GetHashCode()改为简单地返回1;.你会注意到字典仍然表现得很好,但是对于任何合理的数据集,它都会表现得非常糟糕.

Answer 2

散列冲突主要影响性能 - 而不是正确性.只要Equals()行为正确.

Dictionary使用哈希码作为将项目组织成单独的"桶"的方法.如果太多项共享相同的哈希代码,则可能会遇到性能问题.但是,只要Equals()能够正确区分实例,就应该得到正确的结果.

哈希码可能导致问题的地方是可变对象.如果您的Thingy类允许Foo或Bar更改字典中的项目,则可能无法在后续访问尝试中找到它.这是因为现在生成的哈希码与用于在字典中存储值的哈希码不同.