This week's book giveaway is in the Java 8 forum.
We're giving away four copies of Java 8 in Action and have Raoul-Gabriel Urma, Mario Fusco, and Alan Mycroft on-line!
See this thread for details.
The moose likes Java in General and the fly likes Why is 31 taken in finding the hashCode of String? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Why is 31 taken in finding the hashCode of String?" Watch "Why is 31 taken in finding the hashCode of String?" New topic
Author

Why is 31 taken in finding the hashCode of String?

Avinash Haridasu
Ranch Hand

Joined: Jul 12, 2011
Posts: 31
/**
* Returns a hash code for this string. The hash code for a
* <code>String</code> object is computed as
* <blockquote><pre>
* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] // Line 1
* </pre></blockquote>
* using <code>int</code> arithmetic, where <code>s[i]</code> is the
* <i>i</i>th character of the string, <code>n</code> is the length of
* the string, and <code>^</code> indicates exponentiation.
* (The hash value of the empty string is zero.)
*
* @return a hash code value for this object.
*/

public int hashCode() {
int h = hash;
if (h == 0 && count > 0) {
int off = offset;
char val[] = value;
int len = count;

for (int i = 0; i < len; i++) {
h = 31*h + val[off++]; // Line: 2
}
hash = h;
}
return h;
}


From Line 1 and Line 2 of the above we can find that 31 is used in finding the hashCode() of a string.

But why is it only 31 ???
Wouter Oet
Saloon Keeper

Joined: Oct 25, 2008
Posts: 2700

I'm not exactly sure why but I'm pretty sure it has got something to do with the fact that it is a prime number.


"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." --- Martin Fowler
Please correct my English.
Jaikiran Pai
Marshal

Joined: Jul 20, 2005
Posts: 9336
    
110

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

[My Blog] [JavaRanch Journal]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36555
    
  16
It might be worth a look at the Joshua Bloch and Bruce Eckel links in this post.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36555
    
  16
That Wordpress article Jaikiran Pai quoted is better than my links.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Why is 31 taken in finding the hashCode of String?
 
Similar Threads
hashcode()...
Dan Chisholm's Topic Exam Q.5
Java String hashcode() base 31 computation
How hashCode() works?
Immutable - Hashcode() - lazy initialization.