生成两个不同的字符串，但它们具有相同的哈希值

Question

我想进行一些测试，需要一些具有相同哈希码但不同字符串的字符串。我找不到任何例子，所以决定写一个简单的程序来为我完成。

以下代码会一遍又一遍地生成两个随机字符串，直到它们生成相同的哈希码。

    static Random r = new Random();
    static void Main(string[] args)
    {
        string str1, str2;
        do
        {
            str1 = GenerateString();
            str2 = GenerateString();
        } while (str1.GetHashCode() != str2.GetHashCode() && str1 != str2);

        Console.WriteLine("{0}\n{1}", str1, str2);
    }

    static string GenerateString()
    {
        string s = "";
        while (s.Length < 6)
        {
            s += (char)r.Next(char.MaxValue);
        }
        return s;
    }

这段代码理论上似乎可以工作，但可能需要几个世纪才能完成。因此，我想反其道而行之，从一个哈希码生成两个字符串。

我知道不可能从哈希码中检索出一个字符串，但是否可能从中生成可能的字符串？

我正在使用Visual Studio 2015 Community Edition。 版本：14.0.23107.0D14REL。

.NET Framework: 4.6.00081。

- M.kazem Akhgary

---

如果你只是想进行测试，可以创建一个类并重写 GetHashCode 方法，使其返回一个固定值的糟糕实现，从而在任何地方都产生冲突。 - Alejandro

只需要几秒钟，生日悖论可以快速验证。在32位代码中，“1241308”的哈希值等于“699391”的哈希值；在64位代码中，“942”的哈希值等于“9331582”的哈希值。 - Hans Passant

利用生日悖论的方法是将所有生成过的字符串存储起来。每次生成新字符串时，都要与所有之前的字符串进行比较，这样可以极大地增加找到匹配项的机会。如果有N个哈希码，则经过检查N/2个字符串后，你的方法将有50%的几率找到碰撞。而使用生日方法，在检查√N个字符串后，也有50%的几率发现碰撞。在哈希码为32位且N约为40亿的情况下，这意味着要检查20亿个字符串或者只需检查65000个字符串，区别非常明显。 - John Kugelman

@ScottChamberlain：那不是真的。这个数学公式只适用于哈希值大致上符合均匀随机分布的情况。如果不是，你可能需要更多的哈希值才能找到碰撞 _(例如 hash(x) = x%INT_MAX，你需要迭代超过 INT_MAX 个值才能找到碰撞)_。 - BlueRaja - Danny Pflughoeft

最时髦的方法是使用SMT求解器来寻找哈希码碰撞。 - usr

Answer 1

通过反复比较随机字符串来查找两个字符串将需要相当长的时间。相反，生成字符串并按哈希码将其存储在字典中。然后查找每个字符串。匹配会很快被发现。

匹配成功！！xqzrbn和krumld的哈希码为80425224

void Main()
{

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

    while(true) {
        var s = RandomString();        
        var h = s.GetHashCode();
        string s2;
        if (lookup.TryGetValue(h, out s2) && s2 != s) {
            Console.WriteLine("MATCH FOUND!! {0} and {1} hash code {2}",
                lookup[h],
                s,
                h);
            break;
        }
        lookup[h] = s;

        if (lookup.Count % 1000 == 0) {
            Console.WriteLine(lookup.Count);
        }
    }
}

static Random r = new Random();

// Define other methods and classes here
static string RandomString() {

    var s = ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString();

    return s;
}

- Samuel Neff

---

感谢 @ScottChamberlain 和 SamuelNeff 的回答。看起来生成字符串的方法也会影响概率！更多的字符会降低获取相同哈希码的机会。 - M.kazem Akhgary

@M.kazemAkhgary 这不是真的，你有这种感觉是因为alpha方法使用了更多的CPU计算能力，所以需要更长时间来找到匹配项。项目数量应该是相同的。 - Behrooz

@Behrooz 如果你存储了许多具有完全相同的HashCode但Equals()返回false的值，那么字典“爬行”的唯一方法是。使用int，不可能有(x.GetHashCode() == y.GetHashCode()) && (x.Equals(y) == false)。 - Scott Chamberlain

@Behrooz 请查看我的这个旧回答，我在其中详细介绍了比评论更多的过程。 - Scott Chamberlain

@Behrooz 注意，O(1)并不意味着快，它意味着常数时间。它可能一直很慢，但仍然是O(1)。这并不是说字典很慢，只是一般而言。字典的性能取决于桶的数量和键在桶中的分布（哈希码的随机性）。 - Samuel Neff

Answer 2

利用生日悖论。不仅直接测试两个字符串，而是测试之前出现过的所有字符串。

using System;
using System.Collections.Generic;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var words = new Dictionary<int, string>();

            int i = 0;
            string teststring;
            while (true)
            {
                i++;
                teststring = i.ToString();
                try
                {
                    words.Add(teststring.GetHashCode(), teststring);
                }
                catch (Exception)
                {
                    break;
                }
            }

            var collisionHash = teststring.GetHashCode();
            Console.WriteLine("\"{0}\" and \"{1}\" have the same hash code {2}", words[collisionHash], teststring, collisionHash);
            Console.ReadLine();
        }
    }
}

对于我的机器，它会几乎瞬间产生输出

“699391”和“1241308”具有相同的哈希码-1612916492

由于在.NET中字符串是如何进行哈希处理的，您可能无法得到与我完全相同的输出，但速度应该一样快。

- Scott Chamberlain

---

在.NET Core上运行时，哈希码每次应用程序运行时都会更改，因此在此问题中发布的任何哈希码都将与您的应用程序不同。该行为在这里有所描述。如果您需要两个具有相同哈希码的字符串进行测试，就像我一样，您需要每次应用程序运行时生成它们。幸运的是，这只需要不到100毫秒。或者，您可以创建一个新类，并使用GetHashCode的错误实现，就像Alejandro建议的那样。 - Jeremiah Mercier

是的，这就是我为什么放置了“由于在.NET中字符串被哈希的方式，你可能得不到与我完全相同的输出，但速度应该是一样快的。” - Scott Chamberlain