skip to content

How do you implement hashCode() by hand, and why is the multiplier 31 used in the classic formula?

level: middleimportance: should knowfreq 60%

answer

  1. result = 31 * result + fieldHash, seeded non-zero
  2. 31 is an odd prime → good bit distribution, no info loss
  3. 31 * i == (i << 5) - i (strength reduction)
  4. long: high XOR low 32 bits; arrays: Arrays.hashCode
  5. prefer Objects.hash(...); same fields as equals

basics

~20 s

Start with a number, then for each field do result = 31 * result + fieldHash. The 31 mixes the fields so different objects spread out across buckets. Today you usually just write Objects.hash(field1, field2, ...) instead of doing it by hand.

solid answer

~50 s

The classic manual formula starts with a non-zero seed and folds in each significant field: result = 31 * result + c, where c is that field's hash contribution. For an int use the value itself; for long use (int)(v ^ (v >>> 32)); for boolean use v ? 1 : 0; for object fields use Objects.hashCode(field) (null-safe); for double use Double.hashCode; for arrays use Arrays.hashCode. The multiplier 31 is an odd prime, which helps distribute hashes and avoids the information loss an even multiplier causes (multiplying by an even number shifts bits left, eventually discarding high bits). 31 was also chosen because 31 * i == (i << 5) - i, an optimization the JVM can apply. The exact constant matters less than mixing field hashes order-dependently so that, e.g., {a,b} and {b,a} differ. In practice prefer Objects.hash(...), which does exactly this internally; use the manual loop only on a hot path where avoiding the varargs array allocation matters. Use the same fields as equals.

code

java · 12 lines
java
// Modern, preferred:
@Override public int hashCode() {
    return Objects.hash(name, age, height);
}

// Equivalent manual loop (hot-path, no varargs array):
@Override public int hashCode() {
    int result = Objects.hashCode(name);
    result = 31 * result + Integer.hashCode(age);
    result = 31 * result + Double.hashCode(height);
    return result;
}

go deeper

for a junior

Knows hashCode must be overridden with equals and can use Objects.hash(...) to produce it.

for a middle

Can write the manual 31*result+field loop, handle long/double/array fields correctly, and knows equal objects must share a hash code.

for a senior

Explains why 31 (odd prime, distribution, (i<<5)-i), the long-folding and array hazards, and when the manual loop beats Objects.hash on a hot path.

for a principal

Drives conventions (records/generated hashCode), reasons about hash distribution quality and collision behaviour under load, and audits for mutable-field-in-hashCode hazards across the codebase.

## Why hashCode exists `hashCode()` returns an `int` that hash-based collections (`HashMap`, `HashSet`) use to pick a bucket. The contract: **equal objects must return equal hash codes** (so a key can be found again), unequal objects *may* collide, and the value must be consistent during the object's life (given the equality fields don't change). ## The classic manual recipe (Effective Java, Item 11) ```java @Override public int hashCode() { int result = 17; // non-zero seed result = 31 * result + Integer.hashCode(age); // int field result = 31 * result + Objects.hashCode(name); // object field (null-safe) result = 31 * result + Long.hashCode(id); // long field result = 31 * result + Double.hashCode(height); // double field result = 31 * result + Arrays.hashCode(tags); // array field return result; } ``` Field-type contributions: - **int / short / byte / char**: the value (`Integer.hashCode(v)` is just `v`). - **long**: `(int)(v ^ (v >>> 32))` — XOR the high 32 bits into the low 32 so both halves matter (`Long.hashCode` does this). - **boolean**: `v ? 1 : 0`. - **float**: `Float.floatToIntBits(v)` (`Float.hashCode`). - **double**: `Double.hashCode(v)`, which bit-converts then folds the long. - **object reference**: `Objects.hashCode(field)` — returns 0 for null, else `field.hashCode()` (null-safe). - **array**: `Arrays.hashCode(arr)` (or `Arrays.deepHashCode` for nested). The array's own hashCode is identity-based, so you must use the helper. ## Why 31? Several reasons, in priority order: 1. **Odd prime — good distribution.** Multiplying by an *odd* number is important: if the multiplier were even, the multiply shifts bits to the left and the low bits become 0, so over many fields you lose information (high bits fall off the top, low bits become predictable). An odd multiplier keeps the result invertible and spreads bits. Being **prime** historically helps avoid patterns when the table size shares factors with the multiplier. 2. **Order sensitivity.** Because each step does `31 * result + field`, the *position* of a field affects the result, so `(a, b)` and `(b, a)` hash differently — useful for things like strings where order matters. 3. **Cheap to compute.** `31 * i` equals `(i << 5) - i` (shift-and-subtract), so even on hardware with slow multiplication the JIT can strength-reduce it. This is a historical micro-optimization; modern CPUs multiply fast. The **exact** constant is not magic — any small odd value would work; 31 is conventional (it is what `String.hashCode` uses). ## Prefer Objects.hash in modern code ```java @Override public int hashCode() { return Objects.hash(age, name, id, height); } ``` `Objects.hash(...)` runs the same `31 *` loop over its varargs. It allocates a small array for the varargs each call, so on a measured hot path the manual loop (no allocation) can be worth it — otherwise prefer the one-liner for clarity. **For a single field, use `field.hashCode()` directly, not `Objects.hash(field)`** (avoids the array). ## The cardinal rule: same fields as equals hashCode must be derived from **exactly the fields equals compares**. If equals uses x and y, hashCode must too — otherwise two equal objects can get different hash codes and one becomes unfindable in a HashMap.

  • Is it legal for hashCode() to always return 0?
    Yes, it satisfies the contract (equal objects still share the hash), but it is terrible for performance: every object lands in one bucket, turning HashMap lookups from O(1) into O(n) (a single bucket's chain/tree). It is correct but defeats the point of hashing.
  • Why XOR the two halves of a long instead of just casting it to int?
    A plain (int) cast keeps only the low 32 bits, so two longs differing only in their high bits would hash identically. (int)(v ^ (v >>> 32)) folds the high 32 bits into the low ones so all 64 bits influence the result.

saying these in an interview costs you the question

  • Saying 31 makes hashes unique — it does not; collisions are allowed and expected
  • Returning a constant like 0 from hashCode (legal but degrades HashMap to a linked list)
  • Using a different field set in hashCode than in equals
  • Using == or raw hashCode() on an array field instead of Arrays.hashCode
  • Calling field.hashCode() on a possibly-null object field instead of Objects.hashCode

context

resolving links…