使用相同的hashcode生成两个不同的字符串

I want to do some tests which require some strings with the same hash code, but not the same strings. I couldn't find any examples, so I decided to write a simple program to do it for me.

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

The code below generates two random strings over and over until they generate the same hash code.

下面的代码不断地生成两个随机字符串，直到它们生成相同的散列代码。

    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;    }

This code seems to be working (theoretically), but it may take centuries to complete. So I was thinking of doing vice versa and generate two strings from one hash code.

这段代码似乎在(理论上)起作用，但可能需要几个世纪才能完成。所以我想反过来，从一个哈希代码中生成两个字符串。

I know it's not possible to retrieve a string from a hash code, but is it possible to generate possible strings from it?

我知道从哈希代码中检索字符串是不可能的，但是是否可以从中生成可能的字符串呢?

I'm using Visual Studio 2015 Community Edition. Version: 14.0.23107.0D14REL.

我使用的是Visual Studio 2015社区版。版本:14.0.23107.0D14REL。

.NET Framework: 4.6.00081.

net框架:4.6.00081。

2 个解决方案

#1

Finding two strings by repeatedly comparing random strings will take practically forever. Instead generate strings and store them in an a dictionary by hashcode. Then look up each. Match found pretty quickly.

通过反复比较随机字符串来找到两根字符串实际上需要花费很长时间。相反，生成字符串并通过hashcode将它们存储在一个字典中。然后查找。比赛很快找到。

MATCH FOUND!! xqzrbn and krumld hash code 80425224

匹配发现! !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 herestatic 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;}

#2

Take advantage of the Birthday Paradox. Instead of only testing two strings directly, test all strings you have seen before.

利用生日悖论。不只是直接测试两个字符串，而是测试您以前看到的所有字符串。

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();        }    }}

For my machine it produces the output

对于我的机器，它产生输出。

"699391" and "1241308" have the same hash code -1612916492

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

almost instantly.

几乎立即。

Due to how strings are hashed in .NET you may not get the exact same output as me, but it should be just as fast.

由于在。net中字符串是如何被哈希的，你可能不会得到和我一样的输出，但是它应该和我一样快。

#1