在 .NET 中，Dictionary<string,TValue> 是否会发生键冲突

Question

我刚了解到：

.NET 中的字典实现为哈希表 来自此 answer and the linked MSDN article about the Dictionary<TKey, TValue> Class。
字符串哈希函数 GetHashCode() 不为每个唯一的字符串值提供唯一的哈希码 值。不同的字符串可以return相同的哈希码，根据对应的MSDN article about the string class.

这让我想到，.NET 中的字典（至少在使用字符串作为键时）容易发生键冲突。

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

此外：

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

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

关于重复项的说明：

其实我问的不是碰撞本身，而是碰撞对 functionality/correctness 的影响。
Can 2 different string have the same hash code in C#? addresses the fact that strings have non-unique hashes, which I already know and do not ask about. This is also true for What is hashCode used for? Is it unique?
我删除了关于键冲突可能性的部分，因此 Probability of getting a duplicate value when calling GetHashCode() on strings 应该不再是重复的。
What happens when hash collision happens in Dictionary key? 帮助了我，所以我认为这个问题是重复的。

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) 等。不能保证短字符串不会发生冲突等。

在 .NET 中，Dictionary<string,TValue> 是否会发生键冲突

In .NET, can there be key collisions for a Dictionary<string,TValue>

.net

c#

dictionary

key

hash-collision