C# - String.GetHashCode() -> 不要用作唯一标识符

Question

我目前正在阅读 Troelsen 的书籍《C# 和 .NET 4.5 框架》。书中有一节涉及重写的示例。

public virtual int GetHashCode(); // Defined in System.Object

他说（以下引用摘自Troelsen的书）：

鉴于String类已经有一个可靠的哈希码算法，它使用字符串的字符数据来计算哈希值。如果您可以确定类上的某个字段数据对于所有实例都应该是唯一的（例如社会安全号码），只需在该字段数据上调用GetHashCode()方法即可。

基本上，他所说的是某个类有一个成员（自动只读属性）。

public string SSN {get; }

每个该类的实例都将拥有一个唯一的字符串值。 现在，在假设下，

// s1 and s2 are strings
s1.GetHashCode() != s2.GetHashCode(); // Assumption: If this true then s1 == s2 is true

他的推理是正确的。然而，当我阅读String.GetHashCode()时：

如果两个字符串对象相等，则GetHashCode方法返回相同的值。但是，每个唯一字符串值并没有一个唯一的哈希码值。不同的字符串可以返回相同的哈希码。

我想你应该明白我的意思了。如果我错了，请指出我的错误所在。

谢谢！

- jensa

---

我认为他的意思是，“如果你想为一个对象获取哈希码，你可以使用系统提供的哈希码或者一个唯一的字符串字段（也称为键）的哈希码。”他并没有声称哈希码是唯一的（它们从来不是），他是在说你不需要对整个对象进行哈希处理。 - pm100

我理解了，哈希码的目的并不是为了针对给定字符串生成唯一的整数，即我们不是在寻找 s1 != s2 => s1.GetHashCode() != s2.GetHashCode()。重写 GetHashCode 只是为了利用 String 类的 GetHaseCode 函数，以便该示例类的对象可以在使用哈希表的集合类中使用。谢谢！ - jensa

不好的建议，因为具有相同SSN但在其他成员中具有不同值的对象将具有相同的哈希码，并导致高数量的冲突。哈希码确实应该包括决定相等性的所有状态。 - usr

每当某本书和MSDN之间存在差异时，MSDN胜出。 MSDN明确指出，您可能会遇到哈希冲突，不能依赖于字符串的哈希唯一性。这本书是错误的。 - Sam Axe

@usr 这本书假设不会有相同的 Person 实例具有相同的 SSN 值：“如果您可以为类上的某个字段数据确定唯一性，该字段数据对于所有实例都应该是唯一的（例如社会安全号码）”。但是，如果您实际上没有根据 SSN 定义相等性，则您的观点非常值得记住。 - user743382

Answer 1

< p > GetHashCode 的目的不是为对象生成唯一标识符，而是实现基于 哈希表 的数据结构，例如 Dictionary<K, V> 或 HashSet<T>。

哈希函数被要求确保如果 x == y，则 x.GetHashCode() == y.GetHashCode()，但反之不成立：两个不同的对象可以有相同的哈希码。这种情况称为哈希冲突。

哈希表结构在发生冲突时仍然可以正常工作，但会运行得更慢，因为程序需要花费时间来消除正在搜索的冲突对象。因此，一个好的哈希函数将努力最小化冲突。(请注意，如果一个类有超过2^32个可能值，那么完全避免冲突是数学上不可能的，因为鸽笼原理的存在。)

那么，如何为您的类编写一个良好的 GetHashCode 实现呢？做一些复杂的数学运算，将类的每个字段转换为 int，然后对其中的系数确定最佳值吗？

根据 Troelsen 的说法，不需要。只需取您的“最独特”的 string 字段，并对其调用 GetHashCode()。编写 System.String.GetHashCode 的开发人员知道他们在做什么，所以只需使用它，就会自动利用他们的“可靠哈希代码算法”。

- dan04

---

那么使用 HashSet 对于大量字符串的集合来说，相比于 string[] 可以减少内存占用，是吗？ - FindOutIslamNow

@FindOutIslamNow：不，它并不能减少内存使用量。哈希表相对于简单数组的优势在于速度：在正确实现的哈希表中搜索项目的平均情况是O(1)，而在排序数组或二叉树中为O(log n)，在未排序数组中为O(n)。 - dan04

Answer 2

你说得对，相等的哈希码并不保证相等的值。

但你误解了这句话的含义。

这句话特指实现一个Person类的哈希码计算，该类包含一个SSN属性。相等的SSN值意味着相等的Person值。不同的SSN值意味着不同的Person值。（注意：这在现实中不一定成立。）

现在，你需要为Person计算哈希码，以确保两个相等的Person实例具有相同的哈希码，并且最好使得两个不相等的Person实例具有不同的哈希码（尽管后者无法保证）。由于相等是根据SSN定义的，因此重用SSN的哈希码已经可以达到这个目的。

- user743382

Answer 3

如果两个字符串对象相等，则GetHashCode方法返回相同的值。但是，每个唯一的字符串值没有唯一的哈希码值。不同的字符串可以返回相同的哈希码。

有无限数量的字符串，但只有2^32个可能的哈希码值。两个不同的字符串最终具有相同的哈希值是不可避免的。由于生日问题，这种情况比人们想象的更常见。

不要将其用作唯一标识符，这是一个好建议。 .NET的调试版本定期变化哈希码以帮助捕获此类问题，不同的框架版本不能保证生成相同的哈希。请参阅此处获取更多信息。

请查看Eric Lippert关于此主题的博客。

- Eric J.

---

谢谢提供链接，这个也很相关：http://ericlippert.com/2010/03/22/socks-birthdays-and-hash-collisions/ - Eric Lippert

有趣的解释方式...将袜子配对看作是一种2位哈希算法。 - Eric J.

旁注：当我在一家创建设备指纹的公司工作时，我们使用了一个64位哈希（City Hash）。随着数千万个哈希值的增加，在那个64位哈希空间中出现了一些哈希冲突。 - Eric J.