c# - 为什么 C# 不为集合实现 GetHashCode？

Question

我正在将一些东西从 Java 移植到 C#。在 Javahashcode中 aArrayList取决于其中的项目。在 C# 中，我总是从List...

为什么是这样？

对于我的一些对象，哈希码需要不同，因为它们的列表属性中的对象使对象不相等。我希望哈希码对于对象的状态始终是唯一的，并且仅在对象相等时才等于另一个哈希码。我错了吗？

score 19 · Accepted Answer

为了正常工作，哈希码必须是不可变的——对象的哈希码永远不能改变。

如果对象的哈希码确实发生了变化，则包含该对象的任何字典都将停止工作。

由于集合不是不可变的，它们无法实现GetHashCode.
相反，它们继承了 default GetHashCode，它为对象的每个实例返回一个（希望是）唯一值。（通常基于内存地址）

score 10 · Accepted Answer

哈希码必须取决于所使用的相等性的定义，以便 if A == Bthen A.GetHashCode() == B.GetHashCode()（但不一定是相反的；A.GetHashCode() == B.GetHashCode()不包含A == B）。

默认情况下，值类型的相等定义基于它的值，引用类型的相等定义基于它的标识（也就是说，默认情况下，引用类型的实例只等于它自己），因此默认哈希码为值类型依赖于它包含的字段的值*，而对于引用类型，它依赖于标识。实际上，由于我们理想情况下希望不相等对象的哈希码不同，特别是在低位（最有可能影响重新散列的值），我们通常希望两个相等但不相等的对象具有不同哈希。

由于一个对象将保持与自身相等，因此还应该清楚的是GetHashCode()，即使对象发生了变异（即使对于可变对象，身份也不会发生变异），这个默认实现将继续具有相同的值。

现在，在某些情况下，引用类型（或值类型）重新定义了相等性。一个例子是字符串，例如"ABC" == "AB" + "C". 尽管有两个不同的字符串比较实例，但它们被认为是相等的。在这种情况下GetHashCode()必须被覆盖，以便该值与定义相等性的状态相关（在这种情况下，包含的字符序列）。

虽然对同样不可变的类型执行此操作更为常见，但由于各种原因，GetHashCode()它并不依赖于 immutability。相反，GetHashCode()必须在面对可变性时保持一致 - 更改我们在确定散列时使用的值，并且散列必须相应地改变。但是请注意，如果我们使用这个可变对象作为使用哈希的结构的键，这是一个问题，因为改变对象会改变它应该存储的位置，而不会将它移动到那个位置（这也是正确的集合中对象的位置取决于其值的任何其他情况 - 例如，如果我们对列表进行排序，然后改变列表中的一项，则列表不再排序）。然而，这并不意味着我们必须只在字典和哈希集中使用不可变对象。相反，这意味着我们不能对处于这种结构中的对象进行变异，而使其不可变是保证这一点的明确方法。

事实上，在很多情况下，在这种结构中存储可变对象是可取的，只要我们在这段时间内不改变它们，就可以了。由于我们没有不变性带来的保证，因此我们希望以另一种方式提供它（例如，在集合中花费很短的时间并且只能从一个线程访问）。

因此，键值的不变性是可能的情况之一，但通常是一个想法。但是，对于定义哈希码算法的人来说，他们不能假设任何这种情况总是一个坏主意（他们甚至不知道在对象存储在这种结构中时发生了突变）；由他们实现在对象的当前状态上定义的哈希码，无论在给定点调用它是否好。因此，例如，不应该在可变对象上记忆哈希码，除非在每次变异时清除记忆。（无论如何，记忆哈希通常是一种浪费，因为重复命中相同对象哈希码的结构将拥有自己的记忆）。

现在，在手头的情况下，ArrayList 在基于身份的默认相等情况下运行，例如：

ArrayList a = new ArrayList();
ArrayList b = new ArrayList();
for(int i = 0; i != 10; ++i)
{
  a.Add(i);
  b.Add(i);
}
return a == b;//returns false

现在，这实际上是一件好事。为什么？好吧，你怎么知道我们要考虑 a 等于 b？我们可能会，但在其他情况下也有很多充分的理由不这样做。

更重要的是，将平等从基于身份重新定义为基于价值，比从基于价值重新定义为基于身份要容易得多。最后，对于许多对象，有不止一个基于值的相等定义（经典案例是关于什么使字符串相等的不同观点），因此甚至没有一个唯一有效的定义。例如：

ArrayList c = new ArrayList();
for(short i = 0; i != 10; ++i)
{
  c.Add(i);
}

如果我们a == b在上面考虑，我们是否也应该考虑a == c？答案取决于我们在使用的平等定义中关心的内容，因此框架无法知道所有情况的正确答案是什么，因为所有情况都不同意。

现在，如果我们确实关心给定情况下基于价值的平等，我们有两个非常简单的选择。第一个是继承和覆盖平等：

public class ValueEqualList : ArrayList, IEquatable<ValueEqualList>
{
  /*.. most methods left out ..*/
  public Equals(ValueEqualList other)//optional but a good idea almost always when we redefine equality
  {
    if(other == null)
      return false;
    if(ReferenceEquals(this, other))//identity still entails equality, so this is a good shortcut
      return true;
    if(Count != other.Count)
      return false;
    for(int i = 0; i != Count; ++i)
      if(this[i] != other[i])
        return false;
    return true;
  }
  public override bool Equals(object other)
  {
    return Equals(other as ValueEqualList);
  }
  public override int GetHashCode()
  {
    int res = 0x2D2816FE;
    foreach(var item in this)
    {
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
  }
}

这假设我们总是希望以这种方式处理此类列表。我们还可以为给定的情况实现 IEqualityComparer：

public class ArrayListEqComp : IEqualityComparer<ArrayList>
{//we might also implement the non-generic IEqualityComparer, omitted for brevity
  public bool Equals(ArrayList x, ArrayList y)
  {
    if(ReferenceEquals(x, y))
      return true;
    if(x == null || y == null || x.Count != y.Count)
      return false;
    for(int i = 0; i != x.Count; ++i)
      if(x[i] != y[i])
        return false;
    return true;
  }
  public int GetHashCode(ArrayList obj)
  {
    int res = 0x2D2816FE;
    foreach(var item in obj)
    {
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
  }
}

总之：

引用类型的默认相等定义仅依赖于标识。
大多数时候，我们想要那个。
当定义类的人决定这不是我们想要的，他们可以覆盖这个行为。
当使用该类的人再次想要一个不同的相等定义时，他们可以使用IEqualityComparer<T>他们IEqualityComparer的字典、哈希映射、哈希集等使用他们的相等概念。
当对象是基于哈希的结构的关键时，对它进行变异是灾难性的。可以使用不变性来确保不会发生这种情况，但这不是强制性的，也不是总是可取的。

总而言之，该框架为我们提供了不错的默认值和详细的覆盖可能性。

*在结构中使用小数的情况下存在一个错误，因为在某些情况下，结构安全时会使用快捷方式而不是其他情况，但包含小数的结构是短时的一种情况cut 不安全，它被错误地识别为安全的情况。

score 8 · Accepted Answer

是的，你错了。在 Java 和 C# 中，相等意味着具有相同的哈希码，但反之亦然（不一定）正确。

有关详细信息，请参阅GetHashCode。

score 3 · Accepted Answer

哈希码不可能在大多数重要类的所有变体中都是唯一的。在 C# 中，List 相等的概念与 Java 中的不同（参见此处），因此哈希码实现也不相同 - 它反映了 C# List 相等。

score 2 · Accepted Answer

你只是错了一部分。当您认为相等的哈希码意味着相等的对象时，您肯定是错误的，但是相等的对象必须具有相等的哈希码，这意味着如果哈希码不同，那么对象也会不同。

score 2 · Accepted Answer

核心原因是性能和人性——人们倾向于将哈希视为快速的东西，但它通常需要至少遍历对象的所有元素一次。

示例：如果您使用字符串作为哈希表中的键，则每个查询的复杂度都为 O(|s|) - 使用 2 倍长的字符串，这将花费您至少两倍的成本。想象一下它是一棵成熟的树（只是列表的列表） - 哎呀 :-)

如果完整的深度哈希计算是对集合的标准操作，那么很大一部分程序员会在不知情的情况下使用它，然后指责框架和虚拟机运行缓慢。对于像完全遍历这样昂贵的东西，程序员必须意识到复杂性是至关重要的。实现这一目标的唯一方法是确保您必须自己编写。这也是一个很好的威慑力:-)

另一个原因是更新战术。即时计算和更新哈希与每次都进行完整计算需要根据手头的具体情况进行判断调用。

不变性只是一种学术上的逃避——人们使用哈希作为一种更快检测变化的方式（例如文件哈希），并且还使用哈希来处理一直在变化的复杂结构。除了 101 基础知识之外，哈希还有更多用途。 关键再次是，对于复杂对象的哈希使用什么必须是根据具体情况进行判断。

使用对象的地址（实际上是一个句柄，因此在 GC 后它不会改变）作为哈希实际上是哈希值对于任意可变对象保持相同的情况 :-) C# 这样做的原因是它很便宜并且再次轻推人们自己计算。

score -1 · Accepted Answer

为什么太哲学了。创建辅助方法（可能是扩展方法）并根据需要计算哈希码。可能是 XOR 元素的哈希码

c# - 为什么 C# 不为集合实现 GetHashCode？

7 回答 7

Related

Reference