如何在不使用暴力方法的情况下找到具有哈希冲突的三个不同字符串？

Question

我在招聘面试中看到了以下问题：

在 C# 中如何找到具有相同哈希码的三个不同字符串？

换句话说，给定字符串a、b、 和c，以下四个陈述应该为真：

a != b
a != c
a.GetHashCode() == b.GetHashCode()
a.GetHashCode() == c.GetHashCode()

笔记：

1. 您不应该覆盖GetHashCode()也不应该使用自己的String类。使用默认的 .NET 实现。
2. 您不需要知道string.GetHashCode().
3. 人们应该相对较快地找到结果，而不必使用多线程。

我对此有点困惑。有没有一种方法可以做到这一点，而无需实际逐一枚举字符串，这肯定会非常慢，并且无需检查实际实现string.GetHashCode()来找出如何进行冲突？

Answer 1

您只需生成大约 1600 万个哈希值即可找到出现 3 次的哈希值。这只需要几秒钟，并且适合合理的内存量：

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        Random rnd = new Random();
        var dict = new Dictionary<int,String>();
        var pairDict = new Dictionary<int, Tuple<String, String>>();
        String[] result = null;
        while(result == null) {
            String s = rnd.Next(0x40000000).ToString("x8");
            int hash = s.GetHashCode();
            String match;
            if (dict.TryGetValue(hash, out match)) {
                if (s == match) {
                    // already tried this string
                    continue;
                }
                Tuple<String, String> pair;
                if (pairDict.TryGetValue(hash, out pair)) {
                    if (s == pair.Item2) {
                        // already tried this string
                        continue;
                    }
                    result = new String[] {s, pair.Item1, pair.Item2};
                } else {
                    pairDict.Add(hash, new Tuple<String, String>(match, s));
                }
            } else {
                dict.Add(hash, s);
            }
        }
        foreach(String s in result) {
            Console.WriteLine( s + ".GetHashCode() == " + s.GetHashCode());
        }
    }
}