A HashMap in Java stores the values against the keys and it finds them again by hashing the key. That means a lookup, an insertion and a membership test all cost roughly the constant time regardless of how many entries are in the map. That speed, plus the fact that it accepts any object as a key, is why it is the default choice whenever your data is naturally pairs.
The previous lesson in this module covered "How Does ArrayList Combine Array Power With Flexibility?", and the next lesson in this module is about "How Does HashSet Enforce Uniqueness so Fast?".
What does a HashMap actually store?
It stores the entries, each one a key and a value. The keys are unique, so putting the same key twice replaces the value and leaves the size alone, and the values can repeat as much as you like. The lookups are by key, and the map also lets you walk the keys, the values or the entries.
import java.util.HashMap;
import java.util.Map;
public class HashMapBasicsDemo {
public static void main(String[] args) {
Map<String, Integer> stock = new HashMap<>();
stock.put("apple", 12);
stock.put("pear", 4);
stock.put("apple", 7);
System.out.println("size: " + stock.size());
System.out.println("get apple: " + stock.get("apple"));
System.out.println("get pear: " + stock.get("pear"));
System.out.println("get melon: " + stock.get("melon"));
System.out.println("containsKey pear: " + stock.containsKey("pear"));
stock.remove("pear");
System.out.println("after remove: " + stock);
stock.put("fig", null);
System.out.println("a null value is allowed: " + stock.get("fig"));
System.out.println("keys: " + stock.keySet());
System.out.println("values: " + stock.values());
}
}The output is this.
size: 2
get apple: 7
get pear: 4
get melon: null
containsKey pear: true
after remove: {apple=7}
a null value is allowed: null
keys: [apple, fig]
values: [7, null]There are four details to take from that output. The three puts produced a size of two, because the third put replaced the value for "apple". The call get on a missing key returns null rather than throwing, so a null result can mean either that the key is absent or that it is present with a null value, and you use containsKey when you need to tell the difference. A null value is perfectly legal. And the order of keySet() is not promised, so never write a test that expects "apple" before "fig".
Why do keys need both equals and hashCode?
A HashMap finds the right bucket by hashing the key, and then it compares the keys inside that bucket. The hash decides the bucket, and equals decides whether two keys are the same key. If a key type overrides neither one of them, then every instance is treated as its own key, and the lookups fail even when the objects hold identical data.
import java.util.HashMap;
import java.util.Map;
public class HashMapKeysDemo {
static class Ticket {
private final String reference;
Ticket(String reference) {
this.reference = reference;
}
}
static class ProperTicket {
private final String reference;
ProperTicket(String reference) {
this.reference = reference;
}
@Override
public boolean equals(Object other) {
if (this == other) {
return true;
}
if (!(other instanceof ProperTicket ticket)) {
return false;
}
return reference.equals(ticket.reference);
}
@Override
public int hashCode() {
return reference.hashCode();
}
}
public static void main(String[] args) {
Map<Ticket, String> broken = new HashMap<>();
broken.put(new Ticket("A-1"), "first ticket");
System.out.println("lookup with a fresh key object: "
+ broken.get(new Ticket("A-1")));
Map<ProperTicket, String> working = new HashMap<>();
working.put(new ProperTicket("A-1"), "first ticket");
System.out.println("with equals and hashCode: "
+ working.get(new ProperTicket("A-1")));
System.out.println("size stays at one: " + working.size());
}
}The output is this.
lookup with a fresh key object: null
with equals and hashCode: first ticket
size stays at one: 1The first line is the bug that everybody hits once. The map contains an entry, the key object holds the right reference, and the lookup still returns null, because the map never considered the two tickets to be the same. The contract that fixes it has two halves. Two objects that are equal must produce the same hash code, and equal objects must return true from equals. Implement one without the other and the lookups break in confusing ways, which is why the two overrides always travel together.
What happens if you change a key after inserting it?
The entry becomes unreachable. The map found the bucket by using the old hash code, and after you change the key its hash code no longer matches that bucket, so the lookup lands in the wrong place and finds nothing. The data is still in the map. It is simply orphaned.
import java.util.HashMap;
import java.util.Map;
public class HashMapMutableKeyDemo {
static class Session {
private String id;
Session(String id) {
this.id = id;
}
void rename(String newId) {
this.id = newId;
}
@Override
public boolean equals(Object other) {
return other instanceof Session session && id.equals(session.id);
}
@Override
public int hashCode() {
return id.hashCode();
}
}
public static void main(String[] args) {
Map<Session, String> sessions = new HashMap<>();
Session session = new Session("s-1");
sessions.put(session, "logged in");
System.out.println("before the change: " + sessions.get(session));
session.rename("s-2");
System.out.println("after the change the entry is unreachable: " + sessions.get(session));
System.out.println("the map still holds one entry: " + sessions.size());
System.out.println("the value is still stored: " + sessions.values());
}
}The output is this.
before the change: logged in
after the change the entry is unreachable: null
the map still holds one entry: 1
the value is still stored: [logged in]This is why the map keys should be immutable in practice. The usual choices are the strings, the integers, or a record with final fields. Anything whose hash code cannot change after the construction. If you genuinely need to change a key, then remove the entry and put it back with the new key.
Which map should you use?
The HashMap is the sensible default, but two of its siblings solve specific problems.
| Type | Iteration order | Extra cost | Use it when |
|---|---|---|---|
| HashMap | unspecified | none | you only ever look entries up by key |
| LinkedHashMap | insertion order | one extra pointer per entry | you want a predictable print order or to keep recent entries at the end |
| TreeMap | sorted by key | each operation is logarithmic rather than constant | you need sorted keys, or range queries such as everything from "a" to "m" |
One more detail catches the newcomers. A HashMap allows a single null key and the null values, because null is a perfectly good key as far as the map is concerned. The sorted map refuses the null keys, since it has to compare them.
Which other map methods save you a lookup?
Beyond put and get, the map interface carries a handful of methods that remove a get-then-put dance. The method putIfAbsent stores a value only when the key is missing, the method computeIfAbsent calls a function to build the value the first time that a key is seen, and the method merge combines a new value with whatever is already stored. That last one is how you count the occurrences in a list of words with a single map. The method getOrDefault hands back a fallback instead of null when a key is missing.
None of these are exotic, and each one shortens the code that would otherwise look up a key twice. When you need both halves of a pair, walk the entry set rather than looking every value up by its key. Each entry gives you the key and the value together, which avoids a second lookup per row and reads more clearly in a loop over the contents of a map.
HashMap rules worth keeping
- The keys are unique, and a repeated put replaces the value without changing the size.
- The key types must override equals and
hashCodetogether, or the lookups by an equal object fail. - Never change a key after it has been inserted. Remove it and re-insert it instead.
- The iteration order is not guaranteed, so sort it or use a linked map if the order matters.
- The call get returns null for a missing key, which is indistinguishable from a stored null without
containsKey.
Try it yourself: build a map from the country code to the country name for four countries, and then look up one that exists and one that does not, printing the results. Add a country whose name is null and show that containsKey and get behave differently for it. Finally, put the same key in twice with the different values and print the size of the map, to confirm that only the last value survives.