帮助在Java中使用Horner的规则和哈希函数?
发布时间:2020-12-14 06:05:05 所属栏目:Java 来源:网络整理
导读:我正在尝试使用Horner的规则将单词转换为整数.我理解它是如何工作的,如果这个词很长,它可能会导致溢出.我的最终目标是在散列函数h(x)= x mod tableSize中使用转换后的整数.我的书建议,由于溢出,你可以“在计算Horner规则中的每个带括号的表达式之后应用mod运
我正在尝试使用Horner的规则将单词转换为整数.我理解它是如何工作的,如果这个词很长,它可能会导致溢出.我的最终目标是在散列函数h(x)= x mod tableSize中使用转换后的整数.我的书建议,由于溢出,你可以“在计算Horner规则中的每个带括号的表达式之后应用mod运算符.”我并不完全明白这是什么意思.说表达式如下:
((14 * 32 15)* 32 20)* 32 5 我是否在每个带括号的表达式后使用mod tableSize并将它们一起添加?这个散列函数和Horner规则的例子会是什么样子? 解决方法
这本书说你应该利用这些数学等价:
(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 基本上,对于每个基本加法和基本减法,您可以用修改操作数的“高级”版本替换它,并修改结果.由于基本乘法的操作数现在在0..m-1的范围内,所以你得到的最大数字是(m-1)^ 2,如果m足够小,可以减轻溢出. 也可以看看 > Wikipedia:modular exponentiation > -1 mod 2 = 1数学,但Java中的-1%2为-1. 顺便说一句,应该指出的是32是这个类的哈希函数的乘数的一个可怕的选择(因为它不是素数),特别是对于计算(因为它是2的幂).更好的是31,因为: >这是主要的(在数学上很重要!) > 31 * i ==(i << 5) - i (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |