辅导:C语言基础理解GetHashCode()的缺陷
来源:优易学  2011-10-13 10:45:41   【优易学:中国教育考试门户网】   资料下载   IT书店

  致力于一个应该避免编写的方法。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()的实现的上下文中来检测。

[1] [2] 下一页

责任编辑:小草

文章搜索:
 相关文章
热点资讯
资讯快报
热门课程培训