Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does Java's hashCode() in String use 31 as a multiplier?

Per the Java documentation, the hash code for a String object is computed as:

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

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation.

Why is 31 used as a multiplier?

I understand that the multiplier should be a relatively large prime number. So why not 29, or 37, or even 97?

like image 645
jacobko Avatar asked Nov 18 '08 16:11

jacobko


People also ask

Why does Java's hashCode in String use 31 as a multiplier?

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional.

Why does hashCode use prime number?

Within JDK String Class hashCode() method implementation This property of prime number makes it very suitable for use in hashing function so as to get fair distribution in its hashCode output and thus achieving low collisions.

What happens if hashCode for multiple keys is same?

When two unequal objects have the same hash value, this causes a collision in the hash table, because both objects want to be in the same slot (sometimes called a bucket).

What is the purpose of the hashCode () method?

The purpose of the hashCode() method is to provide a numeric representation of an object's contents so as to provide an alternate mechanism to loosely identify it. By default the hashCode() returns an integer that represents the internal memory address of the object.


1 Answers

According to Joshua Bloch's Effective Java (a book that can't be recommended enough, and which I bought thanks to continual mentions on stackoverflow):

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

(from Chapter 3, Item 9: Always override hashcode when you override equals, page 48)

like image 147
matt b Avatar answered Sep 29 '22 10:09

matt b