原则7：明白 GetHashCode() 的陷阱

By D.S.Qiu

尊重他人的劳动，支持原创，转载请注明出处：http://dsqiu.iteye.com

这是这本书介绍的唯一一个原则专门讲一个你应该尽量避免的函数。 GetHashCode() 只用在一个地方：定义基于哈希 key 集合，典型地， HashSet<T> 或者 Dictionary<K,V> 容器。值得称赞的是很多问题会随着实现基类的 GetHashCode() 而解决。对于引用类型，是能起作用但是低效。对于值类型，基类版本的总是不正确的。所以这很糟糕。写一个既高效又正确的 GetHashCode() 是完全可能的。没有哪个函数会像 GetHashCode() 一样产生这么多讨论和困惑。看完下面的消除所有困惑。

如果你定义的类型没有被用作容器的 key 这就没关系了。Window 控件 Web page 控件，或数据库连接很少被用作容器的 key 。在这些例子中，你什么也不用做。所有引用类型的哈希码是正确的，即使这不是低效的。值类型应该是不可变的（immutable），才是正确的，尽管同样地不高效。你创建的大多数类，最好避免 GetHashCode() 的存在。

如果有一天，你创建的类要被用作哈希 key ，你就需要实现 GetHashCode() ，所以继续看下面的。基于哈希码的容器可以优化查找。每个对象产出的整数被称为哈希码。对象根据哈希码以桶的形式存储。为了查找某个对象，你请求哈希码而只是在那个桶里查找。在 .NET 中，每个对象都有一个产生自 System.Object.GetHashCode() 的哈希码。任何重写 GetHashCode() 必须遵循下面三个条件：

1.如果两个对象相等（被操作符 == 定义），你产生相同的哈希值。否则哈希码不能用来查找容器中的对象。

2.对任何对象 A ， A.GetHashCode() 必须是一个实例不变量。无论什么方法调用 A.GetHashCode() 必须返回相同的值。这保证了一个物体总是存储在正确的桶中。

3.哈希函数应该针对所有输入情况产生一个整数随机分布。这就是为什么基于哈希容器高效。

写一个正确且有效的哈希函数需要掌握大量类的知识来保证遵循以上3条规则。 System.Object 和 System.ValueType 定义的版本不具备这个优势。这两个版本是在对你定义的类不知情的情况下提供的默认行为。 Object.GetHashCode() 使用 System.Object 内部域来产生哈希值。每个对象产生的哈希值要保证唯一，而且存储为整数。这些 key 从1开始而且每创建一个对象就递增。对象ID域在 System.Object 构造器中设置，而且不会被后面改动。 Object.GetHashCode() 返回对象的哈希值。

基于上面三条规则逐一检查 Object.GetHashCode() 。如果两个对象是相等的， Object.GetHashCode() 返回相同的哈希值，除非你重写操作符 == 。System.Object 的操作符 ==() 测试两个对象的ID。 GetHashCode() 返回对象的内部ID域。它就是这样获得的。如果你重写了自己版本的操作符 == ，你必须同时重写 GetHashCode() 保证符合第一条规则。有关相等的细节查看原则6。

第二条规则是这样的：对象呗创建之后，它的哈希值不会被改变。

第三条规则，对于所有输入情况应该产生一个所有正式的随机分布，而不持有。一个数字序列不是所有整数的随机分布除非你创建了很大数量的对象。通过 Object.GetHashCode() 产生的哈希码都集中在小范围的整数段。

这意味着 Object.GetHashCode() 是正确但不高效。如果你定义基于哈希表的引用类型，System.Object 的默认行为是正确的但慢。如果你创建一个被用做哈希 key 的类，你应该重写 GetHashCode() ，让你的类型有一个更好的哈希值分布。

在介绍如果重写 GetHashCode 之前，这部分讨论 ValueType.GetHashCode() 遵循的上面三个规则。 System.ValueType 重写了 GetHashCode() ，提供了所有值类型的默认行为。这个版本的哈希码从类型的第一个域返回。考虑下面的例子：

public struct MyStruct 
{
    private string msg; 
    private int id; 
    private DateTime epoch;
}

MyStruct 对象的哈希码产生自 msg 域。假设 msg 不为 null ，下面这段代码总是返回 true ：

 MyStruct s = new MyStruct();
s.SetMessage("Hello"); 
return s.GetHashCode() == s.GetMessage().GetHashCode();

第一个规则说的是两个对象相等（操作符 ==() 定义的）必须有相同的哈希码。大多数情况下，这条规则是被值类型遵循的，但是也可以打破它，就跟引用类型一样。 ValueType.operator==() 比较 struct 的第一个域，以及其他域。如果要遵从第一条规则，只要重写 operator== 使用第一个域，就能正确工作。任何 struct 的第一个域不过不参与类型的相等比较就违反此规则，打破了 GetHashCode() 。

第二条规则规定哈希码必须是实例不变量。只有 struct 的第一个域是不可变的菜遵循这个规则。如果第一个域的值会变，那么哈希值也会改变。那就打破了这条规则。是的， GetHashCode 是任何第一个域在生命期被改变的 struct 破坏了。这就是另外一个原因不可变值类型是你最好的考虑。

第三条规则依赖于类型第一个类的使用。如果第一个域产生一个整数随机分布，而且第一个域也是分布在 struct 的所有值，然而 struct 产生一个均匀分布。然而，如果第一个域有相同的值，这个规则会被违反。小改动之前的 struct ：

public struct MyStruct

{

private DateTime epoch;

private string msg;

private int id;

}

epoch 域被设置为当前日期（不包括时间），所有产生于同一日期的 MyStruct 对象都具体相同的哈希码。这就不能形成均匀的哈希码分布了。

总结下默认行为，Object.GetHashCode() 对于引用类型能正确工作，即使没有产生有效的分布。（如果你重写了 Object.operator==() ，你会破坏 GetHashCode() 。 ValueType.GetHashCode() 只有在 struct 的第一个域是只读的才能正确工作。 ValueType.GetHashCode() 产生一个高效的哈希码只有 struct 的第一个域是一个有意义的子集。

如果你想要构建一个更好的哈希码，你需要对你的类型做些约束。理想情况下，你应该创建一个不可变值类型。不可变值类型的 GetHashCode() 的规则会比不做约束类型更简单。现在自己构建一个 GetHashCode() 的实现，并对三条规则进行检查。

首先，如果两个对象相等， operator==() 定义的，它们必须返回相同的哈希值。任何用于产生哈希码的属性或数据都必须在相等判断中同样被考虑。明显，这意味着属性在相等判断和哈希值产生中都被用到。在相等判断用到的属性可能在哈希码计算中没有用到。 System.ValueType 的默认行为就是那样做的，这经常意味着规则3会被违反。相同的数据元素应该被用在两者的计算中。

第二条规则是 GetHashCode() 的返回值必须是实例不变量。想象你定义的一个引用类型， Customer ：

 public class Customer 
{
    private string name; 
    private decimal revenue;
    public Customer(string name) 
    {
        this.name = name; 
    }
    public string Name 
    {
        get { return name; } 
        set { name = value; }
    }
    public override int GetHashCode() 
    {
        return name.GetHashCode(); 
    }
}

执行下面代码：

Customer c1 = new Customer("Acme Products"); 
myHashMap.Add(c1, orders); 
// Oops, the name is wrong: 
c1.Name = "Acme Software";

c1 有时在 HashMap 中会丢失。当你往 map 加入 c1 ，哈希码产生自字符串“Acme Products”。当你改变 Customer 的 name 为 “Acme Software”。哈希码改变了。哈希码产生自新 name : “Acme Software”。 c1 存储在定义为 “Acme Products”的桶中，但是它应该是在“Acme Software”中。你就丢失了 Customer 在你自己的集合中。丢失是因为哈希码不是对象的不变量。你在存储对象后改变了正确的桶。

前面情况只有 Customer 是引用类型才会发生。值类型表现不同，但同样会出现问题。如果 Customer 是值类型， HashMap 存储的是 c1 的复制。最后一行改变 name 的值，并不会对 HashMap 存储有任何影响。因为封箱和拆箱和复制一样，在加入集合之后，你不能改变值类型成员的值。

唯一能解决规则2的方法是使用对象的一个或多个不可变属性定义哈希函数。 System.Object 使用不会改变的对象ID来恪守这条规则。 System.ValueType 希望你的类型的第一个域是不会改变的。你不能比让你的变量不可变做的更好了。当你打算将值类型用作哈希集合的 key ，它必须是不可变类型。如果你违反了这条建议，将会破坏哈希表。回顾 Customer 类，你可以更改 name 为不可变。高亮表示 Customer 的改变：

public class Customer 
{
    private string name; 
    private decimal revenue;
    public Customer(string name) 
    {
        this.name = name; 
    }
    public string Name 
    {
        get { return name; }
        // Name is readonly 
    }
    public decimal Revenue 
    {
        get { return revenue; } 
        set { revenue = value; }
    }
    public override int GetHashCode() 
    {
        return name.GetHashCode(); 
    }
    public Customer ChangeName(string newName)
    {
        return new Customer(newName) { Revenue = revenue };
    } 
}

ChangeName 创建一个新的 Customer 对象，使用构造器和对象初始化语法设置当前 revenue。 name 不可变改变修改 Customer 对象 name 的方式：

Customer c1 = new Customer("Acme Products"); 
myDictionary.Add(c1, orders); 
// Oops, the name is wrong: 
Customer c2 = c1.ChangeName("Acme Software"); 
Order o = myDictionary[c1];
myDictionary.Remove(c1); 
myDictionary.Add(c2, o);

你不得不移除原来的 Customer，改变 name ，然后把新的 Customer 对象加入到 Dictionary 中。这看起来比第一个版本更繁琐，但是这个能正确工作。前一个版本运行程序员写不正确的代码。随着强制用于计算哈希值的属性为不可变，增强了代码的正确性。使用你的类型不会出错。是的，这个版本更好的工作。你要强迫开发者写更多的代码，因为这是正确代码的唯一的方法。确保计算哈希值的数据成员要不可变。

第三条规则说的是 GetHashCode() 应该产生所有输入情况的随机分布。满足这个需求特定依赖你创建的类型。如果魔术公式存在，它会被实现在 System.Object ，而且这个原则也不会存在。一个常用而且成功的算法是使用对所有域使用 XOR 返回 GetHashCode() 的值。如果你的类型包含了一些不可变域，使用它们来计算。

GetHashCode() 有一个非常特别的需求：相等的对象必须产生相等的哈希码，而且这些哈希值必须是实例不可变的而且产生一个均匀分布会更有高效。只有不可变类型，三条才会满足。对于其他类型，依靠默认行为，但是明白这里面的陷阱。

小结：

这篇的内容是我们最简单了，好像也没有我们什么事情，只要记住最后一句话： 对于其他类型，依靠默认行为，但是明白这里面的陷阱。本来不想写的，听了某人的鼓励，还是决定坚持，虽然写到了凌晨3点，但还是完成了。所以有时候坚持只是需要一个理由，虽然不太会受这个影响，但是还是会给自己一个心理暗示。

天亮了，还要上班，还要帮国外的帮，也就不能睡觉了，加油，我可以的！

欢迎各种不爽，各种喷，写这个纯属个人爱好，秉持”分享“之德！

有关本书的其他章节翻译请点击查看，转载请注明出处，尊重原创！

如果您对D.S.Qiu有任何建议或意见可以在文章后面评论，或者发邮件（[email protected])交流，您的鼓励和支持是我前进的动力，希望能有更多更好的分享。

转载请在文首注明出处：http://dsqiu.iteye.com/blog/1981202

更多精彩请关注D.S.Qiu的博客和微博（ID：静水逐风）