使用给定的哈希函数查找冲突字符串
Find a collision string with a given hash function
我有一个字符串 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 的字符串（聪明的东西）？我想到的唯一方法是计算 anna 的 k，即 29，然后以某种方式想到另一个长度为 3 的字符串，它给出 29.
你为什么不简单地生成所有长度为 3 的字符串并计算它们的哈希值（事实上，当哈希函数的所有 61 个可能值都可以达到时你可以停止）？选项的数量不是太多。
一个可能的优化：如果你需要回答多个查询（比如给定一个字符串，找到一个长度为3且哈希函数值相同的字符串），你可以生成所有长度为3的字符串并计算它们的哈希值一次建地图hash -> a string of length 3 with this hash。一旦你有了这张地图，找到一个长度为 3 且与给定字符串具有相同散列的字符串只是一次地图查找。
我有一个字符串 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 的字符串（聪明的东西）？我想到的唯一方法是计算 anna 的 k，即 29，然后以某种方式想到另一个长度为 3 的字符串，它给出 29.
你为什么不简单地生成所有长度为 3 的字符串并计算它们的哈希值（事实上，当哈希函数的所有 61 个可能值都可以达到时你可以停止）？选项的数量不是太多。
一个可能的优化：如果你需要回答多个查询（比如给定一个字符串，找到一个长度为3且哈希函数值相同的字符串），你可以生成所有长度为3的字符串并计算它们的哈希值一次建地图hash -> a string of length 3 with this hash。一旦你有了这张地图，找到一个长度为 3 且与给定字符串具有相同散列的字符串只是一次地图查找。