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

Java's String hashCode() Mystery: Why the Multiplier of 31?

Java's hashCode() method for strings is a fundamental aspect of their efficient storage and retrieval in data structures. By combining the characters of a string in a specific formula, it produces an integer that represents the string's unique identity. However, the choice of the multiplier 31 in this formula sparks questions.

Why 31 as the Multiplier?

The Java documentation indicates that a relatively large prime number should be used as a multiplier to avoid hash collisions and achieve uniform distribution. However, why not 29, 37, or 97 instead of 31?

Reason 1: Odd Prime

According to Joshua Bloch's "Effective Java," the choice of 31 stems from its being an odd prime. Using an even number could result in information loss if multiplication overflowed, as multiplying by 2 is equivalent to shifting.

Reason 2: Performance Optimization

An interesting property of 31 is that multiplication by it can be efficiently replaced by a shift and a subtraction: 31 * i == (i << 5) - i. Modern virtual machines often perform this optimization automatically, improving the performance of the hashCode() computation.

Importance of Primeness

While less evident, the use of a prime number also has benefits. Prime numbers distribute values more evenly, reducing the likelihood of hash collisions compared to non-prime multipliers. This enhances the ability to distinguish unique strings and maintain consistent retrieval performance.

Therefore, the multiplier of 31 in Java's String hashCode() method is not an arbitrary choice but a result of its optimization, efficiency, and collision avoidance properties, making it an effective value for identifying and managing string objects.

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!