Hash Map

A key leads to a value

HashMap stores key-value pairs. The key is used for lookup, while the value is the data that should be obtained for that key. This format is useful when it is not enough to know whether an object has been seen: we also need to store information associated with it.

Map<String, Integer> scores = new HashMap<>();

scores.put("Alice", 8);
scores.put("Bob", 5);

int aliceScore = scores.get("Alice");
boolean hasBob = scores.containsKey("Bob");

The put(), get(), containsKey(), and remove() operations take O(1) on average. This makes a map a convenient replacement for repeatedly searching for a pair in an array or list.

One key, one current value

If put() is called with a key that already exists, a new pair is not created next to the old one: the value for that key is replaced.

scores.put("Alice", 8);
scores.put("Alice", 10);

System.out.println(scores.get("Alice"));

The program prints 10. A map therefore naturally models the relation “each key has one current value”: an element index, an occurrence count, a vertex state, the best result found so far, or other data that must be accessed quickly by key.

When to choose a Map

Use a map when the algorithm needs more than a fast yes-or-no answer and must retrieve something by key. If there is no additional value and a membership check is enough, a Set is usually simpler.