Map: HashMap, LinkedHashMap, TreeMap and key operations

Map basics

A Map<K,V> maps unique keys to values. The key must be unique; values may repeat.

Map<String, Integer> pop = new HashMap<>();
pop.put("Tokyo",   14000000);
pop.put("London",  9000000);
pop.put("Tokyo",   14500000);  // replaces previous value
System.out.println(pop.get("London"));            // 9000000
System.out.println(pop.getOrDefault("Paris", 0)); // 0
System.out.println(pop.containsKey("Tokyo"));     // true

Iterating a Map:

// Three views:
for (String key : pop.keySet())           { ... }
for (Integer val : pop.values())          { ... }
for (Map.Entry<String,Integer> e : pop.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

Modern merge methods:

// putIfAbsent: only inserts if the key is missing
pop.putIfAbsent("Paris", 2200000);

// computeIfAbsent: compute and insert only if missing
Map<String, List<String>> groups = new HashMap<>();
groups.computeIfAbsent("admin", k -> new ArrayList<>()).add("alice");

// merge: combine existing value with new one, or insert if absent
Map<String, Integer> wordCount = new HashMap<>();
wordCount.merge("java", 1, Integer::sum); // 1
wordCount.merge("java", 1, Integer::sum); // 2

Three implementations:

| Class | Order | Operations | |---|---|---| | HashMap | None | O(1) average get/put | | LinkedHashMap | Insertion order | O(1) average | | TreeMap | Natural/Comparator sort | O(log n) |

TreeMap also implements NavigableMap giving floorKey, ceilingKey, headMap, tailMap.