object.GetHashCode()能否为不同机器上的相同对象(字符串)产生不同的结果?
是否有可能同一个对象,特别是string
或任何原始类型或非常简单的类型(如struct
),在不同的机器上调用时生成.GetHashCode()
方法的不同值?
例如,表达式"Hello World".GetHashCode()
可以在不同的机器上生成不同的值。 我主要是要求C#.NET,但我想这可能适用于Java甚至其他语言?
编辑:
正如下面的答案和评论所指出的那样,我知道.GetHashCode()
可以被覆盖 ,并且不能保证它在不同版本的框架之间产生的结果。 因此,重要的是要澄清我有简单的类型(不能inheritance,因此GetHashCode()
被覆盖)并且我在所有机器上使用相同版本的框架。
简短回答:是的。
但简短的答案并不好玩,是吗?
当您实现GetHashCode()
您必须做出以下保证:
当在另一个应该被认为与此相等的对象上调用
GetHashCode()
,在此App Domain中,将返回相同的值。
而已。 有一些事情你真的需要尝试做(尽可能多地使用不相等的对象传播这些东西,但不要花太多时间来讨论它首先超过散列的所有好处)和你的代码如果你不这样做会很糟糕,但它实际上不会破坏。 如果你不走那么远就会破裂,因为那样:
dict[myObj] = 3; int x = dict[myObj];//KeyNotFoundException
好的。 如果我正在实现GetHashCode()
,为什么我会更进一步,为什么不呢?
首先,为什么我不呢?
也许这是一个略有不同的程序集版本,我在构建之间改进(或至少尝试过)。
也许一个是32位,一个是64位,我为了效率而疯狂,并为每个选择不同的算法来使用不同的字大小(这不是闻所未闻的,尤其是在散列像集合或字符串这样的对象时) 。
也许我决定在决定什么构成“平等”对象时要考虑的一些因素本身在这种方式上因系统而异。
也许我实际上是故意用不同的构建引入不同的种子来捕捉任何同事错误地依赖我的哈希码的情况! (我听说MS使用string.GetHashCode()
的实现来做这件事,但是不记得我是否从可靠或轻信的来源中听到了这一点。
主要是,这将是前两个原因之一。
现在,为什么我可以提供这样的保证?
如果我这么做的话,很可能是偶然的。 如果可以仅基于单个整数id来比较元素的相等性,那么我将使用它作为我的哈希码。 对于不太好的哈希,任何其他东西都会更有效。 我不太可能改变这个,所以我可能会。
我可能的另一个原因是我自己想要保证。 没有什么可说的,我不能提供它,只是我不需要。
好的,让我们做一些实用的事情。 在某些情况下,您可能需要与机器无关的保证。 有些情况下你可能会想要相反,我会稍微谈谈。
首先,检查你的逻辑。 你能处理碰撞吗? 好的,那我们就开始吧。
如果它是你自己的类,那么实现以便提供这样的保证,记录它,并且你已经完成了。
如果它不是你的类,那么以提供它的方式实现IEqualityComparer
。 例如:
public class ConsistentGuaranteedComparer : IEqualityComparer { public bool Equals(string x, string y) { return x == y; } public int GetHashCode(string obj) { if(obj == null) return 0; int hash = obj.Length; for(int i = 0; i != obj.Length; ++i) hash = (hash << 5) - hash + obj[i]; return hash; } }
然后使用它而不是内置的哈希码。
有一个有趣的案例,我们可能想要相反。 如果我可以控制你正在散列的字符串集,那么我可以选择一堆具有相同哈希码的字符串。 基于哈希的集合的性能将会变得更糟,并且非常糟糕。 机会是我可以比你处理它更快地做到这一点,所以它可以是拒绝服务攻击。 发生这种情况的情况并不多,但重要的是如果你正在处理我发送的XML文档,你不能只排除一些元素(许多格式允许元素自由)。 然后解析器中的NameTable
会受到伤害。 在这种情况下,我们每次都创建一个新的哈希机制:
public class RandomComparer : IEqualityComparer { private int hashSeed = Environment.TickCount; public bool Equals(string x, string y) { return x == y; } public int GetHashCode(string obj) { if(obj == null) return 0; int hash = hashSeed + obj.Length; for(int i = 0; i != obj.Length; ++i) hash = hash << 5 - hash + obj[i]; hash += (hash << 15) ^ 0xffffcd7d; hash ^= (hash >>> 10); hash += (hash << 3); hash ^= (hash >>> 6); hash += (hash << 2) + (hash << 14); return hash ^ (hash >>> 16) } }
这将在给定的使用中保持一致,但从使用到使用不一致,因此攻击者无法构造输入以强制它为DoSsed。 顺便说一句, NameTable
不使用IEqualityComparer
因为它想要处理具有索引和长度的char数组而不构造字符串,除非必要,但它确实做了类似的事情。
顺便说一句,在Java中, string
的哈希码被指定并且不会改变,但对于其他类可能不是这种情况。
编辑:在上面的ConsistentGuaranteedComparer
中对方法的整体质量进行了一些研究之后,我不再满足于在我的答案中使用这些算法; 虽然它用于描述这个概念,但它并没有像人们想象的那样好。 当然,如果一个人已经实现了这样的事情,那么就不能在不违反保证的情况下改变它,但如果我现在建议使用我的这个库,那么在研究之后写的如下:
public class ConsistentGuaranteedComparer : IEqualityComparer { public bool Equals(string x, string y) { return x == y; } public int GetHashCode(string obj) { return obj.SpookyHash32(); } }
对于上面的RandomComparer
,并没有那么糟糕,但也可以改进:
public class RandomComparer : IEqualityComparer { private int hashSeed = Environment.TickCount; public bool Equals(string x, string y) { return x == y; } public int GetHashCode(string obj) { return obj.SpookyHash32(hashSeed); } }
或者更难以预测:
public class RandomComparer : IEqualityComparer { private long seed0 = Environment.TickCount; private long seed1 = DateTime.Now.Ticks; public bool Equals(string x, string y) { return x == y; } public int GetHashCode(string obj) { return obj.SpookyHash128(seed0, seed1).GetHashCode(); } }
即使在不同的运行中,它也会在同一台机器上产生不同的结果。
所以它基本上可以用来(实际上是用来)在程序的当前运行期间检查一些东西,但是没有意义来存储它,以后检查它的东西。 导致您获得的数字是由运行时生成的。
编辑
对于字符串的特定情况,即使在不同的机器上,它也会产生相同的结果,除非机器具有不同的架构。