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

Question

我有一个字符串 anna，其中字符串中的字符值为 a = 1，n = 14(您可以计算其他字符的值，例如 (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 的字符串(聪明的做法)？我想到的唯一方法是计算 anna 的 k，即 29，然后以某种方式想到另一个长度为 3 的字符串，它给出29。

Answer 1

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

一个可能的优化:如果你需要回答多个查询(比如给定一个字符串，找到一个长度为 3 且哈希函数值相同的字符串)，你可以生成所有长度为 3 的字符串并计算一次它们的哈希值以构建一个映射 hash -> 一个长度为 3 的字符串，带有这个 hash。一旦你有了这张 map ，找到一个长度为 3 且与给定字符串具有相同散列的字符串只是一次 map 查找。