Java maps

HashMap<K, V> is the default map: separate chaining over a power-of-two table, load factor 0.75, expected O(1) put, get, containsKey and remove. Iteration order is unspecified. put returns the previous value or null, get returns null when the key is absent, and a key is identified by hashCode + equals.

It is not thread-safe; use ConcurrentHashMap when several threads write.

1static void basics() {
2    Map<String, Integer> age = new HashMap<>();
3    age.put("Ada", 36);
4    Integer old = age.put("Ada", 37);          // returns the previous value: 36
5    System.out.println(old + " " + age.get("Ada") + " " + age.get("Bob") + " " + age.containsKey("Bob"));
6}

LinkedHashMap is a HashMap plus a doubly linked list through its entries, so iteration follows **insertion order** (or, with accessOrder = true, order of last access). The cost is a little extra memory; lookups stay O(1).

Access order plus removeEldestEntry gives an LRU cache in a few lines: each get moves the entry to the end, and the oldest entry (the least recently used) is dropped when the size passes the capacity. After putting 1, 2, 3, reading 1 and putting 4 into a capacity-3 cache the keys are [3, 1, 4].

1static <K, V> Map<K, V> lruCache(int capacity) {
2    return new LinkedHashMap<K, V>(16, 0.75f, true) {                  // true = access order
3        @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
4            return size() > capacity;                                    // drop the least recently used
5        }
6    };
7}

TreeMap keeps keys **sorted** in a red-black tree: put, get and remove are O(log n), but it offers operations a hash map cannot: firstKey, lastKey, floorKey, ceilingKey, headMap, tailMap and subMap. It orders keys with compareTo or a Comparator, never with hashCode or equals.

Choose by the question you need to answer: exact lookup by key (HashMap), lookup plus insertion order (LinkedHashMap), or order-based queries such as “the largest key not above x” (TreeMap).

1static void navigate() {
2    TreeMap<Integer, String> tm = new TreeMap<>(Map.of(10, "a", 20, "b", 30, "c"));
3    System.out.println(tm.floorKey(25) + " " + tm.ceilingKey(25) + " " + tm.firstKey() + " " + tm.headMap(20));
4    // prints: 20 30 10 {10=a}
5}

getOrDefault(key, d) returns the value for key, or d if the key is absent. It does **not** insert the default, so the usual counting idiom needs a put: counts.put(w, counts.getOrDefault(w, 0) + 1). That is two hash lookups per word.

One trap: if the key is present with a stored null value, getOrDefault returns null, not the default, because the key exists. Choose the “Count with getOrDefault” option in the animation and watch the map being updated word by word. HashMap order is unspecified, so the animation lists entries in the order they were first inserted; the real map for “to be or not to be” prints {not=1, or=1, be=2, to=2}.

1static Map<String, Integer> countWords(String[] words) {
2    Map<String, Integer> counts = new HashMap<>();
3    for (String w : words) counts.put(w, counts.getOrDefault(w, 0) + 1);      // a missing key counts as 0
4    return counts;
5}

1Map<String, Integer> counts = new HashMap<>();
2for (String w : words) counts.put(w, counts.getOrDefault(w, 0) + 1);              // option 0: a default for a missing key
3for (String w : words) counts.merge(w, 1, Integer::sum);                           // option 1: insert 1, or combine with the old value
4Map<Integer, List<String>> byLength = new HashMap<>();
5for (String w : words) byLength.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);   // option 2: create the list on first use

computeIfAbsent(key, f) returns the existing value, or calls f to create one, stores it and returns it. It is the standard way to build a map of lists: map.computeIfAbsent(k, x -> new ArrayList<>()).add(v) replaces the three-step “get, check for null, put”. Choose “Group by length with computeIfAbsent” in the animation.

The mapping function must not modify the same map: HashMap detects this and throws ConcurrentModificationException (Java 9 and later). Also, computeIfAbsent treats a key mapped to null as absent and replaces it.

1static Map<Integer, List<String>> groupByLength(String[] words) {
2    Map<Integer, List<String>> byLength = new HashMap<>();
3    for (String w : words) byLength.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);
4    return byLength;                                    // {2=[to, be, or, to, be], 3=[not]} for "to be or not to be"
5}

1Map<String, Integer> counts = new HashMap<>();
2for (String w : words) counts.put(w, counts.getOrDefault(w, 0) + 1);              // option 0: a default for a missing key
3for (String w : words) counts.merge(w, 1, Integer::sum);                           // option 1: insert 1, or combine with the old value
4Map<Integer, List<String>> byLength = new HashMap<>();
5for (String w : words) byLength.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);   // option 2: create the list on first use

merge(key, value, f) does the whole read-modify-write in one call: if the key is absent it stores value; otherwise it stores f(oldValue, value). If f returns null the key is **removed**. Counting becomes a one-liner, counts.merge(w, 1, Integer::sum), with a single lookup. Choose “Count with merge”.

Use merge for counting, summing and collecting; use computeIfAbsent when you need to create a mutable container; use getOrDefault for read-only access with a fallback.

1static void mergeDemo() {
2    Map<String, Integer> c = new HashMap<>();
3    c.merge("x", 1, Integer::sum);
4    c.merge("x", 1, Integer::sum);                      // {x=2}
5    c.merge("x", 5, (oldV, newV) -> null);              // the function returned null: key removed
6    System.out.println(c);                              // {}
7}

1Map<String, Integer> counts = new HashMap<>();
2for (String w : words) counts.put(w, counts.getOrDefault(w, 0) + 1);              // option 0: a default for a missing key
3for (String w : words) counts.merge(w, 1, Integer::sum);                           // option 1: insert 1, or combine with the old value
4Map<Integer, List<String>> byLength = new HashMap<>();
5for (String w : words) byLength.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);   // option 2: create the list on first use

HashMap and HashSet iterate over the bucket array from index 0 upwards, and within a bucket in chain order. For small Integer keys the bucket is the value itself modulo the capacity, so keys often appear sorted by accident; for other keys the order looks random and can change when the table resizes. Never write code that depends on it.

When order matters, say so with the type: LinkedHashMap/LinkedHashSet for insertion order, TreeMap/TreeSet for sorted order. The animation shows the same values in all collections: try “Colliding buckets (mod 16)”.

1List<Integer> list = new ArrayList<>();
2Set<Integer> linked = new LinkedHashSet<>();
3Set<Integer> hash = new HashSet<>();
4Set<Integer> tree = new TreeSet<>();
5PriorityQueue<Integer> heap = new PriorityQueue<>();
6for (int x : arr) {
7    list.add(x);        // keeps insertion order, keeps duplicates
8    linked.add(x);      // keeps insertion order, drops duplicates
9    hash.add(x);        // order decided by hash buckets
10    tree.add(x);        // always sorted
11    heap.add(x);        // heap array: only the smallest is guaranteed first
12}
13System.out.println(list + " " + linked + " " + hash + " " + tree + " " + heap);

HashMap allows one null key (it hashes to 0, so it lives in bucket 0) and any number of null values. TreeMap with natural ordering throws NullPointerException for a null key because it cannot compare it. ConcurrentHashMap, Hashtable and the immutable Map.of(...) reject null keys and values (Map.of(...).get(null) also throws).

Null values make get ambiguous: a result of null can mean absent or present-with-null. Use containsKey to tell them apart, or avoid null values altogether.

1static void nulls() {
2    Map<String, Integer> hm = new HashMap<>();
3    hm.put(null, 1); hm.put("a", 2);
4    System.out.println(hm.get(null));                                     // 1
5    try { new TreeMap<String, Integer>().put(null, 1); }
6    catch (NullPointerException e) { System.out.println("TreeMap: no null key"); }
7}