滚动哈希溢出/负结果保护

Question

这个问题与rolling-hash非常相似，但是关于溢出/否定结果的一些细节对我来说仍然不清楚。我也检查了这个 Rabin-Karp实现，并且对下面的行有疑问：txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;我了解以下表达式可能会给出否定结果：txtHash - RM*txt.charAt(i-M)第一个问题：如果我们总是添加 Q，一个大素数，这个结果是否会由于溢出而导致负数？如果不是，为什么不呢？如果是，是否应该仅在结果为负时才进行此添加？第二个问题：如果我们暂时不关心负数，写下面的表达式是否正确？txtHash = (txtHash - RM*txt.charAt(i-M)) % Q;第三个问题，这部分最让我困惑：让我们假设当我们添加 Q 时不会发生溢出。为什么在前导数字上有最左边的 % Q 操作？txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q ) % Q;我已经阅读了我链接的答案，并根据 Aneesh 的答案，如果我理解正确，下面的表达式应该是相似的：hash = hash - ((5 % p)*(10^2 %p) %p)txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;但我不明白为什么它们相似，因为在哈希示例中，% p 不是针对先前的哈希值计算的，但是对于 txtHash，我们也计算了先前哈希的 % Q。

Answer 1

第一个问题：

如果我们总是添加 Q，一个大素数，这个结果是否会由于溢出而导致负数？如果不是，为什么不呢？如果是，是否应该仅在结果为负时才进行此添加？

通常选择质数 Q 以使 2Q 仍然不会溢出类型。

现在让我们看看。

• txtHash是从 0 到 Q - 1。

• RM*txt.charAt(i-M)很大。

• RM*txt.charAt(i-M) % Q是从 0 到 Q - 1。

• txtHash - RM*txt.charAt(i-M) % Q是从 -(Q - 1) 到 Q - 1。

• txtHash + Q - RM*txt.charAt(i-M) % Q是从 1 到 2Q - 1。

所以，只要 2Q - 1 不溢出，上面的表达式就可以了。

第二个问题：

如果我们暂时不关心负数，写下面的表达式是否正确？

txtHash = (txtHash - RM*txt.charAt(i-M)) % Q;

是的，如果% Q总是给出从 0 到 Q-1 的结果（例如在 Python 中），上面的表达式就可以了。

第三个问题，这部分最让我困惑：

让我们假设当我们添加 Q 时不会发生溢出。为什么在前导数字上有最左边的 % Q 操作？

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q ) % Q;

假设我们删除最左边的% Q. 然后让我们再次估计：

• txtHash是从 0 到 Q - 1。

• RM*txt.charAt(i-M)很大。

• 多大？从 0 到 (Q - 1) * CharCode。

• txtHash - RM*txt.charAt(i-M)是从 -(Q - 1) * (CharCode - 1) 到 Q - 1。

• txtHash + Q - RM*txt.charAt(i-M)从 -(Q - 1) * (CharCode - 2) 到 2Q - 1。

仍然可能是负面的。不是我们想要的。