Help use Horner’s rules and hash functions in Java?

I'm trying to convert words to integers using Horner's rules I understand how it works. If the word is long, it may cause overflow My ultimate goal is to use the converted integer in the hash function H (x) = x mod tablesize My book suggests that due to overflow, you can "apply the mod operator after evaluating each bracketed expression in Horner's rule." I don't quite understand what this means The expression is as follows:

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

Do I use mod tablesize after each parenthesized expression and add them together? What would this example of hash function and Horner rule look like?

Solution

The book says you should use these mathematical equivalents:

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

Thus,

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

amount to

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

where?

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

Basically, for each basic addition and basic subtraction, you can replace it with an "advanced" version of the modified operand and modify the result Since the operand of the basic multiplication is now 0 M-1, so the maximum number you get is (m-1) ^ 2. If M is small enough, overflow can be reduced

You can also have a look

> Wikipedia:modular exponentiation > Wikipedia:modulo operation

>- 1 mod 2 = 1 math, but - 1% 2 in Java is - 1

By the way, it should be noted that 32 is a terrible choice for the multiplier of the hash function of this class (because it is not a prime), especially for calculation (because it is a power of 2) Better 31, because:

>This is the main (mathematically important!) > It is one smaller than a power of 2, so it can be optimized to cheaper shifts and subtractions

> 31 * i ==(i << 5) - i