TreeMap's red-black tree ordering and NavigableMap methods, LinkedHashMap's ordering layer on top of HashMap, and the removeEldestEntry() trick that turns it into a working LRU cache in four lines.
Published September 22, 2026
HashMap Deep Dive covered the workhorse. These two exist because sometimes you need something HashMap fundamentally cannot give you: order.
TreeMap is backed by a red-black tree — a self-balancing binary search tree that guarantees O(log n) worst case for get, put, and remove, versus HashMap's O(1) average but O(log n) worst case (post-Java-8 treeification) or theoretically O(n) in pre-8 versions. The tradeoff for that guarantee: every operation pays the log n cost, always — there's no O(1) fast path.
Ordering comes from either the key's natural ordering (Comparable) or a supplied Comparator:
TreeMap<String, Integer> byNaturalOrder = new TreeMap<>(); // uses String's natural (alphabetical) order
TreeMap<String, Integer> byLength = new TreeMap<>(Comparator.comparingInt(String::length));
If you only needed some ordering, LinkedHashMap would suffice and be faster. TreeMap earns its keep through NavigableMap:
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "a"); map.put(20, "b"); map.put(30, "c");
map.floorKey(25); // 20 — greatest key <= 25
map.ceilingKey(25); // 30 — smallest key >= 25
map.higherKey(20); // 30 — smallest key strictly > 20
map.lowerKey(20); // 10 — greatest key strictly < 20
map.headMap(20); // {10=a} — all entries with key < 20
map.tailMap(20); // {20=b, 30=c} — all entries with key >= 20
These are the reason to reach for TreeMap: range queries and "nearest key" lookups that would require a manual scan (and sort) with HashMap. A common real use: an event-scheduling system finding "the next event after time T" — ceilingKey(T) does it in O(log n) directly.
LinkedHashMap extends HashMap and layers a doubly-linked list through all its entries, threading through the same bucket array HashMap already uses. Every put/get still gets HashMap's O(1) average bucket lookup — the linked list only exists to remember order, it doesn't change how entries are located.
By default, iteration order matches insertion order. A constructor flag switches to access order:
new LinkedHashMap<>(16, 0.75f, true); // accessOrder = true
With accessOrder=true, every get() (and put() on an existing key) moves that entry to the end of the internal linked list — the most-recently-used entry is always last, the least-recently-used is always first. This one flag is what makes LinkedHashMap the basis of a working LRU cache.
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
LRUCache(int capacity) {
super(16, 0.75f, true); // access-order mode
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity; // true = evict the least-recently-used entry
}
}
removeEldestEntry() is called automatically after every put(), with the current least-recently-used entry passed in — returning true tells LinkedHashMap to evict it. This is the entire mechanism: no manual list management, no separate eviction thread, just one overridden method riding on top of access-order tracking that already existed.
These are thin wrappers around TreeMap/HashMap/LinkedHashMap internally (the value is a dummy constant), so the tradeoffs transfer directly: HashSet — fastest, no order. LinkedHashSet — HashSet speed, insertion-order iteration. TreeSet — sorted iteration and NavigableSet range operations (floor, ceiling, ...), at O(log n) per operation.
Q: Why is TreeMap's worst case O(log n) while HashMap's worst case (pre-treeification) was O(n)? A: A red-black tree is self-balancing by construction — every insert/delete includes rebalancing operations that maintain a bounded height (O(log n)) as an invariant. A HashMap bucket, pre-Java-8, was just a linked list with no balancing at all — a bucket with n colliding entries was genuinely O(n) to scan, which is exactly why treeification (converting an overloaded bucket into a red-black tree) was added in Java 8.
Q: Can you use a mutable key in a TreeMap?
A: Even more dangerous than in HashMap — if a key's compareTo()-relevant state changes after insertion, the tree's internal ordering invariant is silently violated, and further inserts/lookups can behave unpredictably (not just "can't find it," but potentially inconsistent tree structure). Keys used in ordered structures should be immutable even more strictly than HashMap keys.
Q: What happens if accessOrder=true and you iterate a LinkedHashMap with a plain for-each loop?
A: Iterating itself doesn't call get(), so it doesn't reorder anything mid-iteration — order-changing reads specifically come from get(key)/getOrDefault() calls, not from iterating the map's entry set. This matters because iterating while separately calling get() on entries inside the loop could reorder the very structure you're iterating — a subtle ConcurrentModificationException risk worth knowing about.
Q: Why not just use a HashMap plus a separate sorted List if you need both fast lookup and order?
A: You'd have to keep both structures manually synchronized on every insert/remove — real duplication of bookkeeping and a source of subtle bugs if one update path forgets to touch both. TreeMap/LinkedHashMap give you both guarantees from a single structure with a single source of truth.