代码之家  ›  专栏  ›  技术社区  ›  Marcel

在.NET中,字典[duplicate]是否存在键冲突

  •  1
  • Marcel  · 技术社区  · 7 年前

    我刚刚了解到:

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

    在这样的关键碰撞中会发生什么?是否有任何已知的唯一字符串值会发生碰撞?字典会因为这些键值而被打破吗?

    • 这是否取决于代码是在32位还是64位系统上运行?

    注意:我指的不是一个特定的.NETCLR,但如果有必要的话,让我们谈谈桌面的4.5.2 32位版本。


    关于重复项的说明:

    1 回复  |  直到 7 年前
        1
  •  5
  •   Dmitrii Bychenko    7 年前

    您可以轻松生成此类碰撞(请参见 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
    

      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 内部加工 可以依赖