HashMap

You hand your coat in at the cloakroom and get a numbered tag. The tag is the key, and the coat is the value handed out for it. With the tag, the attendant returns your coat and not someone else's.

In Java such a cloakroom is a map, Map: a collection of key–value pairs in which a value is found by its key. The class you take most often is HashMap:

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Anna", 30);
        ages.put("Boris", 25);
        ages.put("Anna", 31);
        System.out.println(ages.get("Anna")); // 31
        System.out.println(ages.size());      // 2
        System.out.println(ages.get("Vera")); // null
    }
}

Let's go through the program line by line:

1. Map<String, Integer> has two type parameters: the key type String and the value type Integer.
2. put("Anna", 30) stores a pair: the key "Anna", the value 30.
3. The second put with the key "Anna" does not add a new pair; it replaces the value: it was 30 and becomes 31.
4. get("Anna") returns the value for the key, 31.
5. ages.size() returns 2: each key is stored once.
6. get("Vera") returns null: the map has no such key.

Keys in a map do not repeat, but values may: Anna and Boris can turn out to be the same age.

getOrDefault and containsKey

A classic task is counting how many times each word occurs. The word is the key, and a counter is the value:

String[] words = {"to", "be", "or", "not", "to", "be"};
Map<String, Integer> counts = new HashMap<>();
for (String w : words) {
    counts.put(w, counts.getOrDefault(w, 0) + 1);
}
System.out.println(counts.get("to"));         // 2
System.out.println(counts.get("not"));        // 1
System.out.println(counts.containsKey("hi")); // false

Let's see how it works:

1. counts.getOrDefault(w, 0) returns the value for the key w, or 0 if there is no such key.
2. put writes a counter one higher. A new word gets 1, and "to" gets 2 the second time it comes up.
3. containsKey("hi") checks whether the key is there and answers false.

You can print the whole map too: System.out.println(counts) prints key=value pairs in braces, for example {not=1, be=2, or=1, to=2}. The order of the pairs is not guaranteed, and an empty map prints as {}.

How HashMap stores pairs

How a HashMap works is one of the most common Java interview questions. You partly know the answer already: HashSet from the last lesson keeps its elements as the keys of a HashMap. Inside the map is an array of buckets, the hooks of our cloakroom. Here is how HashMap works with them:

1. The key's hashCode turns into a bucket number: from 0 to the number of buckets minus one.
2. If the bucket already has pairs, the new one joins the end of the chain. get walks the chain of one bucket: it compares hash codes, and equals confirms the equal key.
3. When the pairs outnumber three quarters of the buckets, the table doubles and lays the pairs out again.

A new HashMap<>() gets 16 buckets on the first put and grows when it holds more than 12 pairs. The widget uses a smaller table, new HashMap<>(4), so its threshold is 3 pairs. The keys cat, dog, owl, fox and bee get the values 1 to 5, and then get("owl") looks for the owl. Watch bucket 1: two keys land there. And on the fourth put the table grows to 8 buckets.

Let's see what happened:

1. The first put created a table of 4 buckets, and the key cat landed in bucket 3.
2. dog and owl have different hash codes but the same bucket number, 1. Their pairs lined up in a chain one after the other.
3. The pair with the key fox was the fourth with a threshold of 3, and the table grew to 8 buckets. The pairs were laid out again: dog and owl moved to bucket 5, fox to 6, cat to 7.
4. The key bee landed in the free bucket 3.
5. get("owl") went straight to bucket 5. dog has a different hash code, so equals was not needed. owl has the same hash code, equals confirmed the key, and get returned 3.

That is why get and put are fast: they look at one bucket, not at every pair. And that is why a HashMap has no order: the pairs do not sit in the order they were added, and they move when the table grows.

Here the cloakroom picture is not exact. An attendant does not rehang the coats when a second hall opens. But a HashMap moves every pair when it grows, and a key's bucket number may change.

Common mistake

The result of get was put into an int:

int n = counts.get("hi"); // ✗

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

There is no key "hi", and get returned null. Behind the assignment to an int hides the unboxing from the wrappers theme, a call to intValue(), and it cannot be called on null. If you need a number, use getOrDefault("hi", 0), and check whether a key is there with containsKey.

Key points

• HashMap holds key–value pairs: put stores a pair and, for a key it already has, replaces the value; get returns null for a missing key.
• getOrDefault gives a default value, and containsKey checks whether the key is there.
• The key's hashCode chooses the bucket, and inside the bucket's chain the key is found by hash code and equals.
• When the pairs outnumber three quarters of the buckets, the table doubles and the pairs are laid out again, so a HashMap has no order.