Advanced HashMap, TreeMap & LinkedHashMap

Reviewed & published by Brayan K

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.

Part of the free Java course at LearnCodingFast — hands-on lessons with worked examples and the output they print, plus practice exercises and a quick quiz.

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.

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
    }
}

🎯 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.

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
    }
}

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:

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

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

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.

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 }
}

🎯 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.

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}
    }
}

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.

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")));
    }
}

🧩 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.

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
    }
}

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

🎉 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.

Practice quiz

Continue this course

• Previous: Java Collections Framework Internals & Performance
• Next: Multithreading in Java: Threads, Runnables & Executors — Create and manage threads, use thread pools and ExecutorService
• Quick reference: Java cheat sheet
• From the blog: Java Collections Framework: A Deep Dive

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.