What's behind the hashCode() method for String in Java? [duplicate]

Question

I've been investigating the hashCode() methods in java and found the one for String class strange. The source code is as follows:

public int hashCode() {     int h = hash;     if (h == 0 && value.length > 0) {         char val[] = value;          for (int i = 0; i < value.length; i++) {             h = 31 * h + val[i];         }         hash = h;     }     return h; } 

The code itself is quite straight forward. But I wonder what's the reason for calculating hash code this way?
Why choose 31?
Why start from 0 instead of value.length - 1?
Any guarantee that this would make hashcodes less possible to collide with each other?

Answer 1

Yes the probability of hashcode collision is very low as for example in case of String it depends upon the string value. If we are not creating any String with new operator then if the a new String has the same value that already present , then new String object is not created, it refers to the old value from heap and in this case only the value of hashCode will be same as expected.

The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

From Java 1.2, java.lang.String class implements its hashCode() using a product sum algorithm over the entire text of the string.[2] Given an instance s of the java.lang.String class, for example, would have a hash code h(s) defined by

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

where terms are summed using Java 32-bit int addition, s[i] denotes the ith character of the string, and n is the length of s.

For your reference in Apache Harmony the method hashCode is:

public int hashCode() {     if (hashCode == 0) {         int hash = 0, multiplier = 1;         for (int i = offset + count - 1; i >= offset; i--) {             hash += value[i] * multiplier;             int shifted = multiplier << 5;             multiplier = shifted - multiplier;         }         hashCode = hash;     }     return hashCode; }