current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 5 down vote favorite
2

This question already has an answer here:

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?

share|improve this question
2  
Check this answer: stackoverflow.com/questions/113511/hash-code-implementation –  NilsH Mar 20 '13 at 8:20
3  
And this stackoverflow.com/a/299748/305142 –  Serkan Arıkuşu Mar 20 '13 at 8:22
add comment

marked as duplicate by sp00m, Nikolay Kuznetsov, Sean Patrick Floyd, Vulcan, Tim Bender Mar 20 '13 at 8:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 1 down vote

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;
}
share|improve this answer
 
It seems curious that they were willing to change the hash code implementation in 1.2, but have not since been willing to add something like hashCode = (hash==0) ? count+1 : hash; so as to avoid having repeated calls to hashCode() take excessively long with certain strings. The existing implementation doesn't cause such slowdowns with many strings, but any string which ever causes the slow behavior will always cause it. –  supercat Jul 10 '13 at 0:04
 
@supercat: your approach would work if there is always only one string with the same content. Java mostly interns Strings, but you can still have two copies having the same characters. The hashCode method is supposed to be consistent with equals(), so your approach is not valid. It would e.g. break behaviour of HashMap and HashSet (contains, remove, etc. might fail when they shouldn't). –  Peter Becker Oct 16 '13 at 23:17
 
@PeterBecker: Perhaps I wasn't clear what I was proposing? Any particular sequence of characters would always return the same hash value under my proposal; the only change would be that strings which under the existing algorithm would hash to zero would yield to a value that depended upon the number of characters in the sequence (which would always be the same for any any particular sequence). What's problematical as it turns out isn't hash sets, but rather switch statements. If a string in a switch statement would hash to zero, such assumption will be hard-wired into the compiled code. –  supercat Oct 17 '13 at 15:00
 
@PeterBecker: Thus, a switch statement would assume any string which cached a hashCode value that wasn't zero could never trigger a switch statement for a string which under the old hashCode method would yield zero. There are other approaches which could be used to allow such strings' hash codes to be cached while still returning zero and without requiring extra fields, but they would slow down some other string operations. For example, one could specify that if count is -1, then the "real" count is stored in hash and the hashCode value should return as zero. –  supercat Oct 17 '13 at 15:03
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.