使用 C# 中的默认哈希函数生成具有相同哈希值的三个不同字符串

Question

我试图使用编程语言提供的默认哈希函数生成三个不同的字符串 A、B 和 C，以便它们的哈希值全部相等。具体来说，我需要确保A不等于B，B不等于C，A不等于C。

我尝试了多种方法，但尚未成功找到解决方案。我正在寻求帮助来实现可以满足这些要求的方法或算法。所有三个字符串的哈希值必须相同，这一点至关重要。

这是我的实现，但是它仍然不完整，因为我与前两个字符串发生了冲突，但与第三个字符串没有发生冲突。

var dictionary = new Dictionary<int, string>();

  int collusionCounter = 0, stringCounter = 0;
  string myString;
  int hash = 0;

  List<string> myList = new List<string>();


  while (true)
  {
    stringCounter++;
    myString = stringCounter.ToString();

    try
    {
      hash = myString.GetHashCode();
      dictionary.Add(hash, myString);
    }
    catch (Exception)
    {
      if (dictionary.ContainsKey(hash))
      {
        myList.Add(myString);
        collusionCounter++;
        if (collusionCounter == 2)
        {
          break;
        }
      }
      continue;
    }
  }

  var A = myList[0];
  var B = myList[1];
  var C = dictionary[hash];

  Console.WriteLine($"{A.GetHashCode()} {B.GetHashCode()} {C.GetHashCode()}");

hier 是实现的结果：

374545419 1954295680 1954295680

我将不胜感激任何关于如何有效完成这项任务的指导或见解。谢谢你！

Answer 1

.NET 中的字符串哈希码不稳定，这意味着每次运行程序时特定字符串都有不同的哈希码。哈希码仅在程序的单次执行期间稳定。这个 .NET 功能可能会破坏您想要做的事情，但是让我们假设 .NET 中的字符串哈希码是稳定的，并尝试在此假设下找到您问题的答案。

\n

通过了解生成哈希码的算法并对它进行逆向工程，您也许能够在数学上找到 3 个具有相同哈希码的不同字符串。这可能并非不现实，因为哈希码并不意味着加密安全，因此对它们进行逆向工程可能是可行的。但我不能在这个方向上帮助你，因为我不是数学家。

\n

我将建议一种暴力概率方法来解决这个问题。.NET 哈希码是 32 位数字，因此如果您有一组 2 ^ 32 + 1 (4,294,967,297) 个元素，则可以保证至少发生一次冲突。您将需要一个字符串生成器，它可以生成比这个数字更多的唯一字符串。一个好的候选者似乎是8 个小写拉丁字符的所有排列的生成器，其总体空间为 26 ^ 8 = 208,827,064,576\xe2\x80\xac 字符串。平均大约 48 个字符串将共享相同的哈希码，因此如果您随机选择一个不与其他 2 个字符串冲突的字符串，您将非常不幸。查找 3 个字符串的算法如下：

\n

\n
1. 将第一个生成的字符串添加到列表中a，并将其哈希码存储在变量中b。
\n
2. 启动一个循环，在每次迭代中生成下一个字符串，并将其哈希码与b. 如果值相等，则将生成的字符串添加到列表中a。
\n
3. 当列表中有 3 个字符串时退出循环a。这些字符串不同，但它们共享相同的哈希码。
\n

\n

我希望在大约 80 亿次循环迭代后得到你的结果。

\n