c# - .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
}

所以这在大多数情况下都有效，但在极少数情况下，两个实际上不同的 Thingys 具有相同的哈希码。

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

字典是这种情况，还是只解决散列码不同但 (hash % size) 相同的冲突？如果这行不通，还有什么可能？

Answer 1

哈希冲突只会影响性能，不会影响完整性。

一个简单的测试是将 GetHashCode() 更改为简单地返回 1;。您会注意到字典仍然可以正常运行，但对于任何合理的数据集，它的性能都会非常糟糕。