帮助在Java中使用Horner的规则和哈希函数？

Question

我正在尝试使用Horner的规则将单词转换为整数.我理解它是如何工作的,如果这个词很长,它可能会导致溢出.我的最终目标是在散列函数h(x)= x mod tableSize中使用转换后的整数.我的书建议,由于溢出,你可以"在计算Horner规则中的每个带括号的表达式之后应用mod运算符." 我并不完全明白这是什么意思.说表达式如下:

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

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

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足够小,可以缓解溢出.

也可以看看

• 维基百科:模幂运算
• 维基百科:模数运算
  • -1 mod 2 = 1数学上,但-1 % 2在Java中-1.

顺便说一句,应该指出的是32是这个类的哈希函数的乘数的一个可怕的选择(因为它不是素数),特别是对于计算(因为它是2的幂).更好的是31,因为:

• 这是主要的(数学上很重要!)
• 它比一个2的幂小一个,所以它可以优化到更便宜的移位和减去
  • 31 * i == (i << 5) - i

Answer 2

它们的意思是用结果 mod tableSize 替换括号表达式的结果：

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