PHASE 9Intermediate ~31 min· topic 6 of 13

Topic 9.6

LinkedHashMap and TreeMap

In one line

LinkedHashMap is a HashMap that also remembers order (insertion or, optionally, access order), which makes a five-line LRU cache. TreeMap keeps keys sorted in a red-black tree and answers range and nearest-key questions in O(log n).

Think of it like this

Two ways to keep a visitors' book. A hotel register lists guests in the order they checked in, and a librarian's "recently borrowed" shelf moves a book to the end each time someone borrows it, so the book at the front is the one nobody has touched for longest. A dictionary keeps words in alphabetical order, so you can open it at "M" and read every word up to "P". The first two are LinkedHashMap; the dictionary is TreeMap.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Insertion order: Entries come out in the order their keys were first put in.
Access order: Entries come out from least recently used to most recently used; reading an entry moves it to the end.
LRU cache: A fixed-size cache that, when full, throws away the entry that was used least recently.
Eviction: Removing an entry from a cache to make room for a new one.
NavigableMap: A sorted map interface with methods for nearest keys, ranges and reverse order. TreeMap implements it.
Range view: A map such as headMap(k) that shows only part of another map's keys, without copying them.
floor and ceiling key: The nearest key at or below a value, and the nearest key at or above it.

Step by step

01LinkedHashMap: a hash table with a thread through it

LinkedHashMap.Entry extends HashMap.Node and adds before and after. The map adds head, tail and a boolean accessOrder. HashMap's code calls three hooks that LinkedHashMap overrides: afterNodeAccess (move to tail in access order), afterNodeInsertion (maybe evict the eldest) and afterNodeRemoval (unlink).

So the hashing, buckets, resizing and treeify rules of Topic 9.4 all still apply; only the order of iteration and the extra links are new.

LinkedHashMap: a hash table with a thread through itdiagram

Rendering diagram…

02Insertion order vs access order

Insertion order (the default) answers "in what order did these keys first arrive?". Re-putting a key keeps its place; removing and putting it again moves it to the end.

Access order answers "which key was used least recently?". get moves the entry to the tail, so in access-order mode even reading changes the map's structure: it increments modCount, which matters when iterating (see Break it).

Main.javawhole filejava

Map<String, Integer> byInsertion = new LinkedHashMap<>();
Map<String, Integer> byAccess    = new LinkedHashMap<>(16, 0.75f, true);  // initialCapacity, loadFactor, accessOrder

03An LRU cache in five lines

Override removeEldestEntry in an access-ordered map. After each put of a new key, the map asks whether to drop the head (the least recently used entry); returning size() > capacity keeps the cache bounded.

Every operation stays O(1): the hash table finds the entry, the linked list moves or removes it. It isn't thread-safe; for a shared cache use a library like Caffeine, which also handles expiry and concurrency.

LruCache.javawhole filejava

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruCache(int capacity) {
        super(16, 0.75f, true);              // access order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;            // evict the least recently used
    }
}

An LRU cache in five linesdiagram

Rendering diagram…

04TreeMap: sorted keys in a red-black tree

Each TreeMap.Entry holds key, value, left, right, parent and a colour bit. get(k) starts at the root and compares: smaller goes left, larger goes right, 0 means found. The tree stays balanced (Topic 9.5), so that's at most about 2·log₂(n) steps.

The comparison replaces equals and hashCode entirely. Keys need a total ordering, and it should agree with equals (Topic 9.5's BigDecimal trap applies to maps too).

05Nearest-key and range queries

"What was the price in effect at 10:42?" Store price changes keyed by time and ask floorEntry(1042): the latest change at or before 10:42. "Which server owns this hash?" Ask ceilingEntry(hash) and wrap around to firstEntry() if it's null: that's a consistent-hashing ring (see the System Design course's consistent hashing topic, /topic/phase-8/consistent-hashing).

headMap(k) (keys < k), tailMap(k) (keys ≥ k) and subMap(a, b) ([a, b)) are live views; overloads with boolean flags choose inclusive or exclusive ends. Removing from a view removes from the map, which makes "delete everything older than t" a one-liner: map.headMap(t).clear().

Main.javawhole filejava

TreeMap<Integer, Double> priceAt = new TreeMap<>();
priceAt.put(900, 101.5);
priceAt.put(1015, 102.0);
priceAt.put(1100, 99.8);

priceAt.floorEntry(1042);      // 1015=102.0, the price in effect at 10:42
priceAt.headMap(1000).clear(); // drop history before 10:00

06Cost summary

LinkedHashMap: same O(1) expected costs as HashMap, iteration O(size), about 8 extra bytes per entry for the two links (with compressed references). TreeMap: O(log n) for get, put, remove and every navigation method; iteration O(n) in key order; about 40 bytes per entry.

A useful mental rule: if you ever sort a HashMap's keys every time you print or scan them, you wanted a TreeMap; if you sort them only once at the end, a HashMap plus one sort is usually cheaper.

Try it yourself

1
Change the cache's eviction
In the LRU example, change super(16, 0.75f, true) to super(16, 0.75f, false). Predict which key is evicted when /contact arrives (now /home, the oldest inserted: this is a FIFO cache, not LRU). Run and check.
2
Handle leaderboard ties
Add scores.put(820, "zoya") in the leaderboard example. Predict what happens to asha. Then change the map to TreeMap<Integer, List<String>> and use computeIfAbsent(score, k -> new ArrayList<>()).add(name).
3
Add a server to the ring
In the ring example, add ring.put(10, "server-D") before the first loop. Predict which users move to it (only those whose position falls between 300 and 10, wrapping past 360), then run.

Code & diagrams

Insertion order vs access order New tab

Expected output

insertion order: {tea=99, cake=4, chai=4}
access order:    {chai=4, tea=99, cake=4}
after re-adding tea: {cake=4, chai=4, tea=3}

An LRU cache with removeEldestEntry New tab

containsKey doesn't count as an access; get, put, getOrDefault and the compute methods do.

Expected output

[/home, /about, /menu]
after get /home: [/about, /menu, /home]
  evict /about
[/menu, /home, /contact]
[/home, /contact, /menu]
hit? false

TreeMap as a leaderboard and time series New tab

A real leaderboard must handle ties (two players with 820); key by score then name, or map each score to a list of names.

Expected output

top: 910=meera
leaderboard: {910=meera, 820=asha, 700=kabir, 640=ravi}
first score above 700: 820=asha
700 and up: {700=kabir, 820=asha, 910=meera}
between 650 and 850: {700=kabir, 820=asha}
price at 10:42: 102.0
price at 08:00: null
after dropping old history: {1015=102.0, 1100=99.8}
pollFirstEntry: 640=ravi, left [700, 820, 910]

A consistent-hashing ring with ceilingEntry New tab

Only the keys that belonged to the removed server moved. That is the whole point of consistent hashing.

Expected output

asha at 83 -> server-A
ravi at 74 -> server-A
meera at 132 -> server-B
kabir at 341 -> server-A
after removing server-B:
asha -> server-A
ravi -> server-A
meera -> server-C
kabir -> server-A

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Call get while iterating an access-ordered map

With Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true); holding a and b, run for (String k : lru.keySet()) System.out.println(k + "=" + lru.get(k));.

terminal

$ java Main

── what you'll see ──

a=1

Exception in thread "main" java.util.ConcurrentModificationException

at java.base/java.util.LinkedHashMap$LinkedHashIterator.nextNode(LinkedHashMap.java:1023)

at java.base/java.util.LinkedHashMap$LinkedKeyIterator.next(LinkedHashMap.java:1046)

at Main.main(Main.java:8)

Break #2

Ask for a backwards range

Call map.subMap(5, 1) on a TreeMap<Integer, String>.

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.lang.IllegalArgumentException: fromKey > toKey

at java.base/java.util.TreeMap$NavigableSubMap.<init>(TreeMap.java:1682)

at java.base/java.util.TreeMap$AscendingSubMap.<init>(TreeMap.java:2204)

at java.base/java.util.TreeMap.subMap(TreeMap.java:1225)

at java.base/java.util.TreeMap.subMap(TreeMap.java:1266)

at Main.main(Main.java:6)

Myth vs fact

Myth

LinkedHashMap is slower for lookups than HashMap.

Fact

Lookups use the same hash table, so they cost the same. Inserts and removes do a little extra link work, and each entry is 8 bytes bigger.

Myth

Putting an existing key again moves it to the end of a LinkedHashMap.

Fact

Only in access-order mode. In the default insertion order, an update keeps the entry's original position.

Myth

TreeMap is just a HashMap that sorts on output.

Fact

It's a completely different structure, a balanced binary search tree, with O(log n) operations and no hashing at all. Its keys never need hashCode.

Interview problem

The problem

Design an LRU cache with O(1) get and put

Implement LRUCache(int capacity) with int get(int key) (returns -1 if absent) and void put(int key, int value). When the cache is full, put evicts the least recently used key. Both operations must be O(1).

You're given

Capacity between 1 and 3,000; up to 200,000 operations.
get counts as a use; put on an existing key updates it and counts as a use.

The interviewer follows up

Why must the list be doubly linked?

Why store the key inside the list node?

How would you make it LFU (least frequently used)?

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
LinkedHashMap iteration is O(size), but HashMap iteration is O(capacity + size). For a map that's mostly empty slots, LinkedHashMap iterates faster despite its bigger entries.
▸
removeEldestEntry is called after every insertion of a new key (via afterNodeInsertion), not after updates. Its Javadoc explicitly allows modifying the map inside it, but the intended use is just to return a boolean.
▸
TreeMap.putAll from a SortedMap with the same comparator builds the tree in O(n) with buildFromSorted instead of n separate O(log n) inserts. Constructing new TreeMap<>(sortedMap) is the fast way to copy one.
▸
ConcurrentSkipListMap is the concurrent counterpart of TreeMap: a lock-free skip list with the same NavigableMap API and O(log n) expected time. There's no concurrent LinkedHashMap in the JDK; use Caffeine for concurrent LRU-like caches.

Remember this

1
**LinkedHashMap** extends HashMap. Every entry is a HashMap node plus two extra links, before and after, forming a doubly linked list through all entries in the map, with head and tail fields. Lookups still go through the hash table in O(1); iteration follows the list, so it's predictable and O(size).
2
By default the list is in insertion order: a new key goes to the tail, and putting an existing key again only updates the value without moving it. Pass true as the third constructor argument, new LinkedHashMap<>(16, 0.75f, true), and it switches to access order: every get, put, getOrDefault or compute on a key moves that entry to the tail. The head is then the least recently used entry.
3
After every insertion, LinkedHashMap calls the protected method removeEldestEntry(Map.Entry eldest); if it returns true, the head entry is removed. Override it to return size() > capacity on an access-ordered map and you have an LRU cache ("least recently used" eviction). This exact design is the DSA course's LRU Cache problem (/dsa/design-ds), where you also build the hash map plus linked list by hand.
4
**TreeMap is a red-black tree (Topic 9.5) whose nodes hold a key and a value. Keys are kept sorted** by compareTo or a Comparator; get, put, remove and containsKey are O(log n). null keys aren't allowed with natural ordering; null values are fine.
5
TreeMap implements NavigableMap, which adds the questions a hash map can't answer: firstKey/lastKey, floorKey(k) (largest ≤ k), ceilingKey(k) (smallest ≥ k), lowerKey, higherKey, the ...Entry versions of each, headMap(k), tailMap(k), subMap(a, b) (live views), descendingMap(), and pollFirstEntry()/pollLastEntry(). That's how you build leaderboards, time-series lookups ("the price in effect at 10:42"), interval schedules and the ring in consistent hashing.
6
Choosing: HashMap for pure lookups, LinkedHashMap when output order must match input order (JSON, reports, tests) or for an LRU cache, TreeMap for sorted keys or range and nearest-key queries. Since Java 21 both LinkedHashMap and TreeMap are SequencedMaps, with firstEntry, lastEntry, pollFirstEntry and reversed(), and LinkedHashMap gains putFirst and putLast (Topic 9.12).

Explain it without notes

How does LinkedHashMap maintain order, and what's the difference between insertion and access order?

Implement an LRU cache in Java and explain the time complexity of each operation.

When would you choose TreeMap over HashMap? Give two concrete use cases.

What are floorKey, ceilingKey, headMap and subMap, and are the range methods copies?

Practice

Use a LinkedHashMap<String, Integer> to count words in "the cat and the hat and the bat" and print the counts in the order each word first appeared.

Build a booking checker with a TreeMap<Integer, Integer> mapping start time to end time. Add bookings 900-1000 and 1100-1200, then check whether 930-1030, 1000-1100 and 1150-1300 can be booked (no overlap), using floorEntry and ceilingEntry. Print each result.

Write a FIFO cache of capacity 2 (evicts the oldest inserted key, not the least recently used) using LinkedHashMap and removeEldestEntry. Put a, b, read a, put c, then print the keys.

Trade-offs

↔
LinkedHashMap buys a predictable order for a little memory. Use it whenever output order matters (APIs, reports, tests); the cost is rarely noticeable.
↔
TreeMap gives sorted order and range queries but each operation is O(log n) with pointer-chasing; for pure lookups a HashMap is several times faster.
↔
A LinkedHashMap LRU cache is perfect for a single thread. Shared caches need concurrency, expiry and statistics, which is why production code uses Caffeine or a similar library rather than synchronising a LinkedHashMap.

Done when you can

Done when you can explain how LinkedHashMap keeps order and switch it to access order.
Done when you can write an LRU cache with removeEldestEntry and state its O(1) costs.
Done when you can use floorEntry, ceilingEntry, headMap, tailMap and subMap on a TreeMap.
Done when you know range views are live and how to clear old entries with one call.
Done when you can pick between HashMap, LinkedHashMap and TreeMap for a given task.

Command Palette

Words you'll meet

Step by step

01LinkedHashMap: a hash table with a thread through it

02Insertion order vs access order

03An LRU cache in five lines

04TreeMap: sorted keys in a red-black tree

05Nearest-key and range queries

06Cost summary

Try it yourself

Change the cache's eviction

Handle leaderboard ties

Add a server to the ring

Code & diagrams

Break it on purpose

Call get while iterating an access-ordered map

Ask for a backwards range

Myth vs fact

Interview problem

Design an LRU cache with O(1) get and put

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can