|
C语言基础 理解GetHashCode()的缺陷 |
|
|
|
www.nanhushi.com 佚名 不详 |
|
致力于一个应该避免编写的方法。GetHashCode()仅仅用在一个地方：在基于hash(哈希)结构的集合中，用来定义key(键值)的hash值，典型的是Hashtable(哈希表)或者Dictionary(字典)容器。因为基类在对GetHashCode()的实现上存在很多问题，所以仅用在一个地方很好。对于引用类型，这也能工作但是效率低。对于值类型，基类的版本经常是不正确的，而且越来越糟。不写GetHashCode()是完全可能的，那样就会同时获得效率和正确性。没有哪个单独的方法比GetHashCode()带来更多的讨论和混乱。继续读来移除所有的困惑。
如果你正在定义一个从不会在容器里面用作key的类型，这没什么影响。表示WinForm控件、web页面控件或数据库连接的类型，不大可能被用作集合中的key。在那些情况下，什么也不要做。所有的引用类型将会有一个正确的hash码，即使是很低效的。值类型应该是不可变性的，这种情况下，默认的实现，尽管是效率低的，但是是可以工作的。在你创建的多数类型中，最好的途径就是完全避免GetHashCode()的存在。
Examda提示:创建一个要用作hashtable的key的类型，需要编写自己的GetHashCode()实现，那么继续读。基于hash结构的容器使用hash码来优化搜索。每个对象生成一个叫做hash码的整型值。对象都被存储在基于hash值的bucket(容器，桶？)里。为了搜索一个对象，你需要它的键值，在bucket容器里面搜索它。在.Net里面，每个对象都有一个由System.Object.GetHashCode()决定的hash码。任何对GetHashCode()的重载必须遵守这三个规则：
1.如果2个对象是相等的(由==操作符定义)它们必须生成同样的hash值。否则，hash值不能被用来在容器里面查找对象。
2.对于任何对象A，A.GetHashCode()必须是一个实例不变量。无论在A里面调用什么方法，A.GetHashCode()必须总是返回同样的值。这能保证，放在bucket容器里的对象永远在正确的bucket里。
3.Hash方法应该为所有的输入在整型范围内生成一个随机的分布。这就是使用基于hash结构的容器里面获得效率的原因。
编写一个正确且高效的hash方法要求对该类型有更多了解来保证遵守规则3。在System.Object和System.ValueType中定义的版本没有这优点。这些版本在几乎不知道你的特定类型的情况下，必须提供最好的默认行为。Object.GetHashCode()使用了System.Object类的一个内部字段来生成hash值。每个对象在它被创建的时候都被分配一个唯一的对象值(以一个整型值来存储)。这些值以1开始，每次有任何类型的一个新对象被创建时该值就会增加。对象标识符字段在System.Object构造器的内部被设置，以后不能再被修改。Object.GetHashCode()将对象标识符字段的hash值作为结果hash值返回。
现在根据那三条规则来检查Object.GetHashCode()。如果2个对象是相等的，除非你重写过了==操作符，Object.GetHashCode()会返回同样的hash值。System.Object的==版本检测对象标识符。GetHashCode()返回内部的对象标识符字段，这能工作。然而，如果你已经提供了自己版本的==，就必须也要提供自己版本的GetHashCode()才能确保遵守了第一条规则。Item 9详细介绍了相等性。
遵循了第二个规则：一个对象在被创建后，hash码从不改变。
第三个规则，对所有的输入要随机分布在整型范围内，这一条不成立。除非你创建大量的对象，否则一个数字队列不是整型范围内的随机分布，由Object.GetHashCode()生成的hash码集中在整型范围的低端部分。
这意味着Object.GetHashCode()是正确的但是非高效的。如果你创建一个基于你定义的引用类型的hashtable，继承自System.Object的默认行为就是可工作、比较慢的hashtable。当你创建一个准备作为hash键值的引用类型时，应该重写GetHashCode()，以便于为你的特定类型在整型范围内得到一个更好的hash值分布。
在讲述怎么编写自己重写版本的GetHashCode之前，这一节用那三条同样的规则来检查Value.GetHashCode()。System.ValueType重写了GetHashCode(),为所有的值类型提供了默认的行为。这个版本返回在该类型内部定义的首个字段的hash值作为自己的hash值。考虑这个例子：
public struct MyStruct
{
private String msg;
private Int32 id;
private DateTime epoch;
}
从MyStruct对象返回的hash码就是由msg字段生成的hash码。下面代码段总是返回true：
MyStruct s = new MyStruct();
return s.GetHashCode() == s.msg.GetHashCode();
翻译时,环境.Net2.0,试验：
总是返回false
第一个规则是说2个相等的对象(由==定义的相等)必须由相同的hash码。该规则对于值类型来说，在多数情况下是被遵守的。但是你可以打破它，就像对待引用类型一样。ValueType的操作符==()比较结构体中很多字段中的首个字段，这满足了规则1。只要你定义了任何重写的==操作符，就使用了首个字段，就能工作。任何结构体，如果它的首个字段没有参与类型的相等性，那么就违背了该规则，破坏了GetHashCode()。
第二个规则阐明了hash码必须是一个实例不变量。只有当这个结构体中的首个字段是不可变字段时，才符合该规则。如果首个字段的值可改变，那么hash码也可变，这就违背了该规则。是的，对于任何你创建的结构体，如果在它的生命期内首个字段是可以被修改的，那么GetHashCode()就会被打破。为什么不可变的值类型是你最好的选择呢，这也是另外一个原因(参看Item 17)。
第三个规则依赖于首个字段的类型和它如何被使用。如果首个字段生成了一个在整型范围的随机分布，而且它也遍布了结构中的所有值，那么，该结体构也能生成一个很好的平均分布。然而，如果首个字段经常有同样的值，这个规则也会被打破。考虑对前面的结构体做个小小的修改;
public struct MyStruct
{
private DateTime epoch;
private String msg;
private Int32 id;
}
如果epoch字段被设置成了当前的日期(不含时间)，所有在某个特定日期被创建的MyStruct对象将会有同样的hash值。这就阻止了所有hash值的平均分布。
概括Object.GetHashCode()的默认行为，在引用类型上工作得很正确，尽管它没必要生成一个高效的分布(如果你已经重写了Object.operator==()，会打破GetHashCode())。只有在结构体中的首个字段是只读的情况下，ValueType.GetHashCode()才能工作。只有当结构体满足下列条件的时候：包含了遍布于他的输入中某个有意义的集合的值，ValueType.GetHashCode()才能生成高效的hash码， 如果你正打算构建一个更好的hash码，需要在你的类型里面加入一些限制。重新检测这三个规则，这次是在构建一个可工作的对GetHashCode()的实现的上下文中来检测。
首先，如果2个对象是==操作符定义的相等的话，它们必须返回同样的hash值，任何被用来生成hash码的属性或者数据值必须参加该类型的相等性判断。显然，这意味着，被用作相等性的属性同时也被用作来生成hash码。有的属性参与相等性判断，但不被用来进行hash码计算，这也是可能的。System.ValueType的默认行为就是那样做的，但是这意味着规则3经常被违背，同样的数据元素应该同时参加2个计算。
第二条规则是，GetHashCode()返回的值必须是一个实不例变量。想象，你定义了一个引用类型Customer:
public class Customer
{
private String name;
private decimal revenue;
public Customer(string name)
{
name = name;
}
public String Name
{
get { return name; }
set { name = value; }
}
public override Int32 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（hash图）中的某个地方。当你把c1放到图中时，hash码由字符串“Acme Products”生成。在将客户的名字修改为“Acme Software”之后，hash码值发生了变化。现在它由新的名字“Acme Software”生成。C1存储在以“Acme Products”定义的bucket容器里面，但是它应该存储在以“Acme Software”定义的bucket容器里面。你已经将客户遗失在了自己的集合里面，因为hash码不是一个对象不变量。在存储完该对象之后，你已经修改了这个正确的bucket容器。
仅仅当Customer是一个引用类型时，前面的情况才会发生。值类型做了不同的错误行为，但是它们也会引起问题。如果Customer是值类型，c1的一个拷贝就会被存储在hash图中。最后一行修改name值的代码对存储在hash图中的拷贝没有影响。因为装箱和拆箱都是进行拷贝的，所以，在一个值类型的对象被添加到一个集合中后，想修改它的成员是非常不可能的。
表达规则2的唯一方法就是定义hash码方法，让它返回一个基于一个或多个不变属性的值。System.Object通过使用不变的对象标识符遵守了该规则。System.ValueType希望你的类型的首个字段不会改变。除了使你的类型是个不可变的之外，没有更好的方法。当你定义一个准备在hash容器中作为key使用的值类型时，它必须是一个不可变的类型。若违背该建议，你的类型的用户将会找到一个打破将你的类型用作key的hashtable的方法。再看Customer类，你可以修改使用户名不可变：
public class Customer
{
private readonly String name;
private Decimal revenue;
public Customer(String name): this(name, 0)
{
}
public Customer(String name, Decimal revenue)
{
name = name;
revenue = revenue;
}
public String Name
{
get { return name; }
}
// Change the name, returning a new object:
public Customer ChangeName(String newName)
{
return new Customer(newName, revenue);
}
public override Int32 GetHashCode()
{
return name.GetHashCode();
}
}
使name不可变，将改变你的下述行为：你该如何处理客户对象来修改name：
Customer c1 = new Customer("Acme Products");
myHashMap.Add(c1, orders);
// Oops, the name is wrong:
Customer c2 = c1.ChangeName("Acme Software");
Order o = myHashMap[c1] as Order;
myHashMap.Remove(c1);
myHashMap.Add(c2, o);
你不得不移除原始的客户，修改name，将新的客户对象添加到hashtable中。它看起来比第一个版本更笨重，但能工作。前面的版本允许程序员编写不正确的代码。通过将被用来计算hash值的属性强制为不可变的，可以得到正确的行为，你的类型的用户不会出错了。是的，这个版本更能工作。你正在强迫开发者编写更多的代码，但是仅仅因为这是编写正确代码的唯一方式。请确认任何被用来计算hash值的数据成员是不可变的。
第三个规则是说GetHashCode()应该为所有的输入生成一个在整型范围内的随机分布。要满足这个要求依赖于你创建的类型的细节。如果存在一个魔法公式，就肯定早就在System.Object里面实现了，而这个条款也不会存在。一个通用并且成功的算法是：对类型里面的所有字段使用GetHashCode()后，对其返回值取XOR。如果你的类型包含一些可变的字段，在计算中排除它们。
GetHashCode()有非常特别的要求：相等的对象必须产生相等的hash码，hash码必须是对象不可变的，必须产生一个平均的分布以便获得效率。仅仅有不可变的值类型才能满足3个规则，对于其它类型，依赖于默认的行为，但是要理解它的缺陷。考试大论坛
|
|
|
|
| 文章录入：杜斌 责任编辑：杜斌 |
|
上一篇文章： C语言基础C#中的Boxing/Unboxing
下一篇文章： Visitor访问者模式（行为型模式） |
| 【字体：小 大】【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口】 |
| |
|
