将字符串映射到整数的哈希函数

Question

寻找一些哈希函数，用于将字符串映射到整数，满足以下限制。

限制： 相同的字符串映射到相同的数字。 不同的字符串映射到不同的数字。 在应用程序的一个运行中，我得到了相同长度的字符串，在运行时我才知道长度。

有什么建议可以创建这个哈希函数吗？

- Night Walker

---

使用 String.GetHashCode() 方法。 - KV Prajapati

@Yuck，字符串可以是任何ASCII值。 - Night Walker

@AVD 虽然在 C# 中是 GetHashCode()。 - Yuck

@L.B：但这真的很误导人。他要求 X，你给了他一个答案，但没有表明它不能满足 X。 - jason

@Jason，好的，你想要什么？道歉吗？ - L.B

Answer 1

哈希函数不能保证不同的值（在您的情况下是字符串）生成不同的哈希码，但相同的值总是生成相同的哈希码。

这是因为信息被丢失了。如果您有一个长度为32个字符的字符串，它将有64个字节（每个字符2个字节）。一个int 哈希码有四个字节。这是不可避免的，被称为冲突。

注意：Dictionary<Tkey,TValue>在内部使用哈希表。因此实现了冲突解决策略。请参见 MSDN 上的C# 2.0使用数据结构的广泛研究。

这是当前实现dictionary.cs的代码。

- Olivier Jacot-Descombes

Answer 2

你不可能找到一种哈希算法，它保证对于不同的字符串不会返回相同的整数。根据定义，哈希算法会出现碰撞。在世界上可能的字符串数量远远超过32位整数的可能性。

- Robert Levy

Answer 3

不同的字符串对应不同的数字。

由于字符串数量多于数字数量，因此在不限制输入集的情况下是不可能完成的。如果将 n 个鸽子放入 m 个盒子中，且 n > m，则至少有一个盒子会装有超过一个鸽子。

- jason

Answer 4

String.GetHashCode函数不符合您的需求吗？

- Jesse Smith

---

它无法满足不同字符串对应于不同数字的不可能要求。 - jason

@Jason：没错，但 GetHashCode 提供的高概率可能已经足够满足 OP 的需求了。 - Heinzi

@Heinzi - 以后几年内，如果他的应用程序突然停止工作，他能否联系您进行调试？ :) - Robert Levy

@Heinzi：GetHashCode并不能保证这样的事情！实际上，你很有可能会遇到碰撞。这就是生日问题，只不过日历中有更多的天数。使用2^32个桶，只需要大约75000个字符串就有超过0.5的概率发生碰撞。 - jason

@Jason：关于生日悖论的观点很好。正如我所说，这取决于操作员的要求。如果他想为随机字符串值实现哈希表，则GetHashCode就可以了。如果他想检查相等性，则没有哈希函数是足够的。 - Heinzi

“高概率”的唯一性是一种幻觉。我发现当对字符串进行哈希处理时，在生成约70,000个字符串后，发生冲突的可能性为50％。我从未遇到过插入200,000个字符串而没有生成重复项的情况。这适用于真实世界数据以及我在过去15年中编写的多个应用程序中随机生成的测试数据。 - Jim Mischel