Ordered and Sorted Maps

LinkedHashMap for insertion order and LRU caches, TreeMap for sorted keys and range queries.

Advanced11 min read

Read these first

How HashMap Works Inside

Why this matters

LinkedHashMap gives you a working LRU cache by overriding one method, which is a genuinely useful piece of knowledge.
TreeMap's navigation methods solve "find the nearest value at or below this" problems that a hash map cannot express at all.
Interviews frequently ask you to implement an LRU cache, and the one-method version is a strong answer when paired with the manual one.

table — array of buckets

bucket 0empty

bucket 1"asha" → 30

bucket 5 — collision chain

"ravi" → 24next →

"neha" → 29next → null

bucket 9 — treeified

Red-black treeMore than 8 entries: lookup becomes O(log n)

Bucket index comes from the key's hash, not its insertion order — which is why HashMap iteration has no predictable sequence.

The hash picks a bucket. Keys that land in the same bucket form a short list, and once a bucket grows past eight entries it becomes a balanced tree so lookups stay fast.

LinkedHashMap

It keeps everything HashMap does and adds a doubly linked list across entries.

Java

Map<String, Integer> insertion = new LinkedHashMap<>();
insertion.put("carl", 3);
insertion.put("ana", 1);
insertion.put("bob", 2);
insertion.put("carl", 30);              // updating does not change position

System.out.println(insertion);           // {carl=30, ana=1, bob=2}

Iteration follows insertion order, and re-putting an existing key leaves its position alone. The cost is two extra references per entry and slightly slower insertion.

Access order

The three-argument constructor switches from insertion order to access order, where reading an entry moves it to the end.

Java

Map<String, Integer> accessed = new LinkedHashMap<>(16, 0.75f, true);
accessed.put("a", 1);
accessed.put("b", 2);
accessed.put("c", 3);

accessed.get("a");                       // "a" moves to the end

System.out.println(accessed);            // {b=2, c=3, a=1}

The head of the list is now the least recently used entry, which is exactly what a cache needs to evict.

An LRU cache in one override

removeEldestEntry is called after every insertion. Return true and the head entry is evicted.

Java

public class LruCache<K, V> extends LinkedHashMap<K, V> {

    private final int capacity;

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

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

Java

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");            // capacity exceeded — evicts "b", the eldest

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

Every operation is O(1): the hash table finds the entry and the linked list maintains the order.

TreeMap

A red-black tree, kept balanced so every path from root to leaf has a similar length. Keys are stored in sorted order rather than hashed.

Java

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("carl", 72);
scores.put("ana", 91);
scores.put("bob", 65);

System.out.println(scores);              // {ana=91, bob=65, carl=72} — sorted by key
System.out.println(scores.firstKey());   // ana

Ordering comes from the keys' compareTo, or from a Comparator you supply:

Java

TreeMap<String, Integer> byLength = new TreeMap<>(
        Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

Navigation and range queries

This is the reason to accept O(log n).

Java

NavigableMap<Integer, String> tiers = new TreeMap<>();
tiers.put(0, "Bronze");
tiers.put(1_000, "Silver");
tiers.put(5_000, "Gold");
tiers.put(20_000, "Platinum");

// The classic lookup-by-range: which tier does 7,500 points earn?
System.out.println(tiers.floorEntry(7_500).getValue());     // Gold

tiers.firstEntry();                  // 0=Bronze
tiers.lastEntry();                   // 20000=Platinum

tiers.floorKey(7_500);               // 5000  — greatest key ≤ 7500
tiers.ceilingKey(7_500);             // 20000 — least key ≥ 7500
tiers.lowerKey(5_000);               // 1000  — strictly less
tiers.higherKey(5_000);              // 20000 — strictly greater

tiers.headMap(5_000);                // {0=Bronze, 1000=Silver}
tiers.tailMap(5_000);                // {5000=Gold, 20000=Platinum}
tiers.subMap(1_000, 20_000);         // {1000=Silver, 5000=Gold}

tiers.descendingMap();               // a reversed view
tiers.pollFirstEntry();              // removes and returns the lowest

floorEntry solving the tier lookup in one call is the canonical example. With a HashMap you would have to keep a sorted list of thresholds alongside it and binary search.

Choosing between the three

Aspect	Need	Implementation
Fastest lookup, order irrelevant	HashMap	O(1) average
Iteration in insertion order	LinkedHashMap	O(1), two extra references per entry
LRU eviction	LinkedHashMap, access order	Override removeEldestEntry
Sorted iteration	TreeMap	O(log n), free ordering
Nearest key, or a key range	TreeMap	floor, ceiling, subMap — not possible with a hash map
Keys are enum constants	EnumMap	Array-backed, faster than all three

Fastest lookup, order irrelevant
NeedHashMap
ImplementationO(1) average
Iteration in insertion order
NeedLinkedHashMap
ImplementationO(1), two extra references per entry
LRU eviction
NeedLinkedHashMap, access order
ImplementationOverride removeEldestEntry
Sorted iteration
NeedTreeMap
ImplementationO(log n), free ordering
Nearest key, or a key range
NeedTreeMap
Implementationfloor, ceiling, subMap — not possible with a hash map
Keys are enum constants
NeedEnumMap
ImplementationArray-backed, faster than all three

TreeMap's O(log n) buys ordering and navigation. If you need neither, HashMap is strictly better.

EnumMap, briefly

When keys are enum constants there is a specialised implementation worth preferring every time.

Java

enum Priority { LOW, MEDIUM, HIGH, CRITICAL }

Map<Priority, Integer> queued = new EnumMap<>(Priority.class);
queued.put(Priority.HIGH, 4);
queued.put(Priority.LOW, 12);

System.out.println(queued);       // {LOW=12, HIGH=4} — declaration order

It is backed by a plain array indexed by the enum's ordinal. No hashing, no collisions, no node objects, and iteration follows declaration order. It is faster and smaller than HashMap for the same job.

Common misreadings

"LinkedHashMap is sorted." It preserves insertion or access order, which is not the same as sorted. TreeMap sorts.
"Updating a value reorders a LinkedHashMap." In insertion order it does not. In access order, put of an existing key does move it.
"TreeMap is slower for everything." Sorted iteration and range queries are faster than hashing plus a sort, and floorEntry has no hash-map equivalent.
"TreeMap uses equals and hashCode." It uses compareTo or a Comparator only.
"removeEldestEntry must remove the entry itself." It returns a boolean; the map does the removal.
"An LruCache extending LinkedHashMap is thread-safe." It is not. Synchronise it or use a purpose-built cache.

Quick recall

Everything you need if you only revisit this box.

LinkedHashMap = HashMap + a doubly linked list across entries. O(1), with predictable iteration order.
The three-argument constructor enables access order, moving each read entry to the end.
An LRU cache is access order plus overriding removeEldestEntry to return size() > capacity. Conceptually: a hash map for lookup, a linked list for eviction order.
TreeMap is a red-black tree: O(log n), sorted, no null keys, and equality decided by compareTo.
TreeMap adds floorEntry, ceilingKey, headMap, tailMap, subMap, descendingMap, pollFirstEntry — range answers a hash map cannot give.
Use EnumMap for enum keys: array-backed, declaration order, faster than all of the above.

Test yourself

Answer these before moving on — recall is what makes it stick.