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

Question

这个问题与rolling-hash非常相似, 但有一些关于溢出/负面结果的细节我仍然不清楚。

我也检查了这个 Rabin-Karp implementation并且对下面的行有问题:

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

First question:

if we always add Q, a large prime, can this result with negative number due to overflow ? If not, why not ? If yes, shouldn't this addition be done only if result is negative ?

通常选择素数 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不溢出，上面的表达式就没问题。

Second question:

If, for a moment, we didn't care about negative numbers, would it be correct to write expression bellow ?

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

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

Third question, this part confuses me most:

Lets assume that the overflow cannot happen when we add Q. Why is there left-most % Q operation over the leading digit ?

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。

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