我在 Essential C# 3.0 和 .NET 3.5 书中读到:
GetHashCode() 在特定对象的生命周期内的返回应该是恒定的(相同的值),即使对象的数据发生变化。在许多情况下,您应该缓存方法返回以强制执行此操作。
这是一个有效的指导方针吗?
我在 .NET 中尝试了几个内置类型,但它们的行为并非如此。
已经很久了,但是我认为仍然有必要对这个问题给出正确的答案,包括解释为什么和如何。到目前为止,最好的答案是详尽引用 MSDN 的答案——不要试图制定自己的规则,MS 人员知道他们在做什么。
但首先要做的事情是:问题中引用的指南是错误的。
现在是为什么 - 其中有两个
首先为什么:如果哈希码以某种方式计算,即使对象本身发生变化,它在对象的生命周期内也不会改变,那么它会破坏等式契约。
请记住:“如果两个对象比较相等,则每个对象的 GetHashCode 方法必须返回相同的值。但是,如果两个对象不比较相等,则两个对象的 GetHashCode 方法不必返回不同的值。”
第二句话经常被误解为“唯一的规则是,在对象创建时,相等对象的哈希码必须相等”。不知道为什么,但这也是这里大多数答案的本质。
考虑两个包含名称的对象,其中名称用于 equals 方法:同名 -> 相同的事物。创建实例 A:名称 = Joe 创建实例 B:名称 = Peter
哈希码 A 和哈希码 B 很可能不一样。当实例 B 的名称更改为 Joe 时,现在会发生什么?
根据问题的指导方针, B 的哈希码不会改变。结果将是:A.Equals(B) ==> true 但同时:A.GetHashCode() == B.GetHashCode() ==> false。
但是,equals&hashcode-contract 明确禁止这种行为。
第二个原因:虽然 - 当然 - 是正确的,但哈希码中的更改可能会破坏使用哈希码的哈希列表和其他对象,反之亦然。不更改哈希码在最坏的情况下会得到哈希列表,其中所有许多不同的对象都将具有相同的哈希码并因此位于相同的哈希箱中 - 例如,当使用标准值初始化对象时会发生这种情况。
现在来看看如何 好吧,乍一看,似乎有一个矛盾 - 无论哪种方式,代码都会中断。但是这两个问题都不是来自更改或未更改的哈希码。
MSDN中很好地描述了问题的根源:
从 MSDN 的哈希表条目:
只要在 Hashtable 中用作键,键对象就必须是不可变的。
这确实意味着:
任何创建散列值的对象都应该在对象更改时更改散列值,但是当它在 Hashtable(或任何其他使用散列的对象,当然)中使用时,它不能 - 绝对不能 - 允许对自身进行任何更改.
首先,最简单的方法当然是设计仅用于哈希表的不可变对象,在需要时将其创建为普通可变对象的副本。在不可变对象内部,显然可以缓存哈希码,因为它是不可变的。
其次如何或给对象一个“你现在被散列”-标志,确保所有对象数据都是私有的,检查所有可以更改对象数据的函数中的标志,如果不允许更改则抛出异常数据(即设置标志)。现在,当您将对象放在任何散列区域时,请确保设置标志,并且 - 以及 - 在不再需要时取消设置标志。为了便于使用,我建议在“GetHashCode”方法中自动设置标志——这样就不会被遗忘。并且“ResetHashFlag”方法的显式调用将确保程序员必须考虑现在是否允许更改对象数据。
好的,也应该说一下:在某些情况下,可以有具有可变数据的对象,其中哈希码仍然没有改变,当对象数据发生更改时,不会违反 equals&hashcode-contract。
然而,这确实要求 equals 方法也不基于可变数据。因此,如果我编写一个对象,并创建一个 GetHashCode 方法,该方法只计算一次值并将其存储在对象中以在以后的调用中返回它,那么我必须再次:绝对必须创建一个 Equals 方法,它将使用为比较存储的值,因此 A.Equals(B) 也永远不会从 false 变为 true。否则,合同将被破坏。这样做的结果通常是 Equals 方法没有任何意义——它不是原始引用 equals,但也不是一个值 equals。有时,这可能是预期的行为(即客户记录),但通常不是。
因此,只需在对象数据更改时更改 GetHashCode 结果,并且如果打算(或只是可能)使用列表或对象在哈希内部使用对象,则使对象不可变或创建只读标志以用于包含对象的哈希列表的生命周期。
(顺便说一句:所有这一切都不是 C# 或 .NET 特定的 - 它是所有哈希表实现的本质,或更一般地说是任何索引列表,当对象在列表中时,对象的标识数据永远不应该改变. 如果违反此规则,将发生意外和不可预知的行为。在某个地方,可能存在列表实现,它会监视列表中的所有元素并自动重新索引列表 - 但这些的性能充其量肯定会令人毛骨悚然。)
答案主要是,它是一个有效的指导方针,但可能不是一个有效的规则。它也没有讲述整个故事。
要指出的是,对于可变类型,您不能将哈希码基于可变数据,因为两个相等的对象必须返回相同的哈希码,并且哈希码必须在对象的生命周期内有效。如果散列码发生变化,您最终会得到一个在散列集合中丢失的对象,因为它不再存在于正确的散列箱中。
例如,对象 A 返回 1 的哈希值。因此,它进入哈希表的 bin 1。然后更改对象 A,使其返回哈希 2。当哈希表查找它时,它在 bin 2 中查找但找不到它 - 该对象在 bin 1 中是孤立的。这就是为什么哈希码必须在对象的整个生命周期内都不会改变,这只是编写 GetHashCode 实现令人头疼的一个原因。
更新
Eric Lippert 发布了一个博客,提供了关于GetHashCode
.
附加更新
我在上面做了一些更改:
指南只是一个指南,而不是规则。实际上,GetHashCode
只有当事物期望对象遵循准则时才需要遵循这些准则,例如当它被存储在哈希表中时。如果您从不打算在哈希表中使用您的对象(或任何其他依赖于 的规则GetHashCode
),您的实现不需要遵循指南。
当您看到“对象的生命周期”时,您应该阅读“对象需要与哈希表合作的时间”或类似内容。像大多数事情一样,GetHashCode
是关于知道何时打破规则。
来自MSDN
如果两个对象比较相等,则每个对象的 GetHashCode 方法必须返回相同的值。但是,如果两个对象比较不相等,则两个对象的 GetHashCode 方法不必返回不同的值。
只要确定对象的 Equals 方法的返回值的对象状态没有修改,对象的 GetHashCode 方法就必须始终返回相同的哈希码。请注意,这仅适用于应用程序的当前执行,并且如果再次运行应用程序,则可以返回不同的哈希码。
为了获得最佳性能,散列函数必须为所有输入生成随机分布。
这意味着如果对象的值发生变化,哈希码也应该发生变化。例如,“Name”属性设置为“Tom”的“Person”类应该有一个哈希码,如果将名称更改为“Jerry”,则应该有一个不同的代码。否则,Tom == Jerry,这可能不是您想要的。
编辑:
同样来自 MSDN:
覆盖 GetHashCode 的派生类也必须覆盖 Equals 以保证被认为相等的两个对象具有相同的哈希码;否则,Hashtable 类型可能无法正常工作。
只要在 Hashtable 中用作键,键对象就必须是不可变的。
我读这篇文章的方式是,可变对象应在其值更改时返回不同的哈希码,除非它们是为在哈希表中使用而设计的。
在 System.Drawing.Point 的示例中,对象是可变的,并且在X 或 Y 值更改时返回不同的哈希码。这将使其成为在哈希表中按原样使用的糟糕候选者。
我认为有关 GetHashcode 的文档有点令人困惑。
一方面,MSDN 声明对象的 hashcode 永远不应该改变,并且是恒定的。另一方面,MSDN 还声明 GetHashcode 的返回值对于 2 个对象应该是相等的,如果这 2 个对象被认为是相等的。
哈希函数必须具有以下属性:
- 如果两个对象比较相等,则每个对象的 GetHashCode 方法必须返回相同的值。但是,如果两个对象比较不相等,则两个对象的 GetHashCode 方法不必返回不同的值。
- 只要确定对象的 Equals 方法的返回值的对象状态没有修改,对象的 GetHashCode 方法就必须始终返回相同的哈希码。请注意,这仅适用于应用程序的当前执行,并且如果再次运行应用程序,则可以返回不同的哈希码。
- 为了获得最佳性能,散列函数必须为所有输入生成随机分布。
然后,这意味着您的所有对象都应该是不可变的,或者 GetHashcode 方法应该基于您的对象的不可变属性。例如,假设你有这个类(天真的实现):
public class SomeThing
{
public string Name {get; set;}
public override GetHashCode()
{
return Name.GetHashcode();
}
public override Equals(object other)
{
SomeThing = other as Something;
if( other == null ) return false;
return this.Name == other.Name;
}
}
这个实现已经违反了 MSDN 中的规则。假设您有 2 个此类的实例;instance1 的 Name 属性设置为“Pol”,instance2 的 Name 属性设置为“Piet”。两个实例都返回不同的哈希码,而且它们也不相等。现在,假设我将 instance2 的名称更改为“Pol”,那么根据我的 Equals 方法,两个实例应该相等,并且根据 MSDN 的规则之一,它们应该返回相同的哈希码。
但是,这是无法做到的,因为 instance2 的哈希码会改变,而 MSDN 声明这是不允许的。
然后,如果您有一个实体,您可以实现哈希码,以便它使用该实体的“主标识符”,这可能是理想的代理键或不可变属性。如果您有一个值对象,您可以实现哈希码,以便它使用该值对象的“属性”。这些属性构成了值对象的“定义”。这当然是价值对象的本质;你对它的身份不感兴趣,而对它的价值感兴趣。
因此,值对象应该是不可变的。(就像它们在 .NET 框架中一样,字符串、日期等......都是不可变的对象)。
想到的另一件事:
在“会话”期间(我真的不知道应该如何称呼它)“GetHashCode”应该返回一个常量值。假设您打开您的应用程序,从数据库(实体)中加载一个对象的实例,并获取其哈希码。它会返回一个特定的数字。关闭应用程序,然后加载相同的实体。这次是否要求哈希码与您第一次加载实体时的值相同?恕我直言,不是。
这是个好建议。以下是布赖恩·佩平对此事的看法:
这不止一次让我绊倒:确保 GetHashCode 在实例的整个生命周期内始终返回相同的值。请记住,在大多数哈希表实现中,哈希码用于标识“桶”。如果对象的“桶”发生变化,哈希表可能无法找到您的对象。这些可能是很难找到的错误,所以在第一时间就做好。
不直接回答您的问题,但是 - 如果您使用 Resharper,请不要忘记它具有为您生成合理的 GetHashCode 实现(以及 Equals 方法)的功能。您当然可以指定在计算哈希码时将考虑类的哪些成员。
查看 Marc Brooks 的这篇博文:
VTO、RTO 和 GetHashCode()——哦,天哪!
然后查看后续帖子(由于我是新手,无法链接,但初始文章中有一个链接)进一步讨论并涵盖了初始实施中的一些小弱点。
这是我创建 GetHashCode() 实现所需要知道的一切,他甚至提供了他的方法以及其他一些实用程序的下载,简而言之就是黄金。
哈希码永远不会改变,但了解哈希码的来源也很重要。
如果您的对象使用值语义,即对象的身份由其值定义(如字符串、颜色、所有结构)。如果您的对象的身份独立于其所有值,则哈希码由其值的子集标识。例如,您的 StackOverflow 条目存储在某个数据库中。如果您更改您的姓名或电子邮件,您的客户条目将保持不变,尽管某些值已更改(最终您通常由一些长的客户 ID # 标识)。
简而言之:
值类型语义 - 哈希码由值定义 参考类型语义 - 哈希码由某个 id 定义
如果这仍然没有意义,我建议您阅读 Eric Evans 的域驱动设计,他在其中探讨了实体与值类型(这或多或少是我在上面尝试做的)。
查看Eric Lippert的 GetHashCode 指南和规则