给定一个使用模哈希函数的算法，这意味着大于某个给定整数的大数字将“环绕”，因此结果始终在 0 和给定整数之间。例如，Rabin-Karp 算法需要一个滚动哈希，并带有一个巧妙的模数。可能的最高模数是多少？为什么是这样？
问问题
54 次
1 回答
-1
要回答这个问题，重要的是检查模调用之间的“最大影响”操作是什么。这意味着，如果您期望一个数字最佳地乘以 97*101=9797，则必须将 2^(32) 除以 9797（来自 Rabin-Karp 示例），然后在该区域中寻找最接近的素数。例如，如果将 2600 添加到整数，则必须从 2^(32) 中减去 2600。如果对给定数字求平方，则必须从 2^(32) 等中取平方根。
然后，这将防止在操作之后和模调用之前发生任何溢出。因此，始终将散列数保持在 0 和所选素数之间。
因为您选择了一个（高）素数，所以哈希冲突的数量尽可能低。
于 2017-03-08T21:59:59.953 回答