algorithm - 为什么 Rabin Karp 算法需要 2 个哈希函数用于模式字符串？（也适用于子字符串）

Question

例如，我们有 string1:"AB"，它必须在 string2:"CABA" 中找到。对于string1 h1=('A'*27 + 'B') and h2=('A'*29 + 'B')，对于string2我们计算hash1和hash2函数(h2.1='C'*27 + 'A', h2.2='C'*29 + 'C') 我们将结果与 string1 的哈希函数进行比较。

我不明白为什么我们需要 2 个哈希函数，每个字符串或子字符串都有不同的基数。

Answer 1

拥有两个不同的散列函数可以降低冲突的可能性，但是具有一个散列函数的版本也可以（我们并不总是需要第二个函数）。