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

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

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

是否在每个带括号的表达式之后加上mod tableSize并将它们加在一起?这个哈希函数和霍纳法则的例子看起来像什么?

参考方案

这本书说您应该利用这些数学等价形式:

(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,但是Java中的-1 % 2-1
  • 顺便说一句,应该指出,对于此类的哈希函数(因为它不是素数),尤其是对于计算(因为它是2的幂),乘数的糟糕选择(因为它不是素数)。更好的是31,因为:

  • 素数(数学上很重要!)
  • 比2的幂小1,因此可以优化为更便宜的平移和减法
  • 31 * i == (i << 5) - i
  • Java:正则表达式模式匹配器是否有大小限制? - java

    我的模式类似于OR:“word1 | word2 | word3”我大约有800个字。可能有问题吗? 参考方案 您仅受记忆和理智的限制。 :)

    Java:线程池如何将线程映射到可运行对象 - java

    试图绕过Java并发问题,并且很难理解线程池,线程以及它们正在执行的可运行“任务”之间的关系。如果我创建一个有10个线程的线程池,那么我是否必须将相同的任务传递给池中的每个线程,或者池化的线程实际上只是与任务无关的“工人无人机”可用于执行任何任务?无论哪种方式,Executor / ExecutorService如何将正确的任务分配给正确的线程? 参考方案 …

    JAVA:字节码和二进制有什么区别? - java

    java字节代码(已编译的语言,也称为目标代码)与机器代码(当前计算机的本机代码)之间有什么区别?我读过一些书,他们将字节码称为二进制指令,但我不知道为什么。 参考方案 字节码是独立于平台的,在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的,如果在Windows x86中编译,则它将仅在Win…

    java:继承 - java

    有哪些替代继承的方法? java大神给出的解决方案 有效的Java:偏重于继承而不是继承。 (这实际上也来自“四人帮”)。他提出的理由是,如果扩展类未明确设计为继承,则继承会引起很多不正常的副作用。例如,对super.someMethod()的任何调用都可以引导您通过未知代码的意外路径。取而代之的是,持有对本来应该扩展的类的引用,然后委托给它。这是与Eric…

    Java:BigInteger,如何通过OutputStream编写它 - java

    我想将BigInteger写入文件。做这个的最好方式是什么。当然,我想从输入流中读取(使用程序,而不是人工)。我必须使用ObjectOutputStream还是有更好的方法?目的是使用尽可能少的字节。谢谢马丁 参考方案 Java序列化(ObjectOutputStream / ObjectInputStream)是将对象序列化为八位字节序列的一种通用方法。但…