Why Does Java's String hashCode() Use 31 as the Multiplier?

Why Java's hashCode() in String Uses 31 as a Multiplier

In Java, the hash code for a String object is calculated using the formula:

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

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

The Importance of a Prime Multiplier

One key aspect of this formula is the use of a prime multiplier, in this case, 31. Using a prime number has the advantage of reducing the likelihood of hash collisions. If a non-prime multiplier were used, two strings with the same hash value could share a common factor, making it easier for hash collisions to occur.

Why Not Another Prime Number?

While 31 is an odd prime, there are other prime numbers that could have been chosen, such as 29, 37, or 97. The choice of 31 was based on a combination of factors:

• Avoiding Overflow: 31 is a relatively small prime, which reduces the risk of integer overflow during the multiplication process. If an even prime were used, overflow could occur when multiplying by 2, potentially losing information.
• Performance Optimization: As noted by Joshua Bloch in "Effective Java," the multiplication by 31 can be replaced by a more efficient shift-and-subtract operation: 31 * i == (i << 5) - i. This optimization is commonly performed by modern virtual machines for performance purposes.
• Tradition: Using a prime multiplier for hash functions is a long-standing practice, and 31 has been a particularly popular choice. While there is no definitive reason why 31 was specifically selected, it has become a standard choice in many programming languages and applications.

The above is the detailed content of Why Does Java's String hashCode() Use 31 as the Multiplier?. For more information, please follow other related articles on the PHP Chinese website!