原 GetHashCode重写指南（译文）

"法典只是指南，而不是规定。" --本人对此深表赞同。在编写代码时, 应当能够正确区分哪些是易于出问题的错误代码，哪些是可以模糊处理的代码，前者需要谨慎处理，以保持代码的正确性和鲁棒性，后者则可以灵活变化。我经常遇到重写GetHashCode需要注意事项的问题，因而，我在这里总结一下：

GetHashCode的作用

设计仅用于在一个hash表中放置，索引一个对象。

为什么对象需要这样的一个方法

在类型系统中的每个对象都应该提供一个 GetType 的方法, 这是完全合理的。数据自描述能力是 CLR 类型系统的一个关键特性。而且, 每个对象都应该有一个 ToString, 以便它能够打印出一个字符串的表示形式, 以便进行调试。这也是合理的, 对象应该能够比较自己与其他对象的平等（equal）。但是, 为什么每个对象都要求能在哈希表中插入自己的哈希值呢？要求每一个对象能够做到似乎是一个奇怪的事情。

我认为, 如果我们今天从头开始重新设计类型系统, 哈希可能会以不同的方式进行, 也许会有一个 IHashable 的接口。但是, 当 CLR 类型系统设计时, 没有泛型类型, 因此需要能够存储任何对象的通用哈希表。

哈希表及某些数据结构如何使用 GetHashCode？

假定一个数据类型“set”。在一个集合中可能需要执行许多操作, 但两个基本的运算是在集合中插入一个新项, 并检查给定项是否在 set 中。我们希望这些操作能够快速进行, 即使该集合很大。例如, 使用一个list实现一个set：

class Set<T>
{
  private List<T> list = new List<T>();

  public void Insert(T item)
  {
    if (!Contains(t)) 
      list.Add(item);
  }

  public bool Contains(T item)
  {
    foreach(T member in list)
      if (member.Equals(item)) 
        return true;
    return false;
  }
}

(我在本文中省略了任何错误检查; 我们可能希望确保该项不是空的。我们可能希望实现一些接口, 等等。我把事情简单化了, 这样我们就能专注于散列部分。）

这里的包含方法查询速度是线性增长的;如果列表中有1万项, 则必须查看所有1万项, 以确定该对象不在列表中。这并非优秀的实现方式。

优化方法是牺牲一点内存空间来换取更快的包含方法检查速度。具体是要制作许多更短的列表, 称为 "桶", 然后快速的查找到我们需要的桶，最后在桶里面查找需要的对象:

class Set<T>
{
  private List<T>[] buckets = new List<T>[100];

  public void Insert(T item)
  {
    int bucket = GetBucket(item.GetHashCode());
    if (Contains(item, bucket))
      return;
    if (buckets[bucket] == null)
      buckets[bucket] = new List<T>();
    buckets[bucket].Add(item);
  }

  public bool Contains(T item)
  {
    return Contains(item, GetBucket(item.GetHashCode());
  }

  private int GetBucket(int hashcode)
  {
    unchecked
    {
      // A hash code can be negative, and thus its remainder can be negative also.
      // Do the math in unsigned ints to be sure we stay positive.
      return (int)((uint)hashcode % (uint)buckets.Length);
    }
  }

  private bool Contains(T item, int bucket)
  {
    if (buckets[bucket] != null)
      foreach(T member in buckets[bucket])
        if (member.Equals(item))
          return true;
    return false;
  }
}

假如set中有10000个成员，然后我们在100个桶里面查，每个桶平均有100个；那么包含方法的效率提升了100倍。

这个set还能够优化，参考List能够在内部数组满的情况下自动伸缩，set也也可实现成自动伸缩以确保较小的桶平均长度，此外设置质数个桶也是个更好的选择，对这个hash表还能做很多的改进，但是基本结构大致如此。

从这个例子中我们能够推断出GetHashCode的规则及指南。

• Rule: 相等的对象有相同的hash值

如果两个对象相等, 则它们必须具有相同的哈希代码;或者, 等价地, 如果两个对象有不同的哈希代码, 那么它们必须是不等的。

推断很简单，假定两个对象是相等但是hash值不同，如果第一个对象放在桶里可能被放进12号桶，如果接着在set中查询另一个不同hash的相等对象时，他可能回去搜索67号桶，那么就会找不到。

需要注意的是两个对象不一定有相同的hash值，假定有40亿个hash值，那么肯定会有超过40亿个对象，还会有远远超出40亿的字符串，因而参考个鸽笼原则则必然有两个不同的对象共享一个hash值

• Guideline:GetHashCod返回的整数应该永远相同

理想情况下, 可变对象的哈希代码应该只从不能改变的字段中计算, 因此对象的哈希值在其整个生存期内都是相同的。

然而，这只是个理想情况，实际上确是：

• Rule:当对象包含在依赖于哈希代码保持稳定的数据结构中时, GetHashCode 返回的整数决不能更改

使一个对象的hash值随着对象的字段变化而变化是可行的，但是其中有一定的风险，如果您有这样一个对象,并且将其放在哈希表中, 则需要一些协议来确保对象在哈希表中不会突变, 从而使对象和维护哈希表的代码保持一致。该协议需要按具体情况制定。

如果一个hash表中的对象的hash值改变了，很明显包含方法将不能正常工作，你把这个对象放到5号桶中，然后hash值突变，在使用contain方法判断对象是否存在时，它就到74号桶里查找，自然是找不到的。

对象可能会超出你预料的放进hash表中，许多linq操作内部都是使用的hash表，在linq操作中不要做危险的可能会导致hash值改变的操作。

• Rule:GetHashCode的消费者不能依赖于时间或者跨程序集操作

假设您有一个对象, 其中有一组字段, 如名称、地址等。如果在两个不同的进程中使两个这样的对象具有完全相同的数据, 则它们不必返回相同的哈希代码。如果您在星期二在一个进程中做了这样一个对象, 请将其关闭, 并在星期三再次运行该程序, 哈希代码可能会有所不同。

System.String.GetHashCode 的文档特别注明两个相同的字符串在 CLR 的不同版本中可以有不同的哈希代码, 实际上它们确实如此。不要将字符串哈希存储在数据库中, 并期望它们永远相同。事实上有人在这上面吃过亏。

• Rule: GetHashCode禁止抛出异常，必须要有返回值

获取哈希代码只计算一个整数;没有任何理由能让它失败。GetHashCode 的实现应该能够处理合法对象。

我偶尔也会回应“我想把我在GetHashCode中抛出notimplementedexception以确保对象从未投入一个哈希表；我不打算为这个对象会被放入一个哈希表。“类似于这种问题。好了，好了，但以前的指南中的最后一句话；这意味着你的对象不能在LINQ中使用，也不能享受由此带来的高性能。

因此它不会抛出一个异常, 所以必须最终返回一个值。将 GetHashCode 实现为无限循环或者抛出异常是不合合理的, 也不明智的。

在对可能递归定义并包含循环引用的对象进行哈希运算时, 这一点尤为重要。如果对象Alpha有个Beta属性，然而对象Beta中又hash了 Alpha成员，那么会永远循环下去 (如果当前架构能够优化尾部调用) 或耗尽堆栈和崩溃的进程。

• Guideline: GetHashCode 的实现必须非常快

hash的目的就是优化查询操作，如果调用GetHashCode消耗的时间比直接查询一万个成员更多，那么没有分毫意义。

我把它归类为 "指南" 而不是 "规则", 因为它是如此含糊。什么才叫慢？这由你来决定。

• Guideline: 哈希代码的分布必须是 "随机的"

"随机分布" 的意思是, 如果在被哈希的对象中有共性, 那么在产生的哈希代码中不应该有相似的共性。例如, 假设您正在散列一个表示某个点的纬度和经度的对象。一组这样的地点很可能是集群位置;奇数总是更好些， 比如说, 大部分是同一个城市的房屋, 或者是同一个油田的阀门, 或者其他的。如果相近数据产生相近哈希值, 那么可能会减少所使用的桶数, 并在桶变得非常大时导致性能问题。

我把这个列为指南而非规则是因为没有具体的标准，并非因为不重要，分布性非常重要，但是当好的分布和执行效率对立的时候，更重要的是要在在两者间取得平衡。

我从深刻的个人的经历中明白了这一点。十多年前, 我为 msn.com 后端服务器使用的表编写了一个字符串哈希算法。我认为这是一个合理的随机分布的算法, 但我犯了一个错误, 它不是。结果是, 所有10万由五个字符, 并且只包含数字的字符串, 总是被哈希到600个桶中的其中5个。msn.com 的人使用我的表试图快速查找数以万计的美国邮政编码, 所有这些代码都是五位数的字符串。在同一个代码中的线程 bug 之间, 我破坏了 msn.com 上一个重要页面的性能;这既费钱又尴尬。数据有时是大量相似的, 一个好的哈希算法将考虑到这一点。

特别要小心“异或”。这是很常见的散列码的结合一起异或他们，但这未必是一件好事。假设您有一个数据结构，其中包含发送地址和家庭地址的字符串。即使在单个字符串的哈希算法是非常好的，如果存在大量两个字符串相同的对象，这些对象的。当数据结构存在冗余时，异或可以产生或加剧分发问题。

Security issue:如果你的hash数据是根据外部数据产生，那可能会有安全问题

当我的算法出现问题时，幸运的是msn.com上的那个页面交互的数据少，但是假定那个页面是从用户那里收集数据，然后存在hash表中用于服务端分析，如果用户怀有敌意, 并且故意制造大量的数据, 总是对同一桶进行哈希运算, 那么他们就可以通过使服务器浪费大量时间查看不平衡的哈希表来对服务器发起拒绝服务攻击。如果面临这种情况, 请教一位专家来可能建立 GetHashCode 的恶意数据抵抗的实现, 这样做的正确和安全正是一个专家在该领域的工作（意思是靠自己难度很大）。

Security issue:不要把GetHashCode用于其他用途

GetHashCode设计仅用于平衡hash表，不用用作其他用途，特别是：

• 没有给对象提供唯一键，碰撞几率非常高。
• 没有进行高度加密，因而不能用于签名或者密码的一部分
• 它不一定有校验的检错性能。

正确地处理所有这些事情是非常棘手的。

原文链接：https://blogs.msdn.microsoft.com/ericlippert/2011/02/28/guidelines-and-rules-for-gethashcode/