为什么C#没有为集合实现GetHashCode？

Question

我正在将一些东西从Java移植到C#.在Java中hashcode,a ArrayList取决于其中的项目.在C#中,我总是从List... 获得相同的哈希码

为什么是这样？

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

Answer 1

为了正常工作,哈希码必须是不可变的 - 对象的哈希码必须永远不会改变.

如果对象的哈希码确实发生了变化,那么包含该对象的任何词典都将停止工作.

由于集合不是不可变的,因此无法实现GetHashCode.
相反,它们继承默认值GetHashCode,它为对象的每个实例返回(希望)唯一值.(通常基于内存地址)

Answer 2

是的,你错了.在Java和C#中,相等意味着具有相同的哈希码,但反过来并不(必然)为真.

有关更多信息,请参阅GetHashCode.

Answer 3

Hashcodes必须依赖于所使用的相等的定义,以便在A == B那时A.GetHashCode() == B.GetHashCode()(但不一定是反向; A.GetHashCode() == B.GetHashCode()不需要A == B).

默认情况下,值类型的等式定义基于其值,而引用类型的等式定义基于其标识(即,默认情况下,引用类型的实例仅等于其自身),因此默认的哈希码为值类型是这样的,它取决于它包含的字段的值*,对于引用类型,它取决于标识.实际上,因为我们理想地希望非等对象的哈希码特别是在低阶位(最有可能影响重新散列的值)中不同,我们通常希望两个等价但不相等的对象具有不同的哈希值.

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

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

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

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

因此,关键值的不变性是可能的事情之一,但通常是一个想法.但是,对于定义哈希码算法的人来说,并不是他们认为任何这样的情况总是一个坏主意(他们甚至不知道在对象存储在这样的结构中时发生了变异); 它们是为了实现在对象的当前状态上定义的哈希码,无论是否在给定点调用它都是好的.因此,例如,除非在每个mutate上清除memoisation,否则不应在可变对象上记忆哈希码.(无论如何,记忆哈希通常都是浪费,因为反复敲击相同对象哈希码的结构会有自己的备忘录).

现在,在手头的情况下,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;
  }
}

综上所述:

1. 引用类型的默认相等定义仅取决于标识.
2. 大多数时候,我们都想要那样.
3. 当定义类的人决定这不是想要的时,他们可以覆盖这种行为.
4. 当使用该类的人再次想要不同的相等定义时,他们可以使用IEqualityComparer<T>,IEqualityComparer因此他们的字典,哈希映射,哈希集等使用它们的相等概念.
5. 改变对象是一个灾难性的,而它是基于散列的结构的关键.可以使用不变性来确保不会发生这种情况,但不是强制性的,也不总是可取的.

总而言之,该框架为我们提供了很好的默认值和详细的覆盖可能性.

*在结构中有一个小数的情况下有一个错误,因为在某些情况下使用快捷方式时它是安全的而不是其他的,但是当包含小数的结构是短时间的一个结构时切割是不安全的,它被错误地识别为安全的情况.