理解哈希码

理解哈希码

我不止一次看到有人问这样的问题:
”
我有一些动态生成字符串的过程，我想设计一个算法，它输入一个字符串并为该字符串生成一个小的唯一标识符（哈希码），以便两个相同的字符串具有相同的标识符，并且如果两个字符串不同，那么它们将具有不同的标识符。我尝试了String.GetHashCode 方法，但偶尔会发生冲突。有没有办法生成保证唯一性的哈希码呢？
”

如果你可以限制要散列的字符串的域(所有可能性)，你有时可以实现上述算法的唯一性。例如，如果域是有限集，则可以开发所谓的完美哈希，以保证域字符串之间没有冲突。

在一般情况下，如果你不知道要散列哪些字符串，这是不可能的。假设你的哈希码是 32 位值。这意味着有 2 的 32 次方个可能的哈希值。但是有超过 2 的 32 次方个可能的字符串。因此，根据鸽子洞原则(又称抽屉原理)，必须至少存在两个具有相同哈希代码的字符串。

关于鸽子洞原理的一个鲜为人知的事实是，它与鸽子无关。术语”鸽子洞”是指桌子上的一个小隔间，用于分发文件或信件等物品。 (因此动词 “to pigeonhole”：分配一个类别，通常基于粗略的概括。因此，鸽子洞原理是指将纸张分类到鸽子洞中的过程，而不是鸠鸽科鸟类的筑巢习性)

最后

Raymond Chen的《The Old New Thing》是我非常喜欢的博客之一，里面有很多关于Windows的小知识，对于广大Windows平台开发者来说，确实十分有帮助。
本文来自：《Understanding hash codes》