The Collections Framework

TreeMap & LinkedHashMap

15 min Lesson 7 of 14

TreeMap & LinkedHashMap

You already know HashMap: fast, unordered. But sometimes you need more than fast lookups — you need the keys to come out in a predictable order. Java offers two Map implementations that solve this in different ways: TreeMap keeps keys sorted by their natural order (or a custom comparator), while LinkedHashMap preserves the order in which keys were inserted.

Why Order Matters

Consider building a leaderboard, a sorted dictionary, or a cache that evicts the oldest entry first. A plain HashMap offers no ordering guarantee at all — iteration can come out in any sequence. Choosing the right ordered map makes your intent explicit and eliminates fragile sorting steps after the fact.

TreeMap — Sorted by Key

TreeMap<K, V> is backed by a Red-Black tree. Every put and get is O(log n) rather than the amortised O(1) of a hash map, but in return the map stays sorted at all times.

import java.util.TreeMap;

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Charlie", 88);
scores.put("Alice",   95);
scores.put("Bob",     72);

// Iterating always yields keys in ascending alphabetical order
for (var entry : scores.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}
// Output:
// Alice   = 95
// Bob     = 72
// Charlie = 88

Because the tree is always sorted, TreeMap exposes a rich set of navigation methods that plain maps lack:

TreeMap<Integer, String> calendar = new TreeMap<>();
calendar.put(1,  "January");
calendar.put(6,  "June");
calendar.put(9,  "September");
calendar.put(12, "December");

System.out.println(calendar.firstKey());          // 1
System.out.println(calendar.lastKey());           // 12
System.out.println(calendar.floorKey(7));         // 6  (greatest key <= 7)
System.out.println(calendar.ceilingKey(7));       // 9  (smallest key >= 7)
System.out.println(calendar.headMap(9));          // {1=January, 6=June}
System.out.println(calendar.tailMap(6));          // {6=June, 9=September, 12=December}
System.out.println(calendar.subMap(6, 12));       // {6=June, 9=September}

NavigableMap interface: TreeMap implements NavigableMap, which adds floorKey, ceilingKey, lowerKey, higherKey, headMap, tailMap, and subMap. Declare your variable as NavigableMap<K,V> when you want to expose these methods to callers.

Custom Sort Order with a Comparator

When you need a different sort order — say, reverse alphabetical, or case-insensitive — pass a Comparator to the constructor:

// Reverse alphabetical order
TreeMap<String, Integer> reversed = new TreeMap<>(Comparator.reverseOrder());
reversed.put("banana", 2);
reversed.put("apple",  1);
reversed.put("cherry", 3);

reversed.keySet().forEach(System.out::println);
// cherry → banana → apple

Keys must be Comparable (or a Comparator must be supplied). If you store keys of a class that does not implement Comparable and provide no comparator, the first put will throw a ClassCastException at runtime.

LinkedHashMap — Insertion-Ordered

LinkedHashMap<K, V> wraps a regular hash table with a doubly-linked list that threads through every entry in insertion order. Lookups are still O(1) — just like HashMap — but iteration reflects the order keys were first added.

import java.util.LinkedHashMap;

LinkedHashMap<String, String> capitals = new LinkedHashMap<>();
capitals.put("France",  "Paris");
capitals.put("Japan",   "Tokyo");
capitals.put("Brazil",  "Brasília");
capitals.put("Canada",  "Ottawa");

// Iteration order == insertion order
capitals.forEach((country, capital) ->
    System.out.println(country + " -> " + capital));
// France  -> Paris
// Japan   -> Tokyo
// Brazil  -> Brasília
// Canada  -> Ottawa

Access-Order Mode — Building an LRU Cache

There is a second constructor form: new LinkedHashMap<>(initialCapacity, loadFactor, true). The third argument switches the map from insertion-order to access-order: every get or put moves the accessed entry to the tail of the linked list. Combined with removeEldestEntry, this gives you a simple LRU (Least Recently Used) cache in about ten lines:

import java.util.LinkedHashMap;
import java.util.Map;

int MAX = 3;

LinkedHashMap<String, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > MAX;
    }
};

lruCache.put("a", "apple");
lruCache.put("b", "banana");
lruCache.put("c", "cherry");

lruCache.get("a");            // "a" is now the most recently used

lruCache.put("d", "date");    // triggers removeEldestEntry; "b" is oldest → evicted

System.out.println(lruCache.keySet()); // [c, a, d]

This is a textbook LRU cache pattern in Java. It works perfectly for caches up to tens of thousands of entries in a single-threaded context. For a thread-safe LRU cache, wrap it with Collections.synchronizedMap or use a dedicated library.

Choosing Between the Three Map Implementations

HashMap — fastest (O(1) amortised), no ordering guarantee. Use when order does not matter.
LinkedHashMap — O(1) lookups, preserves insertion (or access) order. Use for predictable iteration, JSON serialisation order, or LRU caches.
TreeMap — O(log n) operations, always sorted. Use when you need range queries, navigation methods, or guaranteed sorted output.

Quick Comparison

// HashMap   — random order, fastest
Map<String, Integer> hash   = new HashMap<>();

// LinkedHashMap — insertion order, same speed as HashMap
Map<String, Integer> linked = new LinkedHashMap<>();

// TreeMap   — sorted order, slower (log n)
Map<String, Integer> tree   = new TreeMap<>();

Program to the interface. Declare variables as Map<K, V> unless you specifically need NavigableMap methods. This keeps your code flexible — you can swap the implementation without touching call sites.

Summary

TreeMap keeps keys sorted (natural order or a custom Comparator) at the cost of O(log n) operations, and adds powerful navigation methods like floorKey, ceilingKey, and subMap. LinkedHashMap preserves insertion order (or access order when that flag is set) at O(1) speed — making it ideal for predictable iteration and LRU caches. Pick based on whether you need sorted navigation, insertion order, or raw speed.