在.NET中,可以存在Dictionary <string,TValue>的关键冲突

Question

我刚刚了解到:

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

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

这种钥匙碰撞会发生什么？是否存在任何已知的唯一字符串值,实际发生碰撞？字典是否会在这些关键值上被打破？

另外:

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

注意:我不是指特定的.NET CLR,但如果重要,那么让我们来谈谈桌面的4.5.2 32位版本.

---

关于重复的说明:

• 实际上,我并不是在询问碰撞本身,而是关于它们在功能/正确性方面的含义.
• 2个不同的字符串可以在C#中使用相同的哈希码吗？解决了字符串具有非唯一哈希的事实,我已经知道并且没有问过.对于hashCode用于什么,情况也是如此？它有独特之处吗？
• 我删除了关于密钥冲突的可能性的部分,因此在字符串上调用GetHashCode()时获取重复值的概率应该不再重复.
• 在Dictionary键中发生哈希冲突会发生什么？帮助了我,所以我认为这个问题是重复的.

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)等.不能保证短字符串没有冲突等.