The labs on this site need JavaScript to run. The same content is written out below.

Learn › Java › Commonly used classes

equals and hashCode

Why can HashMap not find the key when you override only equals?

To treat two objects with the same contents as equal, you override equals. But before HashMap and HashSet call equals, they first use hashCode to decide which bucket to look in. So if you override only one of equals and hashCode, HashMap and HashSet cannot find an object that you meant to be equal.

Checked against real execution · The 12 combinations were run on JDK 21 and checked against the results

Concepts in this lab

equals and hashCode contract

This is the rule that two objects that are equal according to equals() must return the same hashCode() value. A HashMap or HashSet first uses the hash value to find the storage location and then compares with equals inside it, so if you override only equals, an object with the same contents cannot be found. For this reason, always override both methods together, based on the same fields.

Identity and equality

Identity means that two references point to the same object in memory, and you compare it with the == operator. Equality means that two objects logically have the same value, and you compare it with the equals() method. If you use == to compare strings or value objects, the result can be false even when the contents are the same.

Hash table and HashMap

This data structure decides the storage location (bucket) of a key from the value that a hash function produces for that key. The location can be computed directly from the key alone, so lookup, insertion, and removal are O(1) on average. Java's HashMap has this structure; it does not guarantee order and is not thread-safe.

Hash collision

This happens when different keys are assigned to the same bucket. It cannot be avoided because the number of buckets is finite. Java's HashMap links the entries of the same bucket in a linked list, and when too many entries gather in one bucket, it converts the list to a red-black tree to shorten the search time. More collisions mean lower performance, so hashCode must spread values evenly.

record

This is a syntax, which became a standard feature in Java 16, for compactly declaring a (shallowly) immutable class whose purpose is to hold data. You write only the list of fields, and the constructor, accessor methods, equals, hashCode, and toString are generated automatically. All fields are final, but if a field refers to a mutable object (such as a List), the contents of that object can change. It is used to define DTOs and value objects.

Try these

• Default settings — Only equals is overridden. equals is true, but getting the value from the map returns null.
• Both overridden — You can get the value with an object that has the same contents.
• Nothing overridden — The two are treated as different objects even though their contents are the same.
• Only hashCode overridden — The lookup reaches the same bucket, but equals is false, so the key is not found.
• Declared as a record — Both methods are generated for you automatically.
• hashCode always returns the same value — The contract is kept, but every object ends up in one bucket.

Running with the default settings

1. Two Order objects are created. The id of a is 1, and the id of b is 1. Their contents are the same, but in memory they are two different objects.
2. a.equals(b): The overridden equals compares the id values. They are 1 and 1, so the result is true.
3. Comparing hashCode: hashCode is not overridden, so the hashCode of Object is used. This value is determined separately for each object, so the values of a and b, which are different objects, are (almost always) different. Two objects for which equals is true now have different hashCode values. This breaks the contract that "equal objects must have equal hash codes".
4. map.put(a, "order details"): HashMap first uses a.hashCode() to decide which bucket (storage location) the entry goes into, and then puts the key a together with the value in that bucket.
5. map.get(b): First, b.hashCode() decides which bucket to look in. The hashCode is different from that of a, so the lookup usually goes to a different bucket, and even in the same bucket, a key whose hash value is different never reaches equals. equals is never even called, and null is returned. The value cannot be retrieved even though the two objects are equal according to equals.
6. set.add(a), set.add(b): HashSet uses a HashMap internally, so it decides in the same order. b is treated as a different element from a, so both are added. The size is 2. Objects with the same contents are now in the set as duplicates.

Result of this run

• If you override only equals, two objects that are equal according to equals go to different buckets. In a HashMap, a HashSet, or a cache that uses a HashMap, this becomes a bug in which you "put it in but cannot find it". When you override equals, override hashCode together with it, using the same fields.

Code

class Order {
    final int id;
    Order(int id) { this.id = id; }

    @Override
    public boolean equals(Object o) {
        return o instanceof Order other && id == other.id;
    }
}

Order a = new Order(1);
Order b = new Order(1);

System.out.println(a.equals(b));
System.out.println(a.hashCode() == b.hashCode());

Map<Order, String> map = new HashMap<>();
map.put(a, "order details");
System.out.println(map.get(b));

Set<Order> set = new HashSet<>();
set.add(a);
set.add(b);
System.out.println(set.size());

Assumptions of this model

The results of the 12 combinations (equals, whether the hashCode values are the same, map.get, and the size of set) were checked against the results of running the same code on JDK 21 on this PC. Saying that the values of two objects that do not override hashCode are "different" means that this is almost always the case. The hashCode of Object can also give the same value to different objects (this still does not break the contract), and in that case the key may be found, depending on the result of equals. Even within the same bucket, HashMap skips a key whose hashCode value is different, without calling equals. The specification does not define the exact value that the hashCode of a record returns, but it does guarantee that two records that are equal according to equals have the same hashCode.

Previous lab: == and equals · Next lab: String, StringBuilder