equals, hashCode and identity

Every object has two notions of sameness: identity — is it the same object — and equality — does it represent the same value. == gives you the first. equals gives you the second, but only if the class defines it, and only if hashCode agrees. Get the pair wrong and a HashSet will hold two copies of the same thing, or fail to find one it definitely contains. This lesson is the contract, then the machinery behind it: how HashMap actually uses a hash, where the identity hash lives, and the sequence of events by which a map loses your object.

#The default is identity

Object.equals is this == other. Object.hashCode is derived from the object's identity. So a class that overrides neither treats every instance as unique, which is right for a Connection or a Thread and wrong for a Money, an OrderId or a Coordinate.

The identity hash is not the address. Objects move during garbage collection, so the JVM generates a random-ish number the first time hashCode() or System.identityHashCode() is called on an object and stores it in the object's mark word, the first eight bytes of the header, where it shares space with the lock state and the GC age. That is why the number in Object.toString()'s @1b6d3586 is stable for the object's life and meaningless as an address.

The cost is more than the one-time generation. Those mark-word bits are shared with the lock state, and a biased lock — the JVM's fast path for an object only ever locked by one thread — lives in the same place. Taking an identity hash permanently revokes biasing for that object. Hash an object and then synchronized on it, and it pays full locking cost for the rest of its life. It is a small effect, and it is the kind of thing that makes a hot path mysteriously slower after somebody added logging that printed the object.

#The contract

From the Object Javadoc, condensed:

• Reflexive: x.equals(x) is true.
• Symmetric: x.equals(y) ⇔ y.equals(x).
• Transitive: x.equals(y) and y.equals(z) ⇒ x.equals(z).
• Consistent: repeated calls return the same result while the objects are unchanged.
• x.equals(null) is false.
• If two objects are equal, they must have the same hashCode. The reverse is not required: unequal objects may share a hash.

That last rule is the one that breaks things, and the reason is in how the hash is used.

#Under the hood: what HashMap does with a hash

HashSet is a HashMap with the elements as keys, so one explanation covers both. A HashMap is an array of buckets (16 by default), each holding a chain of entries:

1. Spread. h = key.hashCode(); h ^= (h >>> 16). The top bits are folded into the bottom ones, because step 2 only looks at the bottom ones and a hashCode that varies only in its high bits (some Doubles, some generated hashes) would otherwise land every key in one bucket.
2. Index. bucket = (table.length - 1) & h. The table length is always a power of two, so this is a fast modulo.
3. Search the bucket. Walk the chain; for each entry, compare hash == entry.hash && (key == entry.key || key.equals(entry.key)). The stored hash is compared first because an int comparison is cheaper than equals; identity is tried before equals for the same reason.
4. Treeify. A bucket with more than 8 entries becomes a red-black tree (if the table has at least 64 buckets), ordered by hash and then by compareTo when the keys are Comparable, so a pathological hash degrades to O(log n) rather than O(n). This is why a HashMap under a hash-collision attack still answers.
5. Resize. When the entry count passes capacity × 0.75, the table doubles and every entry is re-bucketed by the same formula, which is a full pass over the map.

#What breaks when you override only equals

class Point {
    final int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
 
    @Override public boolean equals(Object o) {
        return o instanceof Point p && p.x == x && p.y == y;
    }
    // hashCode not overridden
}
 
Set<Point> visited = new HashSet<>();
visited.add(new Point(1, 2));
System.out.println(visited.contains(new Point(1, 2)));

The two points have identity-based hashes, land in different buckets, and equals is never consulted. The set now accepts a second Point(1, 2) as a new element. HashMap keys fail the same way — you put a value under one key and cannot get it back with an equal key. The reverse mistake, hashCode without equals, is quieter: equal-looking keys share a bucket and then fail the equals check, so the map still holds duplicates.

#Walkthrough: how a map loses your object

The other way to lose an object is to change its hash while it is inside. Trace it:

class Tag { String name; /* equals and hashCode over name */ }
 
Map<Tag, Integer> counts = new HashMap<>();
Tag t = new Tag("draft");
counts.put(t, 1);            // hash("draft") → bucket 9
t.name = "final";            // the object's hash is now hash("final") → bucket 3
counts.get(t);               // looks in bucket 3: null
counts.containsKey(t);       // false
counts.size();               // 1 — it is still in bucket 9, unreachable by key
counts.put(t, 2);            // inserts a SECOND entry in bucket 3; size is 2

1. put computed the hash once and stored it in the entry alongside the key.
2. The mutation changed what t.hashCode() returns but not the stored hash in bucket 9.
3. Every lookup recomputes the hash, goes to bucket 3, finds nothing.
4. Iteration still visits the entry in bucket 9, so for (Tag k : counts.keySet()) shows a key the map claims not to contain.

A HashSet with a mutated element is the same story. The rule that follows: hash and compare only fields that do not change while the object can be in a collection, which for a key type means immutable fields, which for a value type means the whole class should be immutable. Making every hashed field final is how you get there by hand.

#A correct pair

@Override public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Point p)) return false;
    return x == p.x && y == p.y;
}
 
@Override public int hashCode() {
    return 31 * x + y;               // Objects.hash(x, y) reads better and costs more -- see below
}

Rules that keep it correct:

• Compare the same fields in both. Any field in equals may be in hashCode; no field in hashCode may be missing from equals.
• Use instanceof, not getClass(), unless subclasses must never be equal — and then think hard, because getClass() breaks equality with proxies (Hibernate, Spring) that subclass your class.
• Use only fields that do not change. See the walkthrough. Objects.hash(x, y) is the readable version and it is not free: it boxes each argument and allocates an Object[] to hold them. Measured over a million calls:

31*x + y         3.4 ms             0 bytes
Objects.hash    29.5 ms    55,995,904 bytes   ->  56 bytes/call

56 bytes is exactly an Object[2] (24) plus two Integers (16 each) — a number you can now derive. Use Objects.hash for readability in code that is not hot, and write the multiply by hand in a key type that sits in a map on a request path.

• Spread the hash. 31 * a + b is the traditional choice because 31 is odd, prime, and the JIT strength-reduces 31 * x to (x << 5) - x. javac does not — javap shows a plain imul; as the Bytecode and JIT lesson says, javac barely optimises and every real optimisation happens at run time. A hash that returns a constant is legal and makes every lookup a linear scan of one bucket, which is a real bug people ship "to be safe". Collisions are normal even with a good hash: "Aa".hashCode() and "BB".hashCode() are both 2112, which you can check in one line and which is why a bucket holds a chain rather than a value.
• Do not use Objects.hash in a hot path if profiling says so — it boxes every argument and allocates a varargs array per call.

Arrays.equals and Arrays.hashCode for array fields; Double.compare rather than == for doubles, so that NaN equals itself and -0.0 does not equal 0.0, matching Double.equals.

#What a later Java does for you

Writing this pair by hand is mechanical and it is easy to get subtly wrong — forget a field, use == on a double, forget that Arrays.equals exists for array fields. Later versions of Java add records, a class form whose equals, hashCode and toString are generated over all components, correctly, with the fields final. They are covered with the rest of what those releases added.

They are worth knowing about now for one reason: they tell you what "correct" looks like. A generated equals compares every component with that component's own equality — Double.compare for doubles, Arrays.equals for arrays — and the fields cannot change afterwards, which removes the mutable-key bug by construction rather than by discipline. That is the standard to write to by hand.

#Entities are different

A JPA entity has a database identity, a mutable state, and often no id until it is saved. Value-based equality is wrong for it — two Order rows with identical fields are two orders. Identity equality is wrong too, because the same row loaded in two sessions is two objects. The usual answer: equality by primary key when both have one, otherwise not equal; hashCode constant or based on the class, so it cannot change when the id is assigned. The Spring Data JPA course goes into this; the point here is that the "right" equals depends on what the class means.

#compareTo should agree

If a class is Comparable, compareTo returning 0 should mean equals returns true. TreeSet and TreeMap use compareTo alone — they never call equals or hashCode — so a comparator that considers two distinct objects equal makes the tree drop one of them. BigDecimal is the famous example: new BigDecimal("2.0").equals(new BigDecimal("2.00")) is false (different scale) but compareTo returns 0, so a HashSet holds both and a TreeSet holds one. HashMap's treeified buckets also fall back to compareTo for ordering, which is one more place an inconsistent pair surprises you.

#Try it yourself

class P {
    final int x, y;
    P(int x, int y) { this.x = x; this.y = y; }
    public boolean equals(Object o) { return o instanceof P && ((P) o).x == x && ((P) o).y == y; }
    public int hashCode() { return 31 * x + y; }
}
class Q { int x, y; Q(int x, int y) { this.x = x; this.y = y; } }
Set<Object> s = new HashSet<>();
s.add(new P(1, 1)); s.add(new P(1, 1));
s.add(new Q(1, 1)); s.add(new Q(1, 1));
s.add(new BigDecimal("1.0")); s.add(new BigDecimal("1.00"));
System.out.println(s.size());

class Money {
    final long paise; final String currency;
    @Override public boolean equals(Object o) { return o instanceof Money m && m.paise == paise; }
    @Override public int hashCode() { return Objects.hash(paise, currency); }
}

#Misconceptions

• "Different hash codes mean the objects are different, and equal hash codes mean they are equal." Only the first half holds, and only when the pair is correct. Equal hashes say nothing; a HashMap calls equals for exactly that reason.
• "hashCode returns the memory address." It returns a number stored in the object header, generated on first use, unrelated to the address, which changes when the collector moves the object.
• "A constant hashCode is safe." It is legal and it turns every hash-based collection holding that type into a linked list, then a tree. Safe is not the word.
• "equals alone is enough for a List." List.contains does use equals only — so a class with equals and no hashCode works in a List and fails silently in a HashSet or as a map key. The bug waits for the first refactor that changes the collection.
• "TreeSet and HashSet agree on membership." Only if compareTo and equals agree. BigDecimal shows they need not.

#Going deeper

• The Object.equals and Object.hashCode Javadoc: the contract, in the words the interviewer will quote.
• java.util.HashMap source: hash(), getNode(), treeifyBin(); readable, and the diagram above is its first fifty lines.
• Effective Java, items 10 and 11.
• java.util.Objects, the whole class: equals, hash, hashCode, requireNonNull — twenty lines of source that remove most of the boilerplate.
• Aleksey Shipilëv, "JVM Anatomy Quark #26: Identity hash code" for where the number lives.