Help using Horner rules and hash functions in Java?

Question

I am trying to use Horner's rule to convert words to integers. I understand how this works, and for how long the word is, it can lead to 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 might "apply the mod statement after evaluating each expression in brackets in the Horner rule". I don’t quite understand what this means. Let's say the expression looks like this:

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

I take mod tableSize after each expression in brackets and add them together? What would it look like with this hash function and this example Horner rule?

Answer 1

The book says that 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 

Is equivalent

  _ _ _ _ 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 main subtraction, you replace it with an “extended” version, in which mod operands and mod results. Since the operands for basic multiplication are now in the range 0..m-1 , the largest number you get is (m-1)^2 , which can facilitate 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 noted that 32 is a terrible choice of factor for the hash functions of this class (since it is not simple), especially for calculation (since it has degree 2). Much better than 31 because:

• It is simple (mathematically important!)
• This one is less than two, so it can be optimized for a cheaper shift and subtracted
  • 31 * i == (i << 5) - i

Answer 2

They mean replacing the result of the expression in parentheses with the following result: mod tableSize:

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

Answer 3

This is easier to understand with Java code. We must apply the modulo operator at each step of the calculation inside the loop:

 public static int hashCode(String key) { int hashVal = 0; for (int j = 0; j < key.length(); j++) { // For small letters. int letter = key.charAt(j) - 96; hashVal = (hashVal * 32 + letter) % arraySize; // mod } return hashVal; }