Java Map

›Short versionOpen if you only have a minute.

A map binds each key to one value. A second put with the same key replaces the value.
Map stands beside Collection. You iterate through keySet, values, or entrySet.
containsKey and get follow the key. containsValue walks every entry and is linear.
HashMap: average constant-time get and put, no order. Keys need a stable equals and hashCode.
TreeMap: sorted keys, O(log n). Comparison must be consistent with equals.
LinkedHashMap: average constant time, plus insertion order or access order.

A phone book, a counter of words, a cache of computed answers: each one is a from a to a . The key is how you ask. The value is what you get back.

Because a map holds pairs, it is not a Collection. The methods are how the pairs, the keys, or the values become something a collection algorithm can walk.

Look up by key, scan by value

The complexity that matters is which side you search. get and containsKey are the cheap calls on a HashMap, average constant time, and logarithmic on a TreeMap. does not get that treatment. If a loop calls it, the loop is quadratic in the number of entries.

Iterate an when you need both sides. A keySet loop that calls get on every key repeats the lookup the entry already held.

getOrDefault, putIfAbsent, computeIfAbsent, and merge cover the patterns that used to be a containsKey check followed by a put. They still count as access on a LinkedHashMap in access order, which matters once you are maintaining a cache.

One entry per key

MapDemo.java

Map<String, Integer> scores = new HashMap<>();
scores.put("Ada", 10);
scores.put("Ada", 12);                 // replaces; size stays 1
scores.get("Ada");                     // 12
scores.containsValue(12);              // linear scan

for (Map.Entry<String, Integer> e : scores.entrySet()) {
    e.getKey();
    e.getValue();
}

You put a key with value null, then call get. You also call get for a key you never put. Both return null. Which call tells them apart?

containsKey. It returns true for the key you stored with a null value, and false for the key that was never put. get alone cannot.