如何在C#中快速找到三个哈希值相同的不同字符串？

要满足题目要求——不重写哈希方法、不研究哈希实现、单线程快速找到结果，核心思路是利用鸽巢原理：int类型的哈希值只有约42亿种可能，但字符串的数量是无限的，必然存在大量哈希冲突。我们只需要生成一批有限的字符串，统计它们的哈希值分组，就能快速找到三个同哈希的不同字符串。

实现步骤 #

1. 用字典存储每个哈希值对应的字符串列表，键为哈希值，值为拥有该哈希的字符串集合。
2. 生成一批短字符串（比如由小写字母组成的2-3位字符串），这类字符串的总数量不大，但足够覆盖哈希冲突的概率。
3. 遍历生成的字符串，计算其默认哈希值并加入对应分组，一旦某个分组的字符串数量达到3，即可输出结果。

代码示例 #

using System;
using System.Collections.Generic;

class HashCollisionFinder
{
    static void Main()
    {
        var hashToStrings = new Dictionary<int, List<string>>();
        var charSet = "abcdefghijklmnopqrstuvwxyz";

        // 先遍历所有2位小写字母组合（共676个）
        foreach (char c1 in charSet)
        {
            foreach (char c2 in charSet)
            {
                string current = $"{c1}{c2}";
                int hash = current.GetHashCode();

                if (!hashToStrings.ContainsKey(hash))
                    hashToStrings[hash] = new List<string>();

                hashToStrings[hash].Add(current);

                if (hashToStrings[hash].Count == 3)
                {
                    Console.WriteLine("找到符合要求的三个字符串：");
                    foreach (var str in hashToStrings[hash])
                        Console.WriteLine($"- {str} 哈希值：{hash}");
                    return;
                }
            }
        }

        // 如果2位组合没找到，遍历3位组合（共17576个）
        foreach (char c1 in charSet)
        {
            foreach (char c2 in charSet)
            {
                foreach (char c3 in charSet)
                {
                    string current = $"{c1}{c2}{c3}";
                    int hash = current.GetHashCode();

                    if (!hashToStrings.ContainsKey(hash))
                        hashToStrings[hash] = new List<string>();

                    hashToStrings[hash].Add(current);

                    if (hashToStrings[hash].Count == 3)
                    {
                        Console.WriteLine("找到符合要求的三个字符串：");
                        foreach (var str in hashToStrings[hash])
                            Console.WriteLine($"- {str} 哈希值：{hash}");
                        return;
                    }
                }
            }
        }
    }
}

说明 #

• 该方法完全依赖.NET默认的String.GetHashCode()实现，不需要了解其具体算法逻辑。
• 单线程执行，遍历短字符串的速度极快，大部分情况下在遍历2位组合时就能找到结果。
• 鸽巢原理保证了必然存在这样的字符串，生成的短字符串数量足够覆盖冲突概率，无需枚举所有可能的字符串。

内容的提问来源于stack exchange，提问作者Arseni Mourzenko