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

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

In Java, the hashCode() method for String objects employs the following formula:

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

where s[i] is the ith character, n is the string length, and ^ denotes exponentiation. This raises the question: why is 31 specifically chosen as the multiplier?

Rationale for a Prime Multiplier

The documentation suggests using a relatively large prime number as the multiplier to minimize collisions in hash tables. Collisions occur when distinct objects produce the same hash code, potentially leading to performance issues. Prime numbers offer a better distribution of hash codes, reducing the likelihood of collisions.

Why Not Other Primes?

The selection of 31 among other primes is attributed to two factors:

1. Overflow Prevention: If the multiplier were even and the multiplication overflowed, information would be lost. This is because multiplying by 2 is equivalent to a shift operation.
2. Performance Optimization: The value 31 allows for an optimization where multiplication can be replaced by a shift and subtraction: 31 * i == (i << 5) - i. Modern virtual machines perform this optimization automatically.

Therefore, 31 satisfies both criteria of being a prime number to prevent collisions while enabling efficient hashing operations for String objects in Java.

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