skip to content

Beyond correctness, what makes a hashCode() implementation 'good', and why does it matter for HashMap performance?

level: seniorimportance: should knowfreq 55%

answer

  1. Correct != good: return 0 is correct but awful
  2. Good spread -> O(1); clustering -> O(n)
  3. 31*result + field, order-sensitive, odd prime
  4. HashMap spreads high bits down (h ^ h>>>16)
  5. Java 8 treeifies long buckets to O(log n)
  6. Predictable hash -> hash-flooding DoS

basics

~20 s

A correct hashCode just needs equal objects to share a code. A good one also spreads unequal objects across many different codes, so HashMap buckets stay small and lookups stay fast. A poor spread piles items into few buckets and slows lookups.

solid answer

~50 s

Correctness and quality are separate. The contract only forces equal objects to share a code; a hashCode that returns a constant is technically *correct* yet terrible — every entry lands in one bucket, so HashMap degenerates toward O(n) (or O(log n) once Java 8+ treeifies long buckets). A *good* hashCode distributes unequal objects uniformly across the int range and uses all the equals-relevant fields, so HashMap's bucket mapping spreads entries evenly and lookups stay near O(1). The classic idiom multiplies an accumulator by an odd prime (31) per field — `result = 31*result + fieldHash` — which makes the result order-sensitive and reduces collisions; `Objects.hash(...)` does this for you. HashMap further applies an internal spreading function to mix high bits down. Distribution quality also has a security dimension: predictable, easily-collided hashes enable hash-flooding denial-of-service, which is why some keyed structures randomize their hashing.

code

java · 16 lines
java
// Bad-but-legal: contract-compliant, performance disaster
@Override public int hashCode() { return 1; }   // all keys -> one bucket

// Classic good idiom (order-sensitive, odd-prime fold)
@Override public int hashCode() {
    int result = 17;
    result = 31 * result + Integer.hashCode(x);
    result = 31 * result + Integer.hashCode(y);
    result = 31 * result + (name == null ? 0 : name.hashCode());
    return result;
}

// Idiomatic equivalent
@Override public int hashCode() {
    return java.util.Objects.hash(x, y, name);
}

go deeper

for a junior

Knows a constant hashCode is legal but makes HashMap slow, and that a good hashCode spreads objects out.

for a middle

Explains the O(1) vs O(n) bucket effect, uses Objects.hash or the 31-multiplier idiom, and includes all equals fields.

for a senior

Connects distribution to HashMap internals (power-of-two table, bitmask index, the high-bit spread function, Java 8 treeification) and reasons about order-sensitivity and field selection.

for a principal

Adds the adversarial view — hash-flooding DoS from predictable hashes, randomized hashing trade-offs — and weighs caching hashCode for hot immutable keys against memory and code complexity.

## Correctness vs. quality The hashCode **contract** is a *correctness* floor: equal objects share a code, codes are consistent within a run, collisions are allowed. **Quality** is a separate, performance concern: *how well* the codes spread unequal objects. A method like `return 0;` (or `return 42;`) is fully **contract-compliant** yet **pathologically bad**, because it forces every key into a single bucket. ## How HashMap turns a code into a bucket A `HashMap` keeps an array (the *table*) whose length is a power of two. For a key it computes `h = key.hashCode()`, applies an internal **spread** (`h ^ (h >>> 16)`, mixing the high 16 bits into the low 16), then takes `index = spread(h) & (table.length - 1)` — a fast bitmask that keeps only the low bits. **Implication:** only the *low* bits of your hashCode select the bucket initially, so a hashCode whose entropy lives only in high bits would collide heavily without that spread step — the JDK's `hash()` exists precisely to mitigate weak hashCodes. ## Why distribution governs speed - If codes are well spread, each bucket holds ~1 entry and `get`/`put` are **O(1)** average. - If many keys share a bucket, that bucket becomes a list that must be scanned with `equals`, pushing toward **O(n)**. - Since Java 8, once a single bucket exceeds a threshold (8 entries, table ≥ 64) it is **treeified** into a balanced (red-black) tree, capping that bucket's lookup at **O(log n)** — a safety net for bad hashCodes and hash-flooding, *not* a license to write poor ones (treeification requires the keys be `Comparable`, or it falls back). ## What a good implementation looks like 1. **Use all and only the equals-relevant fields.** Omitting a distinguishing field raises collisions; including a field equals ignores can violate the contract. 2. **Combine fields order-sensitively with an odd prime.** The textbook idiom: `int result = 17; result = 31*result + a; result = 31*result + b;`. 31 is odd and prime, the multiply is cheap (`31*x == (x<<5) - x`), and being order-sensitive distinguishes objects with the same fields in different roles (e.g. `(x=1,y=2)` vs `(x=2,y=1)`). 3. **In practice, call `Objects.hash(f1, f2, ...)`** (which boxes into an array and applies the same 31-based fold) for clarity, or let a **record** generate it. For a single field, delegate to that field's own `hashCode`. 4. **Consider caching for immutable types.** If hashCode is expensive and the object is immutable (e.g. `String` does this), compute it lazily once and store it. ## The collision allowance is not an excuse The contract *permits* collisions, but every avoidable collision costs lookup time. So 'collisions allowed' is a correctness statement, while 'minimize collisions' is the quality goal you optimize toward. ## Security: hash-flooding If an attacker can submit keys (e.g. HTTP parameters parsed into a `HashMap`) and your hashCode is predictable, they can craft thousands of distinct keys that all collide into one bucket, turning O(1) into O(n) and causing a **denial-of-service** (algorithmic complexity attack). Mitigations include treeified buckets (Java 8+) and, for some structures, randomized/seeded hashing. This is why a 'good' hashCode in adversarial contexts means both well-distributed *and* hard to predict.

  • Why is 31 the conventional multiplier?
    It is an odd prime, which avoids information loss that even multipliers cause (they push bits toward zero), and JITs/compilers can compute 31*x as (x<<5)-x, making it cheap. Other odd primes work too; 31 is just the well-known convention from String and Effective Java.
  • Does the Java 8 bucket treeification make a bad hashCode harmless?
    No. Treeification caps a single overloaded bucket at O(log n) and requires keys to be Comparable to be effective, but it is a safety net, not a substitute. A poorly distributed hashCode still wastes memory, triggers treeification overhead, and may not treeify if keys aren't Comparable.

Think of buckets as checkout lanes. A correct-but-bad hashCode sends every shopper to lane 1 (one giant queue). A good hashCode is a greeter who evenly directs shoppers across all lanes, keeping each line short — fast for everyone.

saying these in an interview costs you the question

  • Treating 'collisions are allowed' as license to ignore distribution
  • Returning a constant or a single mutable field's value
  • Believing HashMap is always O(1) regardless of hashCode quality
  • Thinking treeification removes the need for a good hashCode
  • Ignoring the hash-flooding DoS angle for attacker-supplied keys

context

resolving links…