Keys, equals and hashCode
A hash-based collection finds an element in two steps: it computes the hash code to choose a bucket, and it compares the candidates in that bucket with equals. Both methods come from the key, so a key whose hash code changes after it was stored is in a bucket nobody looks in again. The map is not broken and the entry was not deleted: it is simply unreachable, and the program below shows it.
A mutable key disappears
Key has one field and a correct pair of overrides built from it. The program puts a value with one key, reads it back, changes the field and reads it again:
import java.util.HashMap;
import java.util.Map;
public class MutableKey {
public static void main(String[] args) {
Map<Key, String> map = new HashMap<>();
Key key = new Key("one");
map.put(key, "first value");
System.out.println(map.get(key));
key.name = "two";
System.out.println(map.get(key));
System.out.println(map.containsKey(new Key("one")));
System.out.println(map.size());
System.out.println(map.containsValue("first value"));
}
}
class Key {
String name;
Key(String name) {
this.name = name;
}
@Override
public boolean equals(Object other) {
return other instanceof Key key && name.equals(key.name);
}
@Override
public int hashCode() {
return name.hashCode();
}
@Override
public String toString() {
return "Key(" + name + ")";
}
}
javac -Xlint:all MutableKey.java
java MutableKey
first value
null
false
1
true
Why the lookup fails
The first read works. Then name changes, so hashCode answers a different number, and the second read looks in another bucket and finds nothing: the answer is null. Asking with a fresh key of the original name fails too, because the entry is filed under the old hash and the new key hashes differently.
The entry is still in the map. size() still counts it, containsValue still finds the value by walking every entry, and a loop over entrySet would print it. Only the lookup by key is broken, which is the whole operation a map exists for.
equals without hashCode
The other half of the contract is the pair itself. A class that overrides equals and leaves hashCode alone gets two objects that are equal and hash differently, and the compiler says so with -Xlint:all:
import java.util.HashSet;
import java.util.Set;
public class HashOnly {
public static void main(String[] args) {
Set<Item> set = new HashSet<>();
set.add(new Item(1));
System.out.println(set.contains(new Item(1)));
System.out.println(new Item(1).equals(new Item(1)));
System.out.println(new Item(1).hashCode() == new Item(1).hashCode());
}
}
class Item {
private final int id;
Item(int id) {
this.id = id;
}
@Override
public boolean equals(Object other) {
return other instanceof Item item && id == item.id;
}
@Override
public String toString() {
return "Item(" + id + ")";
}
}
javac -Xlint:all HashOnly.java
java HashOnly
HashOnly.java:14: warning: [overrides] Class Item overrides equals, but neither it nor any superclass overrides hashCode method
class Item {
^
1 warning
false
true
false
The three lines of output are the contradiction: the set does not find an equal object, while equals says the two are equal and the hash codes disagree. The warning names the class and the missing method, and it is one of the few that is always worth fixing, because the alternative is a collection that silently loses elements.
An immutable key
A record is the shortest correct key: its fields are final, and equals and hashCode are built from the same components, so neither can change after the key is stored. A new key with the same components finds the entry:
import java.util.HashMap;
import java.util.Map;
public class ImmutableKey {
public static void main(String[] args) {
Map<Key, String> map = new HashMap<>();
Key one = new Key("one");
Key two = new Key("two");
map.put(one, "first value");
map.put(two, "second value");
System.out.println(map.get(one));
System.out.println(map.get(new Key("one")));
map.remove(one);
System.out.println(map.size());
}
}
record Key(String name) {
}
javac -Xlint:all ImmutableKey.java
java ImmutableKey
first value
first value
1
The second line is the property a map promises: two keys with the same value find the same entry. The remove takes it out, and one entry is left. A record with an array component would need the defensive copy of lesson 042 before it could be a key, because the array behind it can still change.
Removing before changing
When the key has to be mutable, the rule is to remove it before the change and put it back after. The program does that with the same class as the first section, and the lookup by the new field works:
import java.util.HashMap;
import java.util.Map;
public class RemoveFirst {
public static void main(String[] args) {
Map<Key, String> map = new HashMap<>();
Key key = new Key("one");
map.put(key, "first value");
map.remove(key);
key.name = "two";
map.put(key, "first value");
System.out.println(map.get(new Key("two")));
System.out.println(map.size());
}
}
class Key {
String name;
Key(String name) {
this.name = name;
}
@Override
public boolean equals(Object other) {
return other instanceof Key key && name.equals(key.name);
}
@Override
public int hashCode() {
return name.hashCode();
}
}
javac -Xlint:all RemoveFirst.java
java RemoveFirst
first value
1
The workaround is honest but fragile: one caller who forgets the remove brings back the bug, and the code has to be read by everybody who touches the key. The fix that survives is the record above, or a key class with final fields and no setters, which is lesson 042 again. A key in a hash collection is a value, not a record of the program's change.
Exercises
- Add a hashCode to Item in HashOnly and run it again.
- Print the size of the map in MutableKey after a loop over entrySet and compare it with the lookup.
- Make Key final with final fields and remove the setter-style change.
- Use a String as the key of the same map and explain why no such bug is possible.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
How does a HashMap find a key?
Answer
It hashes the key to a bucket and compares the entries there with equals
The hash code chooses the bucket and equals decides among the candidates.
-
What happens when a key changes after it was stored?
Answer
Its hash code changes, so the entry is in a bucket the lookup no longer visits
Nothing re-files the entry, so it stays where the old hash put it.
-
Why must equals and hashCode agree?
Answer
Equal objects must have equal hash codes, or a hash collection cannot find them
A lookup goes through the hash first, so a disagreement hides the object.
-
What does this program print?
import java.util.HashMap; import java.util.Map; public class Q1 { public static void main(String[] args) { Map<String, Integer> map = new HashMap<>(); map.put("a", 1); String key = "a"; System.out.println(map.get(key)); System.out.println(map.get(new String("a"))); } }Answer
1 / 1
String implements equals and hashCode by value, so a new object with the same text is found.
-
What does this program print?
import java.util.HashSet; import java.util.Set; public class Q2 { public static void main(String[] args) { Set<Key> set = new HashSet<>(); Key key = new Key("a"); set.add(key); key.name = "b"; System.out.println(set.contains(new Key("b"))); System.out.println(set.size()); } } class Key { String name; Key(String name) { this.name = name; } public boolean equals(Object o) { return o instanceof Key k && name.equals(k.name); } public int hashCode() { return name.hashCode(); } }Answer
false / 1
The key was stored under the hash of a and is looked for under the hash of b.
-
What does this program print?
public class Q3 { public static void main(String[] args) { Key a = new Key("x"); Key b = new Key("x"); System.out.println(a.equals(b)); System.out.println(a == b); } } record Key(String name) { }Answer
true / false
The record compares the components, while == compares the references.
-
What does this program print?
import java.util.HashMap; import java.util.Map; public class Q4 { public static void main(String[] args) { Map<Key, String> map = new HashMap<>(); Key key = new Key("a"); map.put(key, "v"); map.remove(key); key.name = "b"; map.put(key, "v"); System.out.println(map.get(new Key("b"))); } } class Key { String name; Key(String name) { this.name = name; } public boolean equals(Object o) { return o instanceof Key k && name.equals(k.name); } public int hashCode() { return name.hashCode(); } }Answer
v
The remove before the change left no entry under the old hash, and the put filed the new one.
-
What does the
[overrides]warning name?Answer
A class that overrides equals but not hashCode
The warning is the compiler noticing the pair is incomplete, and it is right.
-
Why is a record a good map key?
Answer
Its fields are final and both methods are generated from them
A key that cannot change keeps its hash code, which is the property the map needs.
-
What still works after a key of a HashMap has changed?
Answer
size and containsValue, but not get or containsKey
The entry is still in the table; only the path by key is lost.
The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.
Article author: Arthur Isaev