C语言基础理解GetHashCode的缺陷

1、C语言基础 理解GetHashCodeO的缺陷致力于一个应该避免编写的方法。GetHashCodeO仅仅用在一个地方：在基 于 hash( 哈希 ) 结构的集合中，用来定义 key( 键值 ) 的 hash 值，典型的是 Hashtable( 哈希表 )或者 Dictionary( 字典) 容器。因为基类在对 GetHashCode() 的实现上存在很多问题， 所以仅用在一个地方很好。 对于引用类型， 这也能工作 但是效率低。对于值类型，基类的版本经常是不正确的，而且越来越糟。不写 GetHashCode()是完全可能的，那样就会同时获得效率和正确性。没有哪个单独 的方法比GetHashCod

2、e()带来更多的讨论和混乱。继续读来移除所有的困惑。如果你正在定义一个从不会在容器里面用作 key 的类型，这没什么影响。 表 示WinForm控件、web页面控件或数据库连接的类型，不大可能被用作集合中的 key。在那些情况下，什么也不要做。所有的引用类型将会有一个正确的hash码，即使是很低效的。值类型应该是不可变性的，这种情况下，默认的实现，尽 管是效率低的， 但是是可以工作的。 在你创建的多数类型中， 的途径就是完全避 免 GetHashCode()的存在。Examda提示：创建一个要用作hashtable的key的类型，需要编写自己的 GetHashCode()实现，那么继续读。基于

3、 hash结构的容器使用hash码来优化搜 索。每个对象生成一个叫做 hash 码的整型值。对象都被存储在基于 hash 值的 bucket( 容器，桶？ ) 里。为了搜索一个对象，你需要它的键值，在 bucket 容器 里面搜索它。在.Net里面，每个对象都有一个由System.Object.GetHashCode() 决定的hash码。任何对GetHashCode()的重载必须遵守这三个规则：1. 如果 2 个对象是相等的 ( 由=操作符定义 ) 它们必须生成同样的 hash 值。 否则， hash 值不能被用来在容器里面查找对象。2. 对于任何对象A, A.GetHashCode()必须

4、是一个实例不变量。无论在 A里 面调用什么方法，A.GetHashCode()必须总是返回同样的值。这能保证，放在 bucket 容器里的对象永远在正确的 bucket 里。3. Hash 方法应该为所有的输入在整型范围内生成一个随机的分布。这就是 使用基于 hash 结构的容器里面获得效率的原因。编写一个正确且高效的 hash 方法要求对该类型有更多了解来保证遵守规则3。在 System.Object 和 System.ValueType 中定义的版本没有这优点。 这些版本 在几乎不 知 道你的 特定类型 的情 况下， 必 须提 供 的 默认行 为。 Object.GetHashCode()

5、使用了 System.Object 类的一个内部字段来生成 hash值。 每个对象在它被创建的时候都被分配一个的对象值 (以一个整型值来存储 )。这些 值以 1 开始，每次有任何类型的一个新对象被创建时该值就会增加。 对象标识符 字 段 在 System.Object 构 造 器 的 内 部 被 设 置 ， 以 后 不 能 再 被 修 改 。 Object.GetHashCode() 将对象标识符字段的 hash 值作为结果 hash 值返回。现在根据那三条规则来检查 Object.GetHashCode() 。如果 2 个对象是相等 的，除非你重写过了 =操作符， Object.GetHas

6、hCode() 会返回同样的 hash 值。 System.Object的=版本检测对象标识符。GetHashCode()返回内部的对象标识 符字段，这能工作。然而，如果你已经提供了自己版本的=，就必须也要提供自己版本的GetHashCode()才能确保遵守了第一条规则。Item9详细介绍了相等性。遵循了第二个规则：一个对象在被创建后，hash码从不改变。第三个规则， 对所有的输入要随机分布在整型范围内， 这一条不成立。 除非 你创建大量的对象 ， 否则一 个数字队 列不是整型 范围内 的随机分布 ，由 Object.GetHashCode() 生成的 hash 码集中在整型范围的低端部分。这

7、意味着 Object.GetHashCode() 是正确的但是非高效的。如果你创建一个 基于你定义的引用类型的 hashtable ，继承自 System.Object 的默认行为就是可 工作、比较慢的 hashtable 。当你创建一个准备作为 hash 键值的引用类型时， 应该重写GetHashCode(),以便于为你的特定类型在整型范围内得到一个更好的 hash 值分布。在讲述怎么编写自己重写版本的GetHashCode之前，这一节用那三条同样的规则来检查 Value.GetHashCode() 。 System.ValueType 重写了 GetHashCode(), 为所有的值类型提

8、供了默认的行为。 这个版本返回在该类型内部定义的首个字段 的 hash 值作为自己的 hash 值。考虑这个例子：publicstructMyStructprivateStringmsg;privateInt32id;privateDateTimeepoch;从MyStruct对象返回的hash码就是由msg字段生成的hash码。下面代码 段总是返回 true ：MyStructs=newMyStruct(); returns.GetHashCode()=s.msg.GetHashCode();翻译时,环境.Net2.0,试验：总是返回 false第一个规则是说2个相等的对象(由=定义的相等)

9、必须由相同的hash码。 该规则对于值类型来说， 在多数情况下是被遵守的。 但是你可以打破它， 就像对 待引用类型一样。 ValueType 的操作符 =() 比较结构体中很多字段中的首个字段， 这满足了规则 1。只要你定义了任何重写的 =操作符，就使用了首个字段，就能 工作。任何结构体， 如果它的首个字段没有参与类型的相等性， 那么就违背了该 规则，破坏了 GetHashCode()。第二个规则阐明了 hash 码必须是一个实例不变量。只有当这个结构体中的 首个字段是不可变字段时， 才符合该规则。如果首个字段的值可改变， 那么 hash 码也可变，这就违背了该规则。是的，对于任何你创建的结构

10、体，如果在它的生 命期内首个字段是可以被修改的，那么GetHashCode()就会被打破。为什么不可变的值类型是你的选择呢，这也是另外一个原因(参看Item17)。第三个规则依赖于首个字段的类型和它如何被使用。 如果首个字段生成了一 个在整型范围的随机分布， 而且它也遍布了结构中的所有值， 那么，该结体构也 能生成一个很好的平均分布。 然而， 如果首个字段经常有同样的值， 这个规则也 会被打破。考虑对前面的结构体做个小小的修改 ;publicstructMyStructprivateDateTimeepoch;privateStringmsg; privateInt32id;如果epoch字段

11、被设置成了当前的日期(不含时间)，所有在某个特定日期被 创建的 MyStruct 对象将会有同样的 hash 值。这就阻止了所有 hash 值的平均分 布。概括 Object.GetHashCode() 的默认行为，在引用类型上工作得很正确，尽 管它没必要生成一个高效的分布 (如果你已经重写了 Object.operator=() ，会 打破 GetHashCode() 。 只有在结构体中的首个字段是只读的情况下， ValueType.GetHashCode() 才能工作。只有当结构体满足下列条件的时候：包含 了遍布于他的输入中某个有意义的集合的值， ValueType.GetHashCode

12、() 才能生 成高效的 hash 码，如果你正打算构建一个更好的 hash 码，需要在你的类型里面 加入一些限制。 重新检测这三个规则， 这次是在构建一个可工作的对 GetHashCode()的实现的上下文中来检测。首先，如果2个对象是=操作符定义的相等的话， 它们必须返回同样的 hash 值，任何被用来生成 hash 码的属性或者 数据值必须参加该类型的相等性判断。 显然， 这意味着， 被用作相等性的属性同 时也被用作来生成 hash 码。有的属性参与相等性判断，但不被用来进行 hash 码计算，这也是可能的。 System.ValueType 的默认行为就是那样做的，但是这意味着规则 3经

13、常被违背，同样的数据元素应该同时参加 2 个计算第二条规则是，GetHashCode()返回的值必须是一个实不例变量。想象，你 定义了一个引用类型 Customer:publicclassCustomerprivateStringname;privatedecimalrevenue;publicCustomer(stringname)name=name;publicStringNamegetreturnname;setname=value;publicoverrideInt32GetHashCode()returnname.GetHashCode();假设执行下面的代码段：Customerc1=newCustomer("AcmeProducts");myHashMap.Add(c1,orders);/Oops,thenameiswrong:c1.Name="AcmeSoftware"C1遗失在hashmap( has