hashCode用于什么?它是唯一的吗?

149
我注意到在 WP7 中的每个控件和项目中都有一个名为 getHashCode() 的方法,它返回一系列数字。我能否使用此哈希码来识别一个项目?例如,我想在设备中识别一张图片或一首歌曲,并检查其位置。如果特定项目的哈希码是唯一的,则可以完成此操作。
你能帮忙解释一下 hashCode 和 getHashCode() 的用途吗?

1
我知道什么是hashCode,我尝试多次运行我的代码以获取hashCode,并且每次对于相同的项目都返回相同的hashCode,似乎没有重复,但我并不是非常确定。好吧,如果你想要downvote,那就没关系,这是你的意见。无论如何,感谢您的编辑! - Nghia Nguyen
5个回答

296

类比简单解释

在了解了它的全部内容后(MSDN文档对我来说有点复杂),我想通过一个“故事”来简化它,希望可以更容易理解。

摘要:什么是哈希码?

Digital Fingerprint - Picture attribute to Pixabay - Freely available for use at: https://pixabay.com/en/finger-fingerprint-security-digital-2081169/

  • 这是一个指纹。

  • 它有什么用处?我们可以使用这个指纹来识别感兴趣的人。

您可以把哈希码想象成我们尝试唯一地识别某人

我是一名侦探,正在寻找罪犯。让我们称他为Cruel先生。(当我还是孩子时,他是臭名昭著的杀人犯——他闯进一所房子绑架并谋杀了一个可怜的女孩,抛弃了她的尸体,他仍然逍遥法外——他在我小时候给我留下了创伤,但那是另外一回事。)Cruel先生有某些特殊的特征,我可以使用这些特征在人海中唯一地识别他。我们在澳大利亚有2500万人口。其中一个是Cruel先生。怎么找到他呢?

不好的识别Cruel先生的方法

显然,Cruel先生有蓝眼睛。这没什么帮助,因为澳大利亚几乎一半的人都有蓝眼睛。

好的识别Cruel先生的方法

还有什么其他方法吗? 我知道:我将使用指纹!

优点

  • 两个人拥有完全相同的指纹非常非常困难(不是不可能,但极其不太可能)。
  • Cruel先生的指纹永远不会改变。
  • Cruel先生整个人都应该(理想情况下)体现在他的指纹中,包括他的外貌、发色、个性、饮食习惯等等,以至于如果他有一个兄弟姐妹(非常相似但不完全相同),那么两者应该具有不同的指纹。我说“应该”,因为我们不能保证这个世界上的两个人会有不同的指纹。
  • 但是我们可以始终保证Cruel先生的指纹始终相同,并且他的指纹永远不会改变。

上述特征通常是良好哈希函数的基础:对于给定的输入,我们希望获得唯一的输出-每次都是相同的输出;如果我们微调输入,则应该得到完全不同的输出。这个输出,就是“哈希码”。

hashFunction(string input) { // etc. }

hashFunction("1234") => "ABCD" output
hashFunction("1235") => "KDSL" output //completely different, even though the input changed only the last digit

那么什么是“碰撞”?

假设我得到一份线索,发现有人的指纹与克鲁先生的指纹相匹配。这意味着我找到了克鲁先生吗?可能!我必须仔细检查。如果我使用SHA256(一种哈希函数)并在只有5个人的小镇中寻找,那么我很可能找到了他!但是,如果我使用另一种著名的哈希函数MD5,在一个超过2^1000人的城市中查找指纹,则会有非常大的可能性出现两个完全不同的人具有相同的指纹。

那么这一切的好处是什么?

哈希码的唯一真正好处是,如果您想将某些东西放入哈希表中,而哈希表中您想快速找到对象的位置,那么哈希码就非常实用。它是通过一个小小的牺牲来大幅提高性能的技巧,而这个小小的牺牲是准确性。

假设我们有一个填满了人员信息的哈希表——澳大利亚2500万嫌疑人。克鲁先生就在其中某个位置.....我们如何快速地找到他呢?你不想考虑每个人的独特特征,因为那会花费太多时间。相反,你可以使用哈希码!哈希码可以告诉您两个人是否不同,例如Joe Bloggs不是克鲁先生。如果指纹不匹配,那么你就知道肯定不是克鲁先生。但是,如果指纹确实匹配,根据你使用的哈希函数而言,已经相当有把握找到了目标。但这并非百分之百确定。唯一确定的方法是进一步调查:(i)他/她是否有机会/动机,(ii)证人等等。

当您使用计算机时,如果两个对象具有相同的哈希码值,则您需要进一步调查它们是否真正相等。例如,您必须检查对象是否具有相同的高度、重量等,如果整数相同,或者如果客户ID匹配,然后得出结论它们是否相同。这通常通过实现IComparer或IEquality接口来完成。

关键摘要

基本上,哈希码就是指纹。

  1. 理论上,两个不同的人/对象仍可能具有相同的指纹。换句话说,如果您有两个相同的指纹......它们不一定都来自同一人/对象。
  2. 但是,相同的人/对象总会返回相同的指纹
  3. 这意味着如果两个对象返回不同的哈希码,那么您可以百分之百确定这些对象是不同的。

理解以上内容可能需要一些时间,建议多读几遍直到完全理解。


2
回复:MSDN文档让我脑细胞死了好几个......我的脑细胞也被逼到了自杀的边缘,只是因为我睡着了才得以幸存 ;) - Shwrk
你在最后加上那个星号注释,毁了整个精美的解释。 - Waldemar Gałęzinowski
我很喜欢它!尤其是名字“Mr.Cruel”! - João Pedro Andrade Marques
作为一个真正的犯罪迷,这可能是我最喜欢的SO答案...永远。 - IfElseTryCatch
我错过了像这样用例子解释的stackoverflow帖子。这让我开心。 - MrAlbino

114

MSDN表示:

哈希码是用于在等式测试期间标识对象的数字值。 它还可以作为集合中对象的索引。

GetHashCode方法适用于哈希算法和数据结构(如哈希表)。

GetHashCode方法的默认实现不保证对于不同对象返回唯一值。此外,.NET Framework不保证GetHashCode方法的默认实现,它返回的值将在.NET Framework的不同版本之间相同。因此,不能将此方法的默认实现用作用于哈希目的的唯一对象标识符。

派生类型可以重写GetHashCode方法。 值类型必须覆盖此方法以提供适用于该类型的哈希函数,并在哈希表中提供有用的分布。 对于唯一性,哈希码必须基于实例字段或属性的值而不是静态字段或属性。

在Hashtable对象中用作键的对象也必须重写GetHashCode方法,因为这些对象必须生成自己的哈希码。 如果用作键的对象不提供有用的GetHashCode实现,则可以在构造Hashtable对象时指定哈希码提供程序。 在.NET Framework版本2.0之前,哈希码提供程序基于System.Collections.IHashCodeProvider接口。 从版本2.0开始,哈希码提供程序基于System.Collections.IEqualityComparer接口。

基本上,哈希码存在是为了使哈希表成为可能。
两个相等的对象保证具有相等的哈希码。
两个不相等的对象不能保证具有不相等的哈希码(这称为冲突)。


5
MSDN上的引用现已过时,现在MSDN已不再明确哈希码不是唯一的。 - Sam Hobbs

14

GetHashCode()用于支持将对象作为哈希表的键。 (Java等中也存在类似的东西)。目标是让每个对象返回不同的哈希码,但这通常无法绝对保证。 但是,必须确保两个逻辑上相等的对象返回相同的哈希码。

典型的哈希表实现从hashCode值开始,取模(因此将该值限制在一个范围内),并将其用作指向“桶”数组的索引。


8

这不仅适用于WP7,而是所有.Net对象都存在的问题。它会做你所描述的事情,但我不建议您在应用程序中将其作为唯一标识符,因为它不能保证是唯一的。

Object.GetHashCode 方法


3
这是来自msdn的一篇文章:https://blogs.msdn.microsoft.com/tomarcher/2006/05/10/are-hash-codes-unique/。虽然有些人声称哈希码为给定输入生成唯一值,但事实上,在技术上寻找到两个不同的数据输入以产生相同的哈希值是可行的,虽然难度较大。但是,哈希算法的有效性取决于生成的哈希码的长度和被哈希的数据的复杂性。因此,只需使用适合数据大小的哈希算法即可获得唯一的哈希码。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接