16

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

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

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

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 <Thingy, int> 放入我的 Thingys 的位置，并使用从字典中出来的顺序值作为我的实际键吗？我想知道字典在检测到罕见的哈希码冲突时是否会调用我的 Equals 方法，确定对象实际上是不同的，并以不同的方式存储它们。然后我在查找它时进行成像，它会看到一个用于该哈希的存储桶并搜索正确的东西，再次使用 Equals 进行比较。

字典是这种情况，还是仅解决哈希码不同但（哈希％大小）相同的冲突？如果这行不通，有什么可能？

4

3 回答 3

27

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

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

于 2010-02-10T20:52:39.070 回答
19

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

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

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

于 2010-02-10T20:53:03.000 回答
1

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

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

于 2010-02-11T00:50:58.640 回答