TreeMap, LinkedHashMap and Building an LRU Cache

HashMap answers "what is the value for this key?" and nothing else. TreeMap and LinkedHashMap each add an ordering guarantee, for very different costs, and one of them gives you a production-grade LRU cache almost for free.

TreeMap#

A TreeMap is a self-balancing binary search tree — specifically a red-black tree, which keeps its height within 2·log(n+1) by recolouring and rotating on insertion and deletion. That bound is what makes every operation O(log n) in the worst case, not just on average.

NavigableMap<LocalDate, BigDecimal> prices = new TreeMap<>();
prices.put(LocalDate.of(2026, 1, 1), new BigDecimal("100"));
prices.put(LocalDate.of(2026, 4, 1), new BigDecimal("110"));
prices.put(LocalDate.of(2026, 7, 1), new BigDecimal("125"));
 
// The price in effect on a given date: the latest entry at or before it.
Map.Entry<LocalDate, BigDecimal> effective = prices.floorEntry(LocalDate.of(2026, 5, 15));
// -> 2026-04-01 = 110
 
// Everything in a window, as a live view
SortedMap<LocalDate, BigDecimal> q2 = prices.subMap(
        LocalDate.of(2026, 4, 1), LocalDate.of(2026, 7, 1));
 
prices.firstKey();          // earliest
prices.lastEntry();         // latest entry
prices.ceilingKey(date);    // smallest key >= date
prices.higherKey(date);     // smallest key strictly > date
prices.descendingMap();     // reversed view
prices.headMap(date, true); // everything up to and including date

That floorEntry call is the shape of query a HashMap simply cannot answer — it would require scanning every key. Effective-dated pricing, rate tables, time-bucketed metrics, IP range lookups and leaderboard rank queries are all TreeMap problems.

TreeMap also rejects null keys (there is nothing to compare) while HashMap allows one. And a TreeMap with a comparator that reads mutable state produces a tree whose ordering silently becomes invalid, which manifests as entries that are present but unfindable — the sorted-collection analogue of the mutable-key bug.

LinkedHashMap#

LinkedHashMap extends HashMap and adds before and after pointers to each entry, weaving a doubly-linked list through them. Lookups still go through the hash table, so they stay O(1); the list exists only to define iteration order.

// Insertion order (default). Re-putting an existing key does NOT move it.
Map<String, Integer> insertion = new LinkedHashMap<>();
 
// Access order. get() and put() move the entry to the END of the list.
Map<String, Integer> access = new LinkedHashMap<>(16, 0.75f, true);
 
access.put("a", 1); access.put("b", 2); access.put("c", 3);
access.get("a");
access.keySet();   // [b, c, a] — "a" moved to the end

The cost over a plain HashMap is two extra references per entry (about 8–16 bytes) and a small constant on each write. In exchange, iteration is deterministic — which matters more than it sounds for API responses, serialised configuration, and any test that asserts on order.

The LRU cache#

Access order plus one overridable hook is a complete LRU implementation:

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
 
    public LruCache(int capacity) {
        // initialCapacity sized to avoid a resize, loadFactor default, accessOrder TRUE
        super((int) (capacity / 0.75f) + 1, 0.75f, true);
        this.capacity = capacity;
    }
 
    /**
     * Called by LinkedHashMap after every insertion. Returning true removes
     * the eldest entry — which, in access order, is the least recently used.
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

LruCache<String, String> cache = new LruCache<>(3);
cache.put("a", "1"); cache.put("b", "2"); cache.put("c", "3");
cache.get("a");                 // "a" becomes most recently used
cache.put("d", "4");            // evicts "b", the least recently used
cache.keySet();                 // [c, a, d]

Both get and put are O(1), because the hash table does the lookup and the list surgery is a constant number of pointer updates. This is the standard answer to "implement an LRU cache" in an interview, and being able to write it from memory — including the three-argument constructor and the removeEldestEntry signature — is worth the five minutes it takes to learn.

If the interviewer asks you to implement it without LinkedHashMap, the structure is the same: a HashMap from key to node, plus a hand-rolled doubly-linked list with sentinel head and tail nodes so that unlinking needs no null checks.

Other uses for insertion order#

LinkedHashMap is not only for caches. Insertion order is the right default whenever a map becomes output:

// A JSON response whose field order should not change between deploys
Map<String, Object> body = new LinkedHashMap<>();
body.put("id", order.id());
body.put("status", order.status());
body.put("total", order.total());
 
// Collectors that preserve encounter order
Map<String, Long> byRegion = orders.stream()
        .sorted(comparing(Order::region))
        .collect(groupingBy(Order::region, LinkedHashMap::new, counting()));

LinkedHashSet is the same idea for sets, and is the natural way to deduplicate while preserving order — something HashSet cannot do and TreeSet does only by sorting.

When to use a real cache library#

The LinkedHashMap LRU is correct and appropriate for a small, single-threaded, bounded cache. Beyond that, Caffeine is the answer, and knowing why is a good senior-level signal:

The eviction-quality row is the interesting one. Strict LRU performs badly under a scan — one pass over a large dataset evicts the entire working set. W-TinyLFU tracks frequency as well as recency and resists that, which is why Caffeine typically beats an LRU of the same size on production traffic.

What gets asked#

Two questions dominate: "implement an LRU cache" and "when would you use a TreeMap?" For the first, write the LinkedHashMap version and mention the thread-safety caveat. For the second, give a range query — floorEntry on an effective-dated price table is a concrete, memorable example that shows you have used it for something real.