Introduction

The documented formula for String.hashCode() can look different from the loop used in the actual implementation, but they are mathematically the same. The reason is that the implementation evaluates the documented polynomial with Horner's method, which is a standard way to compute a polynomial efficiently.

The Documented Formula

The Java documentation defines the hash code of a string s of length n as:

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

using int arithmetic.

Two details matter:

• 's[i] is the numeric value of the ith UTF-16 code unit'
• "using int arithmetic" means overflow is intentional and part of the definition

So the documentation does not describe an idealized infinite-precision formula. It describes exactly what Java should compute with 32-bit signed integer arithmetic.

The Implementation Form

The implementation is typically equivalent to this:

1public int hashCode() {
2    int h = 0;
3    for (int i = 0; i < value.length; i++) {
4        h = 31 * h + value[i];
5    }
6    return h;
7}

At first glance, this looks different from the documented sum of powers of 31. It is the same computation written in iterative form.

Why They Are Equal

Expand the loop one step at a time.

After processing the first character:

h = s[0]

After processing the second character:

h = 31 * s[0] + s[1]

After the third character:

h = 31 * (31 * s[0] + s[1]) + s[2]
  = s[0] * 31^2 + s[1] * 31 + s[2]

After the fourth character:

h = 31 * (s[0] * 31^2 + s[1] * 31 + s[2]) + s[3]
  = s[0] * 31^3 + s[1] * 31^2 + s[2] * 31 + s[3]

The pattern is now clear. After processing all n characters, the loop has produced:

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

That is exactly the documented formula.

Short Inductive Proof

You can state the proof formally by induction.

Induction claim: after processing the first k characters, h equals:

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

Base case, k = 1:

h = 31 * 0 + s[0] = s[0]

So the claim holds.

Inductive step:

Assume it holds for k. On the next iteration:

h_new = 31 * h + s[k]

Substitute the induction hypothesis for h:

h_new =
31 * (s[0] * 31^(k-1) + s[1] * 31^(k-2) + ... + s[k-1]) + s[k]

Distributing 31 shifts every exponent up by one, yielding exactly the formula for k + 1 characters. Therefore the claim holds for all k, including k = n.

Example with a Real String

Take "abc". Using character values 97, 98, and 99:

Documented formula:

97 * 31^2 + 98 * 31 + 99

Implementation loop:

1h = 0
2h = 31 * 0 + 97 = 97
3h = 31 * 97 + 98 = 3105
4h = 31 * 3105 + 99 = 96354

Direct calculation:

97 * 961 + 98 * 31 + 99 = 96354

Same result.

Common Pitfalls

The biggest mistake is reading ^ in the documentation as Java's XOR operator. In the documentation, ^ means mathematical exponentiation, not Java syntax.

Another common issue is forgetting the "using int arithmetic" part. Overflow is not a bug here; it is part of the specified behavior and helps explain why the implementation does not need special overflow handling.

Some explanations also say the loop is only an optimization. That is true, but incomplete. It is not merely a fast approximation. It is algebraically identical to the documented formula.

Finally, remember that String hashing works on UTF-16 code units, not abstract Unicode characters as users might think of them visually.

Summary

• The documentation describes a polynomial in powers of 31.
• The implementation computes the same polynomial using Horner's method.
• A simple expansion or induction proof shows the two forms are identical.
• Overflow is expected because the specification explicitly uses int arithmetic.
• The loop is an exact implementation of the documented formula, not a different algorithm.