Java HashMap
›Short versionOpen if you only have a minute.
- HashMap is the default map. get and put are constant time on average, and iteration order is unspecified.
- Equal keys must return the same hashCode. The code selects a bucket; equals finishes the match.
- A collision is two unequal keys in one bucket. A pile of collisions makes lookup linear.
- One null key is allowed. Null values are allowed, so get returning null is ambiguous without containsKey.
- Do not mutate a key’s equality fields after put. The entry stays in the old bucket and get misses it.
- Iterators are fail-fast. Put of a new key during a walk throws ConcurrentModificationException.
A is the map behind almost every “look this up by name” problem. The speed people quote — — depends on the .
String keys and boxed numbers already follow it. A class you wrote follows it only after both methods exist and stay stable. A here and there is expected. A mutable key is a bug.
Finding the key a second time
put hashes the key, picks a bucket, and either replaces an equal key’s value or appends a new entry. get repeats the hash and the equals checks. If hashCode changed in between, because of a , the second search walks a bucket that never held the entry.
A is the exception the table special-cases. You still get one slot, not a family of nulls. TreeMap will not give you that slot under natural ordering.
Replacing a value with put does not count as the kind of structural change that always invalidates an iterator, but adding or removing a key does. The fail-fast iterator compares modification counts. It detects bugs in a single thread. It is not a lock against another thread.
A key the map can hash again
final class Id {
private final String value;
Id(String value) { this.value = value; }
@Override public boolean equals(Object obj) {
return obj instanceof Id other && value.equals(other.value);
}
@Override public int hashCode() {
return value.hashCode();
}
}
Map<Id, String> names = new HashMap<>();
names.put(new Id("u-1"), "Ada");
names.get(new Id("u-1")); // "Ada"You put an Id, then change the field hashCode reads, then call get with the modified object. Iteration still shows the entry. Why does get return null?
put stored the entry under the old hash code. get uses the new hash code, so it searches a different bucket and does not see the entry. The entry remains reachable by walking the table, which does not rehash. The key has to stay immutable, or it has to leave the map before the field changes.