java - 帮助在 Java 中使用霍纳规则和散列函数？

Question

我正在尝试使用 Horner 规则将单词转换为整数。我明白它是如何工作的，如果这个词很长，它可能会导致溢出。我的最终目标是在散列函数 h(x)=x mod tableSize 中使用转换后的整数。我的书建议，由于溢出，您可以“在计算霍纳规则中每个带括号的表达式后应用 mod 运算符”。我不完全明白他们的意思。假设表达式看起来像这样:

((14*32+15)*32+20)*32+5

我是否在每个带括号的表达式后取 mod tableSize 并将它们加在一起？这个散列函数和霍纳规则的这个例子会是什么样子？

Answer 1

这本书说你应该利用这些数学等价物:

(a * b) mod m = ((a mod m) * (b mod m)) mod m
(a + b) mod m = ((a mod m) + (b mod m)) mod m

因此，

h = (((x*c) + y)*c + z) mod m

相当于

        _   _   _  _
h = (((x*c) + y)*c + z)

在哪里

  _
a * b = ((a mod m) * (b mod m)) mod m
  _
a + b = ((a mod m) + (b mod m)) mod m

本质上，对于每个基本加法和基本减法，您将其替换为 mod 的“高级”版本操作数，和 mod结果。由于基本乘法的操作数现在在 0..m-1 的范围内, 你会得到的最大数字是 (m-1)^2 ，如果 m 可以缓解溢出足够小。

另见

• Wikipedia:modular exponentiation
• Wikipedia:modulo operation
  • -1 mod 2 = 1数学上，但是 -1 % 2在 Java 中是 -1 .

---

顺便说一句，应该指出的是，32 是此类哈希函数的乘数选择(因为它不是质数)，尤其是对于计算(因为它是 2 的幂)。 31 更好，因为:

• 它是质数(在数学上很重要!)
• 它比二的幂小一，所以它可以优化为更便宜的移位和减法
  • 31 * i == (i << 5) - i