13

好的，在您因为互联网上发布了数百个类似的问题而生气之前，我可以向您保证，我刚刚花了几个小时阅读了所有这些问题，但还没有找到我问题的答案。

背景：

基本上，我的一个大型应用程序遇到了这样一种情况，即属性Binding上的某些 sListBox.SelectedItem将停止工作，或者在对当前选定的项目进行编辑后程序会崩溃。我最初询问“已添加具有相同键的项目”从此处的代码问题中选择 ListBoxItem 的异常，但没有得到答案。

直到本周我才有时间解决这个问题，当时我有几天的时间来解决这个问题。现在长话短说，我找到了问题的原因。这是因为我的数据类型类已经覆盖了Equals方法，因此也覆盖了方法GetHashCode。

现在对于那些不知道这个问题的人，我发现你只能使用不可变字段/属性来实现该GetHashCode方法。使用 Harvey Kwok 对Overriding GetHashCode()帖子的回答的摘录来解释这一点：

问题是 Dictionary 和 HashSet 集合使用 GetHashCode 将每个项目放入存储桶中。如果hashcode是根据一些可变字段计算出来的，而对象放入HashSet或Dictionary后，字段确实发生了变化，则无法再从HashSet或Dictionary中找到该对象。

所以实际问题是因为我在GetHashCode而引起的。当用户在 UI 中更改这些属性值时，对象的相关哈希码值会更改，然后无法在其集合中找到项目。

问题：

所以，我的问题是处理需要GetHashCode在没有不可变字段的类中实现方法的情况的最佳方法是什么？对不起，让我更具体一些，因为那个问题被问过了。

Overriding GetHashCode()帖子中的答案表明，在这些情况下，最好简单地返回一个常量值......有些人建议返回该值1，而另一些人建议返回一个素数。就个人而言，我看不出这些建议之间有任何区别，因为我原以为它们中的任何一个都只会使用一个存储桶。

此外，Eric Lippert 博客中GetHashCode 的指南和规则文章有一个标题为指南的部分：哈希码的分布必须是“随机的”，这突出了使用导致没有使用足够存储桶的算法的缺陷。他警告说，算法会减少使用的存储桶数量，并在存储桶变得非常大时导致性能问题。当然，返回一个常量就属于这一类。

我有一个想法，为我的所有数据类型类（仅在 C# 中，而不是数据库中）添加一个额外的Guid字段，专门用于并且仅在GetHashCode方法中使用。所以我想在这个长长的介绍结束时，我的实际问题是哪个实现更好？总结一下：

概括：

在没有不可变字段的类中重写 Object.GetHashCode() 时，最好从GetHashCode方法中返回一个常量，还是为每个类创建一个附加readonly字段，仅在GetHashCode方法中使用？如果我应该添加一个新字段，它应该是什么类型，然后我不应该将它包含在Equals方法中？

虽然我很高兴收到任何人的回答，但我真的希望能收到对这个主题有深入了解的高级开发人员的回答。

4

5 回答 5

16

回到基础。你读了我的文章；再读一遍。与您的情况相关的两条铁定规则是：

  • 如果 x 等于 y，则 x 的哈希码必须等于 y 的哈希码。等效地：如果 x 的哈希码不等于 y 的哈希码，则 x 和 y 必须不相等。
  • 当 x 在哈希表中时，x 的哈希码必须保持稳定。

这些是正确性的要求。如果您不能保证这两个简单的事情，那么您的程序将不正确。

您提出了两种解决方案。

您的第一个解决方案是您始终返回一个常量。这满足了这两个规则的要求，但是您将在哈希表中进行线性搜索。你不妨使用一个列表。

您提出的另一个解决方案是以某种方式为每个对象生成一个哈希码并将其存储在对象中。这是完全合法的，前提是相同的项目具有相同的哈希码。如果你这样做，那么你会受到限制，如果哈希码不同，x 等于 y必须为假。这似乎使价值平等基本上是不可能的。因为如果你想要引用相等，你首先不会覆盖 Equals，这似乎是一个非常糟糕的主意，但只要 equals 是一致的，它就是合法的。

我提出第三种解决方案，那就是：永远不要将你的对象放在哈希表中，因为哈希表首先是错误的数据结构。哈希表的目的是快速回答“这个给定值是否在这组不可变值中？”的问题。而且你没有一组不可变的值，所以不要使用哈希表。为工作使用正确的工具。使用列表，忍受线性搜索的痛苦。

第四种解决方案是：对用于相等性的可变字段进行散列，在每次变异之前从它所在的所有散列表中删除对象，然后再将其放回。这满足了两个要求：哈希码符合相等性，并且哈希表中对象的哈希是稳定的，并且您仍然可以获得快速查找。

于 2013-11-01T05:41:58.773 回答
4

我要么创建一个额外的readonly字段，要么抛出NotSupportedException. 在我看来，另一种选择是没有意义的。让我们看看为什么。

不同（固定）哈希码

提供不同的哈希码很容易，例如：

class Sample
{
    private static int counter;
    private readonly int hashCode;

    public Sample() { this.hashCode = counter++; }

    public override int GetHashCode()
    {
        return this.hashCode;
    }

    public override bool Equals(object other)
    {
        return object.ReferenceEquals(this, other);
    }
}

从技术上讲，您必须注意创建太多对象并溢出counter此处，但实际上我认为这对任何人都不会成为问题。

这种方法的问题是实例永远不会比较相等。但是，如果您只想将 的实例Sample用作其他类型的集合的索引，那完全没问题。

常量哈希码

如果在任何情况下不同的实例应该比较相等，那么乍一看你别无选择，只能返回一个常量。但这会让你在哪里？

在容器内定位实例总是会退化为线性搜索的等价物。因此，实际上通过返回一个常量，您允许用户为您的类创建一个键控容器，但该容器将展示LinkedList<T>. 这对于熟悉您的班级的人来说可能很明显，但我个人认为这是让人们在脚下开枪。如果您事先知道 aDictionary不会像预期的那样运行，那么为什么要让用户创建一个呢？在我看来，最好扔NotSupportedException.

但是投掷是绝对不能做的！

有些人会不同意上面的说法，当那些人比自己聪明时，就应该注意了。首先，这个代码分析警告声明不GetHashCode应该抛出。这是需要考虑的事情，但我们不要教条。有时您必须出于某种原因违反规则。

然而，这还不是全部。Eric Lippert在他关于这个主题的博文中说，如果你从里面扔，GetHashCode那么

由于性能原因，您的对象不能成为许多在内部使用哈希表的 LINQ-to-objects 查询的结果。

失去 LINQ 无疑是一件很糟糕的事情，但幸运的是，这条路并没有就此结束。许多（全部？）使用哈希表的 LINQ 方法具有接受IEqualityComparer<T>在哈希时使用的重载。所以你实际上可以使用 LINQ，但它会不太方便。

最后，您将不得不自己权衡选项。IEqualityComparer<T>我的观点是，只要在技术上可行，最好使用白名单策略（在需要时提供），因为这使代码明确：如果有人试图天真地使用该类，他们会得到一个有助于告诉他们发生了什么的异常on 并且相等比较器在任何使用它的代码中都是可见的，从而使类的异常行为立即清晰。

于 2013-10-31T15:45:35.210 回答
1

在我想覆盖的地方Equals，但对象没有明智的不可变“键”（无论出于何种原因，使整个对象不可变是没有意义的），在我看来只有一个“正确”的选择：

  • 实施GetHashCode以散列与使用相同的字段Equals。（这可能是所有字段。）
  • 记录这些字段在字典中时不得更改。
  • 相信用户要么不将这些对象放入字典中，要么遵守第二条规则。

（返回一个常数值会影响字典性能。抛出异常会禁止太多有用的情况，即对象被缓存但未修改。任何其他实现GetHashCode都是错误的。）

无论如何，这会给用户带来麻烦，这可能是他们的错。（特别是：在不应该使用字典的地方使用字典，或者在应该使用使用引用相等的视图模型类型的上下文中使用模型类型。）

或者，也许我一开始就不应该压倒一切Equals。

于 2019-04-05T05:43:08.233 回答
0

如果这些类确实不包含可以计算哈希值的常量，那么我会使用比 GUID 更简单的东西。只需使用类（或包装类）中持久的随机数。

于 2013-10-31T15:13:00.370 回答
0

一个简单的方法是将 hashCode 存储在一个私有成员中，并在第一次使用时生成它。如果您的实体不经常更改，并且您不会使用两个不同的 Equal 对象（您的 Equals 方法返回 true）作为字典中的键，那么这应该没问题：

private int? _hashCode;

public override int GetHashCode() {
   if (!_hashCode.HasValue)
      _hashCode = Property1.GetHashCode() ^ Property2.GetHashCode() etc... based on whatever you use in your equals method
   return _hashCode.Value;
}

但是，如果您有对象 a 和对象 b，其中 a.Equals(b) == true，并且您使用 a 作为键（dictionary[a] = value）将条目存储在字典中。
如果 a 没有改变，则 dictionary[b] 将返回值，但是，如果您在将条目存储到字典后更改 a，则 dictionary[b] 很可能会失败。唯一的解决方法是在任何键更改时重新散列字典。

于 2013-10-31T15:23:29.803 回答