在 .NET 中，字典<字符串、电视是否存在键冲突>

Question

我刚刚了解到：

• .NET 中的字典实现为哈希表，来自此答案和有关Dictionary<TKey, TValue>类的链接 MSDN 文章。
• 字符串哈希函数GetHashCode()不为每个唯一字符串值提供唯一的哈希代码值。不同的字符串可以返回相同的哈希代码，根据有关字符串类的相应 MSDN 文章。

这让我想到，.NET 中的字典(至少在使用字符串作为键时(容易受到键冲突的影响。

在这样的密钥碰撞中会发生什么？是否有任何已知的唯一字符串值，实际上会发生冲突？字典会在这些键值上被破坏吗？

此外：

• 这是否取决于代码是在 32 位还是 64 位系统上运行？
• 使用长达特定长度的短字符串安全吗？安全？

注意：我不是指特定的 .NET CLR，但如果它很重要，让我们谈谈桌面的 4.5.2 32 位版本。

---

关于重复项的注意事项：

• 实际上，我问的不是碰撞本身，而是它们对功能/正确性的影响。
• 2 个不同的字符串在 C# 中可以具有相同的哈希代码吗？解决了字符串具有非唯一哈希的事实，我已经知道并且没有询问。对于哈希代码的用途是什么也是如此？它是独一无二的吗？
• 我删除了关于密钥冲突可能性的部分，因此在字符串上调用 GetHashCode(( 时获得重复值的概率应该不再是重复的。
• 当字典键中发生哈希冲突时会发生什么？ 帮助了我，所以我认为这个问题是重复的。

Answer 1

您可以轻松生成此类冲突(请参阅 https://en.wikipedia.org/wiki/Birthday_problem(，例如

// key   - computed hash value
// value - original string
Dictionary<int, string> hashes = new Dictionary<int, string>();
for (int i = 0; ; ++i) {
string st = i.ToString();
int hash = st.GetHashCode();
string collision = null;
if (hashes.TryGetValue(hash, out collision)) {
Console.Write($"Collision: "{collision}" and "{st}" hash {hash}");
break;
}
else
hashes.Add(hash, st);
}

结果(在我的工作站 .Net 4.6.1 x86(：

Collision: "699391" and "1241308" hash -1612916492

结果(在我的工作站 .Net 4.6.1 在 IA-64 重新编译(：

Collision: "942" and "9331582" hash -1864841629

因此，如果您想查看密钥冲突(在 x86 模式下(：

// Both "699391" and "1241308" keys have the same hash -1612916492
Dictionary<string, string> demo = new Dictionary<string, string>() {
{"699391", "abc"},
{"1241308", "def"},
};

最后，String.GetHashCode是.Net的内部工作原理，它可以依赖于.Net版本，模式(IA64或x86(等。不能保证短字符串没有冲突等。