Lesson 25 • Advanced

Advanced Maps: HashMap, TreeMap & LinkedHashMap

Go beyond put and get: count and group in one line with merge/computeIfAbsent, navigate sorted keys with TreeMap, build an LRU cache from LinkedHashMap, and update safely across threads with ConcurrentHashMap.

Before You Start

You should already be comfortable with the Collections internals and the hashCode()/equals() contract. This lesson assumes you can create a basic HashMap<K, V> and iterate it — here you'll learn the methods that make Maps genuinely powerful.

What You'll Learn

✓Count and accumulate in one line with merge() and getOrDefault()
✓Build values lazily with computeIfAbsent() and computeIfPresent()
✓Insert only-if-missing with putIfAbsent()
✓Control iteration order with LinkedHashMap (insertion vs access order)
✓Navigate sorted keys with TreeMap: floorKey, ceilingKey, subMap
✓Update maps safely across threads with ConcurrentHashMap atomic ops

🗄️ A Real-World Analogy

Think of the three core Map types as three ways of organising a filing cabinet:

HashMap is a cabinet where folders are thrown into whichever drawer is free. Finding any one folder is instant, but the order is chaos.
LinkedHashMap threads a string through every folder in the order you filed them — fast lookup and a predictable walk from first to last (or, with access order, "most recently touched" last — exactly what an LRU cache needs).
TreeMap is an alphabetised cabinet. Filing takes a moment longer, but you can ask "the folder just before M" or "everything from D to H" — the navigation methods you'll use below.

The modern methods — merge, computeIfAbsent, getOrDefault — are like a clerk who handles "add to the folder, or start a new one if it doesn't exist" in a single instruction, instead of you checking the drawer first every time.

1️⃣ The Methods That Replace "check, then put"

The old way to count things was a three-line dance: get the value, test for null, then put back the incremented number. Java 8 collapsed all of that into a handful of methods. Learn these five and most of your Map code becomes one line.

getOrDefault(key, fallback) — read a key, but return fallback instead of null when it's missing.
putIfAbsent(key, value) — insert only when the key isn't already there; returns the value that ended up staying.
merge(key, value, fn) — if absent, store value; if present, store fn(oldValue, value). The counting workhorse.
computeIfAbsent(key, fn) — if the key is missing, run fn(key), store the result, and return it. Perfect for "get-or-create a List".
computeIfPresent(key, fn) — only transform a value that already exists; does nothing for missing keys.

💡 Rule of thumb: reach for merge when you're accumulating (counts, sums) and computeIfAbsent when the value is a container you keep adding to (a List or Set per key).

Worked Example: getOrDefault, putIfAbsent, merge, compute*

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // getOrDefault — read a key, fall back to a default if missing
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 5);
        System.out.println("apple:  " + stock.getOrDefault("apple", 0));   // 5  (present)
        System.out.println("pear:   " + stock.getOrDefault("pear", 0));    // 0  (default)

        // putIfAbsent — insert only when the key is missing; returns the EXISTING value
        Map<String, String> owners = new HashMap<>();
        owners.putIfAbsent("car", "Alice");   // inserted, returns null
        owners.putIfAbsent("car", "Bob");      // ignored — key already there
        System.out.println("car owner: " + owners.get("car"));            // Alice

        // merge — combine a new value with the existing one (or insert if absent)
        Map<String, Integer> counts = new HashMap<>();
        for (String word : "red blue red green red blue".split(" ")) {
            // if absent -> store 1; if present -> add 1 to the old value
            counts.merge(word, 1, Integer::sum);
        }
        System.out.println("word counts: " + new TreeMap<>(counts));      // sorted view

        // computeIfAbsent — build a value lazily (here: a List per key) and return it
        Map<Character, List<String>> byLetter = new TreeMap<>();
        for (String name : new String[]{"Ann", "Bob", "Amy", "Ben"}) {
            // create the list once, then add to it every time
            byLetter.computeIfAbsent(name.charAt(0), k -> new ArrayList<>()).add(name);
        }
        System.out.println("grouped: " + byLetter);

        // computeIfPresent — only transform a value that already exists
        stock.computeIfPresent("apple", (k, v) -> v - 2);   // 5 -> 3
        stock.computeIfPresent("pear",  (k, v) -> v - 2);   // no-op, key missing
        System.out.println("apple after sale: " + stock.get("apple"));    // 3
    }
}

Output

apple:  5
pear:   0
car owner: Alice
word counts: {blue=2, green=1, red=3}
grouped: {A=[Ann, Amy], B=[Bob, Ben]}
apple after sale: 3

This is real code — run it for free atonecompiler.com/javaor in your own editor.

🎯 Your Turn #1 — Word Frequency

Fill in the blanks so merge counts each word and getOrDefault reads a count safely. The expected output is in the comments — match it exactly.

Try It: Count words with merge()

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 🎯 YOUR TURN — fill in the blanks marked with ___

        String text = "to be or not to be";
        Map<String, Integer> freq = new TreeMap<>();

        for (String word : text.split(" ")) {
            // 1) Count each word. If it's new, start at 1; if seen, add 1.
            freq.merge(word, ___, ___);   // 👉 first ___ = the value to start with
                                          // 👉 second ___ = how to combine old + new
        }

        // 2) Look up a count safely — return 0 when the word never appeared
        int beCount  = freq.___("be", 0);    // 👉 method that reads with a fallback
        int catCount = freq.___("cat", 0);   // 👉 same method, missing key

        System.out.println(freq);
        System.out.println("be:  " + beCount);
        System.out.println("cat: " + catCount);

        // ✅ Expected output:
        // {be=2, not=1, or=1, to=2}
        // be:  2
        // cat: 0
    }
}

This is real code — run it for free atonecompiler.com/javaor in your own editor.

2️⃣ Ordering: LinkedHashMap, TreeMap & EnumMap

A plain HashMap gives you no order at all — iteration can appear in any sequence and may change between runs. When order matters, pick a different implementation:

LinkedHashMap

Iterates in insertion order by default. Pass accessOrder=true to instead order by "most recently used" — the basis of an LRU cache.

TreeMap

Keeps keys sorted (natural order or a Comparator) and adds navigation: floorKey, ceilingKey, subMap, firstKey, lastKey.

EnumMap

A tiny, very fast map whose keys are an enum. Backed by an array, it iterates in the enum's declaration order. Use it whenever your keys are an enum.

TreeMap navigation, in plain English: floorKey(x) = the largest key ≤ x; ceilingKey(x) = the smallest key ≥ x; subMap(from, to) = a live view of keys in the range [from, to) (from inclusive, to exclusive). These turn "find the price tier for a spend" into a single call.

Worked Example: LinkedHashMap, TreeMap navigation & EnumMap

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // LinkedHashMap — remembers INSERTION order (HashMap would not)
        Map<String, Integer> steps = new LinkedHashMap<>();
        steps.put("wake", 1);
        steps.put("brew", 2);
        steps.put("code", 3);
        System.out.println("insertion order: " + steps);   // wake, brew, code — in order

        // TreeMap — keeps keys SORTED, and adds navigation methods
        TreeMap<Integer, String> grades = new TreeMap<>();
        grades.put(50, "D");
        grades.put(60, "C");
        grades.put(70, "B");
        grades.put(80, "A");

        System.out.println("sorted: " + grades);                 // ascending by key
        System.out.println("floorKey(65):   " + grades.floorKey(65));    // 60 (<= 65)
        System.out.println("ceilingKey(65): " + grades.ceilingKey(65));  // 70 (>= 65)
        System.out.println("firstKey: " + grades.firstKey() + ", lastKey: " + grades.lastKey());

        // subMap — a live view of a key range [60, 80)  (60 inclusive, 80 exclusive)
        System.out.println("subMap[60,80): " + grades.subMap(60, 80));

        // EnumMap — a tiny, fast map keyed by an enum (backed by an array)
        Map<Day, String> plan = new EnumMap<>(Day.class);
        plan.put(Day.MON, "Gym");
        plan.put(Day.WED, "Read");
        plan.put(Day.FRI, "Rest");
        System.out.println("EnumMap (enum order): " + plan);     // always MON, WED, FRI
    }

    enum Day { MON, TUE, WED, THU, FRI }
}

Output

insertion order: {wake=1, brew=2, code=3}
sorted: {50=D, 60=C, 70=B, 80=A}
floorKey(65):   60
ceilingKey(65): 70
firstKey: 50, lastKey: 80
subMap[60,80): {60=C, 70=B}
EnumMap (enum order): {MON=Gym, WED=Read, FRI=Rest}

This is real code — run it for free atonecompiler.com/javaor in your own editor.

🎯 Your Turn #2 — Price Tiers

Use TreeMap navigation to find which discount tier a spend qualifies for, then show every tier from 100 upward. Decide carefully between floorKey and ceilingKey.

Try It: TreeMap floorKey + tailMap

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 🎯 YOUR TURN — a price-tier lookup with TreeMap navigation

        // Spend thresholds -> discount label
        TreeMap<Integer, String> tiers = new TreeMap<>();
        tiers.put(0,   "None");
        tiers.put(50,  "Bronze");
        tiers.put(100, "Silver");
        tiers.put(200, "Gold");

        int spend = 130;

        // 1) Find the highest threshold that is <= spend (the tier they qualify for)
        int key = tiers.___(spend);     // 👉 floor or ceiling? you want <= spend
        String tier = tiers.get(key);

        // 2) Show every tier from 100 upward (inclusive) using a tail view
        System.out.println("Spend " + spend + " -> " + tier);
        System.out.println("From 100 up: " + tiers.___(100));   // 👉 tailMap

        // ✅ Expected output:
        // Spend 130 -> Silver
        // From 100 up: {100=Silver, 200=Gold}
    }
}

This is real code — run it for free atonecompiler.com/javaor in your own editor.

3️⃣ Caches & Concurrency: LinkedHashMap LRU + ConcurrentHashMap

Two production patterns pull all of this together.

LRU cache. A cache with a size limit must drop something when it fills up; "least recently used" is the classic policy. Construct a LinkedHashMap with access order on, then override removeEldestEntry to return true once the size passes your capacity. Because access order moves every touched entry to the end, the eldest entry is always the least-recently-used one — eviction is automatic.

Thread safety. A normal HashMap is corrupted by concurrent writes. ConcurrentHashMap lets many threads read and write at once, and its merge, compute, and computeIfAbsent methods run atomically — so incrementing a counter from many threads is correct without you writing any locks.

Don't reach for Collections.synchronizedMap(...) for concurrency — it locks the whole map on every call and you still can't iterate it safely without external locking. ConcurrentHashMap is almost always the better choice.

Real-World: LRU cache + ConcurrentHashMap atomic counters

import java.util.*;
import java.util.concurrent.*;

public class Main {
    // A complete LRU cache: access-order LinkedHashMap + removeEldestEntry.
    static class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private final int capacity;
        LRUCache(int capacity) {
            super(16, 0.75f, true);   // true = ACCESS order (recently used moves to end)
            this.capacity = capacity;
        }
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity;   // evict the eldest once we exceed capacity
        }
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(2);
        cache.put("a", 1);
        cache.put("b", 2);
        cache.get("a");          // touch "a" — now "b" is the least-recently-used
        cache.put("c", 3);       // capacity is 2, so "b" is evicted
        System.out.println("LRU contents: " + cache);   // {a=1, c=3}

        // ConcurrentHashMap — thread-safe map with ATOMIC update methods
        ConcurrentHashMap<String, Integer> hits = new ConcurrentHashMap<>();
        // merge/compute run atomically — safe even when many threads call them
        hits.merge("/home", 1, Integer::sum);
        hits.merge("/home", 1, Integer::sum);
        hits.compute("/about", (k, v) -> (v == null ? 0 : v) + 1);
        System.out.println("page hits: " + new TreeMap<>(hits));

        // computeIfAbsent on ConcurrentHashMap — atomic "get-or-create"
        ConcurrentHashMap<String, Set<String>> tags = new ConcurrentHashMap<>();
        tags.computeIfAbsent("java", k -> ConcurrentHashMap.newKeySet()).add("maps");
        tags.computeIfAbsent("java", k -> ConcurrentHashMap.newKeySet()).add("lru");
        System.out.println("tags[java]: " + new TreeSet<>(tags.get("java")));
    }
}

Output

LRU contents: {a=1, c=3}
page hits: {/about=1, /home=2}
tags[java]: [lru, maps]

This is real code — run it for free atonecompiler.com/javaor in your own editor.

🧩 Mini-Challenge — Group People by City

Support is faded now: only an outline is given. Build a TreeMap<String, List<String>> grouping each person under their city using computeIfAbsent, then print it. The expected output is in the comments.

Mini-Challenge: group names by city

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 🎯 MINI-CHALLENGE: Group people by their city, keeping cities sorted
        //
        // Data (name, city):
        //   Alice/London, Bob/Paris, Cara/London, Dan/Paris, Eve/London
        //
        // 1. Use a TreeMap<String, List<String>>  (sorted by city)
        // 2. For each person, computeIfAbsent(city, k -> new ArrayList<>()).add(name)
        // 3. Print the map
        //
        // ✅ Expected output:
        // {London=[Alice, Cara, Eve], Paris=[Bob, Dan]}

        String[][] people = {
            {"Alice","London"}, {"Bob","Paris"}, {"Cara","London"},
            {"Dan","Paris"}, {"Eve","London"}
        };

        // your code here
    }
}

This is real code — run it for free atonecompiler.com/javaor in your own editor.

Common Errors & Fixes

❌

Using put() where you meant merge(): map.put(word, map.get(word) + 1) throws NullPointerException the first time a word appears, because get returns null and you can't add 1 to it. Fix: map.merge(word, 1, Integer::sum), which handles the missing case for you.

❌

Mutating a map while iterating it: calling map.put(...) or map.remove(...) inside a for (var e : map.entrySet()) loop throws ConcurrentModificationException. Fix: collect changes first, or use iterator.remove(), or map.replaceAll((k, v) -> ...) for in-place value edits.

❌

A null key in a TreeMap: treeMap.put(null, 1) throws NullPointerException because TreeMap must compare keys. HashMap allows one null key; ConcurrentHashMap allows none. Know your implementation before relying on null.

❌

A null value in ConcurrentHashMap: chm.put("k", null) throws NullPointerException. It forbids null values so that a null from get unambiguously means "absent". HashMap, by contrast, happily stores null values.

❌

computeIfPresent returning null deletes the entry: if your remapping function returns null, the key is removed, not set to null. That's intentional — just be aware it can silently shrink your map.

Pro Tips

💡 One-line counter: map.merge(key, 1, Integer::sum) is the idiomatic way to count occurrences.

💡 get-or-create: map.computeIfAbsent(key, k -> new ArrayList<>()).add(item) builds a multi-map without any null checks.

💡 Prefer EnumMap for enum keys: it's faster and uses less memory than a HashMap, and iterates in enum order for free.

💡 Need both order kinds? Sorted snapshot of a HashMap: wrap it once — new TreeMap<>(hashMap) — to print or scan in sorted order without changing the original.

📋 Quick Reference

Method / Type	Purpose	Example
getOrDefault(k, d)	Read with a fallback	map.getOrDefault("x", 0)
putIfAbsent(k, v)	Insert only if missing	map.putIfAbsent("x", 1)
merge(k, v, fn)	Accumulate (count/sum)	map.merge("x", 1, Integer::sum)
computeIfAbsent(k, fn)	Get-or-create a value	m.computeIfAbsent(k, x -> new ArrayList<>())
computeIfPresent(k, fn)	Transform if present	m.computeIfPresent(k, (key, v) -> v - 1)
floorKey / ceilingKey	Largest ≤ / smallest ≥	tree.floorKey(65)
subMap(from, to)	Range view [from, to)	tree.subMap(60, 80)
LinkedHashMap(…, true)	Access order (LRU)	new LinkedHashMap(16, .75f, true)
ConcurrentHashMap	Thread-safe, atomic ops	chm.merge(k, 1, Integer::sum)

❓ Frequently Asked Questions

What is the difference between merge() and put()?

put() blindly overwrites whatever value a key had. merge(key, value, remappingFunction) combines the new value with the existing one: if the key is absent it stores the value, otherwise it calls your function with (oldValue, value) and stores the result. Use put() to set/replace; use merge() to accumulate, like counting with map.merge(word, 1, Integer::sum).

computeIfAbsent vs putIfAbsent — which should I use?

putIfAbsent(k, v) takes a ready-made value and always creates it, even when the key already exists (then throws it away). computeIfAbsent(k, fn) only runs the function when the key is missing, so it's the right choice when the value is expensive to build or is a container you keep adding to — for example computeIfAbsent(k, x -> new ArrayList<>()).add(item).

Can a HashMap have null keys or null values?

HashMap allows one null key and any number of null values. TreeMap forbids null keys because it must compare keys (you get a NullPointerException). ConcurrentHashMap forbids both null keys and null values entirely, because null is ambiguous in a concurrent map — get() returning null can't tell 'absent' from 'mapped to null'.

When should I pick TreeMap over HashMap?

Pick TreeMap when you need keys in sorted order or need navigation: floorKey/ceilingKey, firstKey/lastKey, or range views like subMap/headMap/tailMap. The cost is O(log n) per operation versus HashMap's average O(1). If you never iterate in order and never do range queries, HashMap is faster.

How does a LinkedHashMap become an LRU cache?

Construct it with access order on — new LinkedHashMap<>(16, 0.75f, true) — so every get() and put() moves that entry to the end. Then override removeEldestEntry to return true once size() exceeds your capacity. The eldest entry is always the least-recently-used one, so it gets evicted automatically.

🎉 Lesson Complete!

You can now count and group in one line with merge and computeIfAbsent, pick the right Map for the ordering you need, navigate sorted keys with TreeMap, build an LRU cache from LinkedHashMap, and update maps safely across threads with ConcurrentHashMap.

Next: Multithreading — create and manage threads, and use thread pools with ExecutorService.

Advanced Maps: HashMap, TreeMap & LinkedHashMap

Before You Start

What You'll Learn

🗄️ A Real-World Analogy

1️⃣ The Methods That Replace "check, then put"

🎯 Your Turn #1 — Word Frequency

2️⃣ Ordering: LinkedHashMap, TreeMap & EnumMap

🎯 Your Turn #2 — Price Tiers

3️⃣ Caches & Concurrency: LinkedHashMap LRU + ConcurrentHashMap

🧩 Mini-Challenge — Group People by City

Common Errors & Fixes

Pro Tips

📋 Quick Reference

❓ Frequently Asked Questions

🎉 Lesson Complete!

Cookie & Privacy Settings