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

这个方法在大多数情况下是有效的，但很少有两个不同的Thingys拥有相同的哈希码。

我的问题是：我能否使用Dictionary<Thingy, int>，把我的Thingys放进去，然后使用从字典中出来的连续值作为我的实际键？ 我想知道，当Dictionary检测到罕见的哈希码冲突时，它是否会调用Equals方法，确定对象实际上是不同的，并以不同方式存储它们。那么查找时，它将看到该哈希的桶并搜索正确的Thingy，再次使用Equals进行比较。

这种情况是否适用于字典，或者它只解决哈希码不同但（hash％size）相同的冲突？如果这样行不通，还有什么其他解决方法吗？

- Tesserex

Answer 1

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

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

- Bob

Answer 2

哈希碰撞主要影响性能而不是正确性，只要Equals()函数正常工作。

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

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

- LBushkin

---

这实际上适用于任何字典。所有类型的字典都假定键是常量。 - Joel

对于可变对象，通常应该保持基本的object.Equals()方法不变，因为它返回引用相等性。你通常希望使用==重载来测试值相等性。因此，如果你保持默认的object.Equals()不变，就可以在没有副作用的情况下将可变对象用作字典键。 - Bob

在非不可变类型中覆盖运算符==通常不被推荐。MSDN文档实际上讨论了您可能想要重写Object.Equals()和==运算符的情况。http://msdn.microsoft.com/en-us/library/ms173147%28VS.80%29.aspx - LBushkin

以前没有读过那篇文章。了解正确的语义和最佳实践总是很好的。谢谢！ - Bob

Answer 3

GetHashCode旨在用于哈希表中，其中需要最小化但不需要消除冲突。如果您需要生成真正独特的密钥，则GetHashCode是一个合理的起点（并且不像guid那样过长），但您需要将密钥作为对象的一部分存储，并单独维护已使用密钥的列表。

虽然您可能能够从Dictionary的内部检索出看起来可用的内容，但它可能不可靠 - 例如，如果添加的项超过了字典最初分配的处理能力，则底层数据结构将被重建，个别项可能会出现在完全不同的字典部分。

- Tom Clarkson

---

实际上，我使用字典的意思是将对象存储为字典的键，然后将一个新的最高整数作为值存储，并将该值用作表的键。因此，字典中的值是连续的，如果我查找一个对象，我将得到表的唯一数字键。因此，内部字典结构是无关紧要的。 - Tesserex

因此，实际上您正在使用字典将另一个属性添加到对象中 - 如果您正在使用可以控制的自定义对象，则这并不是最有效的方法。 - Tom Clarkson