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

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

如果不知道GetHashCode的

精确

实现（我也不知道），您可以使用有关字符串哈希通常如何实现的不完整知识。

例如，这些哈希码通常是以哈希大小（32 位）为模计算的字符代码的线性函数。如果我们进行这样的猜测，那么我们可以找到 3 个具有相同哈希码的字符串，如下所示：

1. 查找 2 个具有相同哈希值的字符串。由于生日悖论，您只需对 65K 左右的字符串进行哈希处理即可找到重复项。仅使用

   a

   和

   b

   制作所有琴弦，以确保差异很小。将它们全部设为 32 个字符长。
2. 找到两个字符串后，计算字符代码之间的差异。 您可以将这些差异添加到任何字符串，而无需更改散列，只要不下溢或溢出任何字符即可。因为我们仅使用

   a

   和

   b

   制作字符串，所以所有差异均为 +1 或 -1。

现在您可以使用字母表中间的 32 个字符生成任何您喜欢的字符串。添加与 (2) 的差异以生成具有相同哈希值的第二个字符串。再次添加差异以形成第三个。