c++ - 查找具有给定哈希函数的冲突字符串

Question

我有一个字符串anna，其中字符串中的字符值a = 1, n = 14 ( You can compute the value of other chars like ( char - 96 ) 和哈希函数如下所示：

int hashCode( string s ) // s = "anna";
{
    k = 0;
    for ( int i = 0; i < s.length(); i++ )
      k = ( 7 * k + 3 * s[i] ) % 61;
    return k;
}

如何找到发生碰撞的长度为 3 的字符串（一些聪明的东西）？我想到的唯一方法是计算k哪个anna是29，然后以某种方式想到另一个长度为 3 的字符串29。

Answer 1

为什么不简单地生成所有长度为 3 的字符串并计算它们的哈希值（事实上，当哈希函数的所有 61 个可能值都达到时，您可以停止）？选项的数量不会太大。

一种可能的优化：如果您需要回答多个查询（例如给定一个字符串，找到一个长度为 3 且具有相同哈希函数值的字符串），您可以生成所有长度为 3 的字符串并计算一次它们的哈希值以构建一个映射hash -> a string of length 3 with this hash. 一旦你有了这张地图，找到一个长度为 3 的字符串，它与给定的哈希值相同，这只是一次地图查找。