LinkedHashMap and TreeMap in Depth

You already know how HashMap works. You know about buckets, hash functions, and linked lists inside those buckets. You know that HashMap gives you blazing fast O(1) average lookups. But here is the catch: if you iterate over a HashMap, the order you get your entries back is completely unpredictable. You put entries in one order and they come out in a different order entirely. For a lot of use cases that is perfectly fine. But sometimes you need order. Sometimes you need to know which element was inserted first, or which element was used most recently, or you need all your keys sorted so you can answer questions like "what is the nearest key below 24?" That is exactly where LinkedHashMap and TreeMap come in.

This article is going to cover both of them completely. You will understand how LinkedHashMap extends HashMap with just two extra pointers to give you ordering, how to flip a single constructor flag to turn it into an LRU cache, and then how TreeMap uses a Red Black tree to keep every key sorted at all times. By the end you will also know every method in SortedMap and NavigableMap, because TreeMap implements both of those interfaces and they are where all the real power lives.

---

LinkedHashMap: HashMap with Memory

The simplest way to think about LinkedHashMap is this: it is a HashMap that also remembers the order in which you inserted things. The HashMap does not remember. LinkedHashMap does.

To understand how it achieves this, you need to look at what is actually different inside. When you insert an entry into a regular HashMap, the Node that gets created has four fields: hash, key, value, and next. The next pointer is how chaining works inside a single bucket. That is all HashMap needs.

LinkedHashMap extends HashMap. Its entry nodes inherit everything from HashMap.Node but add two more fields: before and after. Those two extra fields are what turn the flat bucket structure of HashMap into a complete doubly linked list that runs across the entire map.

Here is what the node looks like under the hood:

// Inside LinkedHashMap (simplified)
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before;  // points to the previous entry in insertion sequence
    Entry<K,V> after;   // points to the next entry in insertion sequence

    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Every single entry you ever put into a LinkedHashMap gets wired into this doubly linked list. The map keeps a head reference and a tail reference. The head is the oldest entry, the tail is the newest. Every new entry that comes in gets appended at the tail, and its before pointer gets connected back to the previous tail, and the previous tail's after pointer gets connected forward to the new entry.

Let's walk through a concrete example. You insert five entries into a LinkedHashMap: key 1 with value A, key 21 with value B, key 23 with value C, key 141 with value D, and key 25 with value E.

The HashMap part works exactly as you already know. Hash code gets computed, mod by array size, entry lands in some bucket. Maybe key 1 and key 21 both hash to bucket 0 so they chain together. Maybe key 23 and key 25 both end up in bucket 1. The bucket structure has nothing to do with insertion order.

But at the same time, the doubly linked list is being maintained. After all five insertions the list looks like this:

HEAD -> [1|A] <-> [21|B] <-> [23|C] <-> [141|D] <-> [25|E] -> TAIL

Before of the first entry is null. After of the last entry is null. Every entry in between has both pointers filled in.

When you iterate over the LinkedHashMap, Java does not walk the bucket array. It walks this linked list starting from head and following each after pointer until it reaches null. That is why you always get entries back in insertion order, regardless of how entries are distributed across buckets.

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

public class LinkedHashMapInsertionOrder {
    public static void main(String[] args) {
        Map<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "A");
        map.put(21, "B");
        map.put(23, "C");
        map.put(141, "D");
        map.put(25, "E");

        // Iteration always follows insertion order
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
        // Output: 1->A, 21->B, 23->C, 141->D, 25->E
        // Every time. Guaranteed.
    }
}

Compare this to a regular HashMap with the exact same insertions. A HashMap might give you back 1, 21, 23, 25, 141 or some entirely different permutation depending on how the hash codes distribute across buckets. With LinkedHashMap you always get exactly 1, 21, 23, 141, 25 because that is the order you inserted them.

---

Access Order: Moving Recently Used Entries to the Back

Insertion order is the default behavior. But LinkedHashMap has a second mode called access order that is even more interesting. You enable it by passing true as the third argument to a specific constructor.

// Signature of the constructor that enables access order
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

When accessOrder is false (the default), you get insertion order. When you set accessOrder to true, the map reorders entries every time you call get or put on an existing key. Specifically it moves that entry to the tail of the doubly linked list.

Think about what this means. The tail always holds the most recently touched entry. The head always holds the entry that has not been touched for the longest time. Least recently used lives at the head, most recently used lives at the tail.

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

public class AccessOrderDemo {
    public static void main(String[] args) {
        // The third argument 'true' enables access order mode
        Map<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);

        map.put(1, "A");
        map.put(21, "B");
        map.put(23, "C");
        map.put(141, "D");
        map.put(25, "E");

        // Right now the order is 1, 21, 23, 141, 25 (insertion order)

        // Now access key 23
        map.get(23);

        // 23 just moved to the tail because it was accessed
        // New order: 1, 21, 141, 25, 23
        System.out.println(map);
        // {1=A, 21=B, 141=D, 25=E, 23=C}
    }
}

Internally when you call get with accessOrder set to true, LinkedHashMap finds the entry as usual using the bucket structure, returns its value, but then also calls a method that unlinks that entry from its current position in the doubly linked list and relinks it at the tail. The before and after pointers of the neighbors get updated to close the gap, and the entry's own pointers get updated to connect to the old tail and the null end of the list.

This is a completely free operation in terms of algorithmic complexity. Relinking pointers in a doubly linked list is O(1). You pay no extra cost beyond the normal O(1) HashMap get.

---

Building an LRU Cache with LinkedHashMap

Now here is where access order becomes genuinely powerful. An LRU cache is a fixed size cache that evicts the least recently used entry whenever it gets full. That is exactly the behavior you get from access order mode: the head is always the least recently used entry.

LinkedHashMap has a protected method called removeEldestEntry that you can override. After every put operation, LinkedHashMap calls this method and passes the current head entry (the eldest, the least recently used one). If your override returns true, LinkedHashMap automatically removes that head entry. This is your eviction hook.

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

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

    public LRUCache(int capacity) {
        // initialCapacity matches desired cache size
        // loadFactor 0.75 is standard
        // accessOrder true is what makes this an LRU cache
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    // LinkedHashMap calls this after every put()
    // 'eldest' is the head of the doubly linked list (least recently used entry)
    // Return true to evict it, false to keep it
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        cache.put(1, "A");  // Cache: [1=A]
        cache.put(2, "B");  // Cache: [1=A, 2=B]
        cache.put(3, "C");  // Cache: [1=A, 2=B, 3=C]  (1 is LRU, 3 is MRU)

        cache.get(1);       // Access 1 -> moves to tail
                            // Cache: [2=B, 3=C, 1=A]  (2 is now LRU)

        cache.put(4, "D");  // Cache is full (size would be 4 > capacity 3)
                            // removeEldestEntry returns true
                            // 2=B gets evicted (it's at the head, least recently used)
                            // Cache: [3=C, 1=A, 4=D]

        System.out.println(cache);
        // Output: {3=C, 1=A, 4=D}
    }
}

This is genuinely useful code. Interviewers love asking you to implement an LRU cache. The naive approach involves managing a HashMap and a doubly linked list yourself, keeping them in sync manually, which is painful and error prone. The elegant approach is exactly what you see above: extend LinkedHashMap, pass accessOrder true, override removeEldestEntry to return size() > capacity, and you are done in about fifteen lines.

---

Time Complexity and Thread Safety of LinkedHashMap

LinkedHashMap has exactly the same time complexity as HashMap. Average O(1) for get, put, and remove. Worst case O(n) if every key hashes to the same bucket, or O(log n) if that bucket has converted to a tree (which happens when a bucket exceeds eight elements).

The extra pointer maintenance for the doubly linked list is O(1) work on every operation and does not change the overall complexity class.

Like HashMap, LinkedHashMap is not thread safe. Multiple threads accessing and modifying a LinkedHashMap concurrently without synchronization will produce data corruption and incorrect results. The standard way to make it thread safe is:

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

// Wrapping in a synchronized map adds a mutex around every operation
Map<String, Integer> safeMap = Collections.synchronizedMap(new LinkedHashMap<>());

What Collections.synchronizedMap actually does is wrap your map in a SynchronizedMap object. Every method on that wrapper acquires the same monitor lock before delegating to the underlying LinkedHashMap. So your calls to put and get on safeMap are effectively synchronized blocks that then call the real put and get on the LinkedHashMap. Simple and effective.

There is no ConcurrentLinkedHashMap in the standard library the way there is a ConcurrentHashMap. If you need high concurrency access with ordering guarantees, you either synchronize manually or look at third party libraries.

---

TreeMap: Always Sorted, Always Balanced

Now let's talk about TreeMap. This is a completely different beast from HashMap and LinkedHashMap. It does not use buckets. It does not use a hash function at all. It stores every entry in a Red Black tree, which is a self balancing binary search tree.

Before getting into TreeMap specifically, look at where it sits in the interface hierarchy:

Map
 └── SortedMap
      └── NavigableMap
           └── TreeMap (concrete class)

Map you already know. SortedMap extends Map and adds methods for working with the natural ordering of keys. NavigableMap extends SortedMap and adds even more powerful navigation methods for finding entries relative to a given key. TreeMap is the concrete class that implements all of these.

A Red Black tree is a binary search tree with some additional rules that keep it balanced. In any binary search tree, the left child of a node is always smaller than the node, and the right child is always greater. This property means you can search, insert, or delete in O(log n) time because at each step you eliminate half the remaining candidates. The balancing rules of a Red Black tree guarantee that the tree never degenerates into a linked list even if you insert elements in sorted order.

Example: TreeMap with keys 10, 20, 30, 40, 50

              [30]  (Black)
             /    \
          [20]    [40]  (Black)
          /          \
       [10]          [50]

Every node in a TreeMap has five fields: key, value, parent, left, and right. When you insert a new entry, TreeMap compares the new key against the root, goes left if smaller or right if larger, and keeps going until it finds the correct empty slot. Then it may rotate or recolor nodes to maintain the Red Black balance properties.

The consequence of using a tree instead of a hash table is that every operation costs O(log n). Get, put, remove, and containsKey are all guaranteed O(log n). There is no amortized average, no worst case variation. Every operation is O(log n) every time. This is slower than HashMap for large maps but the trade off is that your keys are always in sorted order.

import java.util.TreeMap;
import java.util.Map;
import java.util.Comparator;

public class TreeMapBasics {
    public static void main(String[] args) {
        // Natural ordering (ascending for integers)
        TreeMap<Integer, String> ascending = new TreeMap<>();
        ascending.put(13, "thirteen");
        ascending.put(5, "five");
        ascending.put(21, "twenty-one");  // note: hyphens only in strings, not in prose
        ascending.put(11, "eleven");

        System.out.println("Natural order: " + ascending);
        // {5=five, 11=eleven, 13=thirteen, 21=twenty one}

        // Custom comparator for descending order
        TreeMap<Integer, String> descending = new TreeMap<>(
            Comparator.reverseOrder()
            // or: (key1, key2) -> key2 - key1
        );
        descending.put(13, "thirteen");
        descending.put(5, "five");
        descending.put(21, "twenty one");
        descending.put(11, "eleven");

        System.out.println("Descending order: " + descending);
        // {21=twenty one, 13=thirteen, 11=eleven, 5=five}
    }
}

One critical restriction: TreeMap does not allow null keys. When you call put with a null key, you get a NullPointerException immediately. The reason is straightforward. TreeMap needs to compare keys against each other to know where in the tree to place them. You cannot compare null against another key. HashMap allows one null key because it special cases it to bucket 0. TreeMap has no such special case. TreeMap does allow null values though; only the key is forbidden.

---

SortedMap Methods: headMap and tailMap

Because TreeMap implements SortedMap, it inherits four particularly useful methods for working with ranges of keys.

The first two are headMap and tailMap. Think of them as "give me everything before this key" and "give me everything from this key onward."

import java.util.TreeMap;
import java.util.SortedMap;

public class SortedMapMethods {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(5, "five");
        map.put(11, "eleven");
        map.put(13, "thirteen");
        map.put(21, "twenty one");

        // headMap: everything strictly BEFORE the given key (exclusive)
        SortedMap<Integer, String> head = map.headMap(13);
        System.out.println("headMap(13): " + head);
        // {5=five, 11=eleven}
        // 13 itself is NOT included because headMap is exclusive on the to-key

        // tailMap: everything FROM the given key onward (inclusive)
        SortedMap<Integer, String> tail = map.tailMap(13);
        System.out.println("tailMap(13): " + tail);
        // {13=thirteen, 21=twenty one}
        // 13 itself IS included because tailMap is inclusive on the from-key

        // firstKey and lastKey
        System.out.println("First key: " + map.firstKey());  // 5
        System.out.println("Last key: " + map.lastKey());    // 21
    }
}

The inclusion rule is worth memorizing because it trips people up in interviews. headMap is exclusive on its boundary: headMap(13) does NOT include 13. tailMap is inclusive on its boundary: tailMap(13) DOES include 13. The NavigableMap interface adds overloaded versions where you can explicitly pass a boolean to control inclusion, which is more flexible.

---

NavigableMap Methods: The Real Power of TreeMap

NavigableMap is where TreeMap gets genuinely impressive. It adds over a dozen methods for finding entries relative to a given key. Let's go through all of them with a working example.

import java.util.TreeMap;
import java.util.Map;

public class NavigableMapMethods {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1, "A");
        map.put(21, "B");
        map.put(23, "C");
        map.put(25, "D");
        map.put(141, "E");

        // The map in sorted order: 1, 21, 23, 25, 141

        // lowerEntry: entry with the greatest key STRICTLY LESS THAN the given key
        System.out.println(map.lowerEntry(23));   // 21=B
        System.out.println(map.lowerKey(23));     // 21 (key only, no value)

        // floorEntry: entry with the greatest key LESS THAN OR EQUAL TO the given key
        System.out.println(map.floorEntry(24));   // 23=C  (24 not present, so return next lower)
        System.out.println(map.floorEntry(23));   // 23=C  (23 is present, return it directly)
        System.out.println(map.floorKey(24));     // 23 (key only)

        // ceilingEntry: entry with the smallest key GREATER THAN OR EQUAL TO the given key
        System.out.println(map.ceilingEntry(23)); // 23=C  (23 is present, return it)
        System.out.println(map.ceilingEntry(24)); // 25=D  (24 not present, return next higher)
        System.out.println(map.ceilingKey(24));   // 25 (key only)

        // higherEntry: entry with the smallest key STRICTLY GREATER THAN the given key
        System.out.println(map.higherEntry(23));  // 25=D
        System.out.println(map.higherEntry(25));  // 141=E
        System.out.println(map.higherKey(23));    // 25 (key only)

        // firstEntry and lastEntry
        System.out.println(map.firstEntry());     // 1=A
        System.out.println(map.lastEntry());      // 141=E

        // pollFirstEntry: removes and returns the smallest entry
        System.out.println(map.pollFirstEntry()); // 1=A  (1 is now gone from the map)

        // pollLastEntry: removes and returns the largest entry
        System.out.println(map.pollLastEntry());  // 141=E  (141 is now gone from the map)

        // What remains in the map now: 21, 23, 25
        System.out.println(map); // {21=B, 23=C, 25=D}
    }
}

The distinction between lower/floor and ceiling/higher is the key thing to get right. Lower and higher are strict: they never return the key you asked about even if it exists. Floor and ceiling are inclusive: they return the exact key if it exists, and fall back to the nearest neighbor only if the exact key is not there.

Think of floor and ceiling like rounding. Floor rounds down (returns the key itself if present, otherwise the next smaller one). Ceiling rounds up (returns the key itself if present, otherwise the next larger one). Lower and higher never round to the exact key; they always step away from it.

All of these methods return null when no qualifying entry exists. If you call lowerEntry on a key that is smaller than or equal to the smallest key in the map, you get null back. Always check for null before using the result.

---

descendingMap and Key Set Methods

TreeMap has two more methods that are useful for reversing the view of your data.

import java.util.TreeMap;
import java.util.NavigableMap;
import java.util.NavigableSet;

public class DescendingDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(1, "A");
        map.put(21, "B");
        map.put(23, "C");
        map.put(25, "D");
        map.put(141, "E");

        // descendingMap: returns a NavigableMap view in reverse order
        // Does NOT copy the data; changes to either map reflect in the other
        NavigableMap<Integer, String> reversed = map.descendingMap();
        System.out.println("Descending: " + reversed);
        // {141=E, 25=D, 23=C, 21=B, 1=A}

        // keySet: returns keys in ascending order
        System.out.println("Key set: " + map.keySet());
        // [1, 21, 23, 25, 141]

        // descendingKeySet: returns keys in descending order
        NavigableSet<Integer> descKeys = map.descendingKeySet();
        System.out.println("Descending keys: " + descKeys);
        // [141, 25, 23, 21, 1]
    }
}

An important implementation detail: descendingMap returns a view, not a copy. Both the original map and the descending view reflect the same underlying Red Black tree. If you add or remove entries through either reference, both see the change. This is memory efficient but you need to be aware of it.

The NavigableMap version of subMap also lets you explicitly control whether each boundary is inclusive or exclusive:

// subMap with explicit inclusion flags
// from 21 (inclusive) to 25 (exclusive)
System.out.println(map.subMap(21, true, 25, false));
// {21=B, 23=C}

// from 21 (inclusive) to 25 (inclusive)
System.out.println(map.subMap(21, true, 25, true));
// {21=B, 23=C, 25=D}

---

HashMap vs LinkedHashMap vs TreeMap: Choosing the Right One

These three maps solve different problems. Knowing which to reach for is the mark of someone who actually understands the data structures rather than just knowing the API.

Feature	HashMap	LinkedHashMap	TreeMap
Underlying structure	Bucket array with chained nodes	Bucket array plus doubly linked list	Red Black tree
Iteration order	Unpredictable	Insertion order or access order	Always sorted ascending by key
get / put / remove	O(1) average	O(1) average	O(log n) guaranteed
Null keys	One null key allowed	One null key allowed	No null keys ever
Null values	Allowed	Allowed	Allowed
Memory overhead	Lowest	Medium (two extra pointers per node)	Medium (parent, left, right per node)
Thread safe	No	No	No
Best for	General fast key value storage	Ordered cache, LRU, config with insertion order	Range queries, sorted output, nearest neighbor lookup

Reach for HashMap by default when you just need fast key value storage and do not care about order. Reach for LinkedHashMap when you need insertion order preserved, or when you are building an LRU cache. Reach for TreeMap when you need your keys sorted, when you need range queries (give me everything between key 10 and key 50), or when you need nearest neighbor lookups (what is the largest key that does not exceed 37).

---

Interview Questions and Pitfalls

Interview questions about these two classes come up regularly. Here are the exact questions you should be ready for.

Why does LinkedHashMap maintain insertion order but HashMap does not?

HashMap only stores the before and after pointers it needs for chaining within a single bucket (the next pointer). It has no global sequence linking entries across buckets. LinkedHashMap adds before and after pointers to every entry so that all entries across all buckets form a single doubly linked list. Iteration walks that linked list from head to tail, which is insertion order.

What is the difference between insertion order and access order in LinkedHashMap?

Insertion order (the default, accessOrder is false) means entries always iterate in the sequence they were first put into the map. Updating an existing key's value does not move it. Access order (accessOrder is true) means that every get or put on an existing key moves that entry to the tail of the linked list. The tail is the most recently used. The head is the least recently used.

How do you implement an LRU cache using LinkedHashMap?

Extend LinkedHashMap, pass accessOrder true to the super constructor, set a capacity field, and override removeEldestEntry to return size() > capacity. Every put call that exceeds capacity will automatically evict the head entry, which is the least recently used entry. This is O(1) for all operations.

What is the time complexity of TreeMap operations?

O(log n) guaranteed for get, put, remove, and containsKey. There is no amortized O(1) like HashMap. Every single operation traverses the Red Black tree, which has a height of at most 2 * log(n).

Why does TreeMap not allow null keys?

TreeMap needs to compare every key against others to determine its position in the tree. Comparing null against a real key would throw a NullPointerException. HashMap special cases null to bucket 0 and never compares it. TreeMap has no such special case.

What is the difference between lowerEntry and floorEntry?

lowerEntry returns the entry with the greatest key strictly less than the given key. It never returns the given key itself even if it exists. floorEntry returns the entry with the greatest key less than or equal to the given key. If the given key exists in the map, floorEntry returns it directly. If it does not exist, floorEntry returns the next smaller one.

What is the difference between headMap and tailMap?

headMap(k) returns a view of all entries with keys strictly less than k. The upper boundary is exclusive. tailMap(k) returns a view of all entries with keys greater than or equal to k. The lower boundary is inclusive.

What interfaces does TreeMap implement?

TreeMap implements NavigableMap which extends SortedMap which extends Map. This means it gets the full set of sorted and navigable operations on top of the base Map interface.

What does pollFirstEntry do and how is it different from firstEntry?

firstEntry returns the entry with the smallest key but leaves it in the map. pollFirstEntry also returns the entry with the smallest key but removes it from the map as a side effect. Poll is a destructive read.

Can TreeMap be used for reverse sorted order?

Yes. Pass a comparator to the TreeMap constructor. Using Comparator.reverseOrder() or writing (k1, k2) -> k2 - k1 will store entries in descending key order. Alternatively you can call descendingMap() on an existing TreeMap to get a reverse ordered view of the same data without copying anything.

Is LinkedHashMap thread safe? What about TreeMap?

Neither is thread safe. Both require external synchronization for concurrent access. You can wrap either with Collections.synchronizedMap() to get basic thread safety, which adds a synchronized block around every method. For high concurrency HashMap use cases, ConcurrentHashMap is the right choice. There is no ConcurrentLinkedHashMap or ConcurrentTreeMap in the standard Java library.

---

Putting It All Together

You now have a complete picture of the Map family in Java. HashMap gives you raw speed with no ordering guarantees. LinkedHashMap gives you the same speed with the bonus that you can iterate in insertion order or in access order for LRU caching. TreeMap gives you sorted keys with powerful range and navigation queries at the cost of O(log n) per operation instead of O(1).

The choice between them is rarely about performance at small scale. A TreeMap with a thousand entries is not meaningfully slower than a HashMap with the same data. The choice is about semantics: what guarantees do you need your data structure to make? If you need sorted iteration, you need TreeMap. If you need LRU eviction, you need LinkedHashMap with access order. If you need neither, HashMap is your friend.

The NavigableMap methods like floorEntry, ceilingEntry, lowerEntry, and higherEntry are not just academic. They appear constantly in competitive programming problems and in real systems that need to find the closest matching entry for a given input. Once you internalize the floor vs lower and ceiling vs higher distinction, these methods become natural tools rather than things you have to look up every time.

Next up is the Set family: HashSet, LinkedHashSet, and TreeSet. If you understood HashMap, HashSet will take you about five minutes because HashSet is literally just a HashMap where you only care about the keys and always store a dummy object as the value. The implementation is almost entirely shared. That is how clean Java's collection design is.