Polynomial hash function - Horner's method for calculating Hash code

There are various ways of computing hash code for strings. A naive way is to add the ASCII values of all the characters of a String. Doing so would lead to many collisions. Another way is to multiply the ASCII values of all characters in a string.
String in java uses polynomial hashing technique to compute hash code. The primary advantage of a polynomial hash function is that the computed hash code retains information about all the characters of String and thus avoids collisions.
The polynomial hash function used in Java String implementation is
For a String of size n,

h(x) = s[0]*R^(n-1) + s[1]*R^(n-2) + ... + s[n - 1]*R + s[n]  

For a String "abcd" and R = 31,
h(x) = 97*31^3 + 98*31^2 + 99*31 + 100          ---------------------------- 1

Here R can be any prime number. The reason for using 31 is two fold.
Firstly, when we mod the resultant hash code with any other number, there are no common factors. Moding the hash code with array size is pretty common operation in a hash table.
Secondly, 31 is a Mersenne prime, a prime that's one less than a two power. Multiplying such a prime is very efficient on any processor as it involves two ops only a shift and subtract. For eg. 31 * n = n << 5 - n.

To evaluate a polynomial, Horner's method could be employed.

Horners polynomial evaluation:
hash = 0;
String str = "abcd";

for(char ch : str.toCharArray()) {
    hash = hash*31 + ch;
}

This results in the same value as the formula #1 above does.
iteration#1
hash = 0*31 + 97

iteration#2
hash = 31(97) + 98

iteration#3
hash = 31(97*31 + 98) + 99

iteration#4
hash = 31(97*31^2 + 98*31 + 99) + 100

         => 97*31^3 + 98*31^2 + 99*31 + 100   (same as formula#1 above)

Since java supports 32-bit integers, for larger strings, the above formula might lead to integer overflow and thus result in negative hash codes. So if the hash code needs to be used to put values into a hash table backed by an array, the sign bit needs to be discarded. This is achieved by (hash & 0x7FFFFFFF)
0x7FFFFFFF(2^31-1) is the Integer.MAX_VALUE in java.
&ing with MAX_VALUE retains all the bits except for the highest order bit(32nd bit), which is the sign bit. So the negative integer is changed to a positive one. This is much more efficient and correct compared Math.abs(). Math.abs() might return a negative value for Integer.MIN_VALUE.

Why are PrimeNumbers used for computing modular hash codes ?

One of the objectives of a hash function is to uniformly distribute keys among the available buckets and avoid collisions to the possible extent. While every hash function starts out with this objective, very few hash functions are able to achieve near uniform distribution. Collisions cannot be avoided but definitely can be minimized.
Modular hashing is a popular hashing technique for generating hash codes of positive integers. The hash code of a positive integer is calculated as h(x) = x%m where m is the number of buckets/slots available.

For m = 10 and an universe of first hundred positive integers(keys), h(x) would uniformly distribute the keys to the available 10 buckets.

The data is uniformly distributed across 10 buckets with 10 keys each.
Real world data is seldom uniformly distributed. Data is usually biased or skewed. In such cases, this hash function doesn't uniformly distribute the data. A good hash function uniformly distributes any type of data.

Now assume that the data is skewed and the data primarily consists of multiples of 5. The modular hash function h(x) does a poor job of distributing the data.

Buckets 0 and 5 have bulk of the data while other buckets are largely empty. Why so ? The multiples of 5 and m have a common factor in 5 and so many of them hashed to bucket#5. The other multiples of 5 which are also multiples of 10 hashed to bucket#0. This is unavoidable. The multiples of m will hash to bucket#0 for any value of m.
(it would be interesting to perform the same exercise for m = 12 and keys that are multiples of 3)
In order to make the distribution more uniform, we need to reduce the number common factors between m and the keys. How do we do so ? by choosing a m, which is prime.

Now lets use the same hash function with a m value that's prime. h(x) = x%m m = 7. I chose 7 as its the nearest prime that's less than 10. 11 is also a good choice, but the number of buckets would be more.

For m = 7, the data is almost uniformly distributed.

Now for the same h(x), m = 7 and universe of first 100 positive integers, assume that the data is skewed towards multiples of 3.

Again h(x) does a good job of distributing the multiples of three.

In conclusion, the distribution of data depends both on h(x), m and the data. Since the input data can be skewed or non-uniformly distributed, we need to work on our hash function and m in order to achieve a uniform distribution among available buckets. In the above examples, I have played around with value of m to achieve a near uniform distribution of data. While 7 is not the best prime number to distribute the keys uniformly, it suffices this particular use case.
Finally, why prime numbers ? Every key that has a common factor with m, will hash to that common factor, thus skewing our distribution of keys. The number of common factors a key can have with m can be reduced by picking a m that's prime.









References:
1. http://cs.stackexchange.com/questions/11029/why-is-it-best-to-use-a-prime-number-as-a-mod-in-a-hashing-function
2. http://algs4.cs.princeton.edu/34hash/