Help using Horner's rule and hash functions in Java?

Question

I am trying to use Horner's rule to convert words to integers. I understand how it works and how if the word is long, it may cause an overflow. My ultimate goal is to use the converted integer in a hash function h(x)=x mod tableSize. My book suggests, because of the overflow, you could "apply the mod operator after computing each parenthesized expression in Horner's rule." I don't exactly understand what they mean by this. Say the expression looks like this:

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

Do I take the mod tableSize after each parenthesized expression and add them together? What would it look like with this hash function and this example of Horner's rule?

Answer 1

The book is saying that you should take advantage of these mathematical equivalences:

(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

Is equivalent 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

Essentially, for each basic addition and basic subtraction, you replace it with an "advanced" version that mod the operands, and mod the results. Since operands to the basic multiplication are now in the range of 0..m-1, the biggest number you'll get is (m-1)^2, which can alleviate overflow if m is small enough.

See also

• Wikipedia:modular exponentiation
• Wikipedia:modulo operation
  • -1 mod 2 = 1 mathematically, but -1 % 2 in Java is -1.

---

By the way, it should be pointed out that 32 is a terrible choice of multiplier for hash functions of this class (since it's not a prime), especially for computing (since it's a power of 2). Much better is 31, because:

• It's prime (mathematically important!)
• It's one less than a power of two, so it can be optimized to a cheaper shift and subtract
  • 31 * i == (i << 5) - i