.NET 字典解决冲突的效果如何？

Question

我遇到了需要为表设置键的自定义对象的问题。我需要生成一个唯一的数字键。我遇到了碰撞问题，我想知道是否可以利用字典来帮助我。假设我有一个像这样的对象：

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

等等，还有更多字段。假设 Foo 和 Bar 是我的关键字段 - 如果它们在两个 Thingy 之间相等，那么这两个对象应该被认为是相等的（一个可能代表对另一个的更新，而其他字段正在更新。）所以我有这些

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
}

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

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

字典就是这种情况，还是它只解决散列码不同但（散列％大小）相同的冲突？如果这行不通，那还有什么办法呢？

Answer 1

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

一个简单的测试是将 GetHashCode() 更改为仅返回 1;。您会注意到字典仍然表现正常，但对于任何合理的数据集，它都会表现得很糟糕。

Answer 2

哈希冲突主要会影响性能 - 而不是正确性。只要 Equals() 行为正确。

Dictionary 使用哈希码作为将项目组织到单独的“存储桶”中的方式。如果太多项共享相同的哈希码，您可能会遇到性能问题。但是，只要 Equals() 能够正确区分实例，您就应该得到正确的结果。

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

Answer 3

GetHashCode 设计用于哈希表，需要最大限度地减少冲突，但不能消除冲突。如果您需要生成真正唯一的密钥，GetHashCode 是一个合理的起点（并且不像 guid 那样长），但是您需要将密钥存储为对象的一部分，并单独维护已使用密钥的列表。

虽然您可能能够从 Dictionary 的内部检索看起来可用的内容，但它可能无法可靠地工作 - 例如，如果您添加的项目多于字典最初分配处理的项目，则底层数据结构将被重建并单独项目可能最终出现在字典中完全不同的部分。