TreeMap & LinkedHashMap

HashMap is fast but gives you no guarantee about the order entries come back in. When ordering matters, Java offers two other Map implementations that trade a little performance for predictable iteration: TreeMap, which keeps entries sorted by key, and LinkedHashMap, which preserves the order entries were inserted.

TreeMap — Sorted by Key

TreeMap keeps its entries sorted automatically, using either the key type's natural ordering (for example, numbers sort ascending, strings sort alphabetically) or a custom Comparator you supply at construction time. Internally it's backed by a red-black tree, which gives O(log n) time for get(), put(), and remove() — slower than HashMap's average O(1), but still very efficient, and you get sorted iteration for free.

TreeMap with natural ordering

Java

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

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Charlie", 88);
scores.put("Alice", 95);
scores.put("Bob", 79);

System.out.println(scores); // keys come back sorted alphabetically

for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

{Alice=95, Bob=79, Charlie=88}
Alice -> 95
Bob -> 79
Charlie -> 88

You can override the default ordering by passing a Comparator to the constructor — useful for sorting descending, sorting by a computed value, or sorting objects that don't implement Comparable at all.

TreeMap with a custom Comparator (descending order)

Java

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

TreeMap<String, Integer> byScoreDesc =
        new TreeMap<>(Comparator.reverseOrder());
byScoreDesc.put("Charlie", 88);
byScoreDesc.put("Alice", 95);
byScoreDesc.put("Bob", 79);

System.out.println(byScoreDesc);

{Charlie=88, Bob=79, Alice=95}

Navigating a TreeMap

Because a TreeMap is sorted, it can answer questions a HashMap simply can't: what's the smallest key? what's the first key at or above a given value? Methods like firstKey() and ceilingKey() make TreeMap a good fit for range-style lookups.

firstKey() and ceilingKey()

Java

import java.util.TreeMap;

TreeMap<Integer, String> priceLevels = new TreeMap<>();
priceLevels.put(10, "Bronze");
priceLevels.put(50, "Silver");
priceLevels.put(100, "Gold");

System.out.println(priceLevels.firstKey());       // smallest key
System.out.println(priceLevels.ceilingKey(60));    // smallest key >= 60

10
100

LinkedHashMap — Insertion Order

LinkedHashMap behaves like HashMap for lookups — it's still backed by a hash table, so get()/put() stay O(1) on average — but it additionally maintains a doubly-linked list running through the entries, which preserves the order they were inserted in.

LinkedHashMap preserves insertion order

Java

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

Map<String, Integer> visits = new LinkedHashMap<>();
visits.put("home", 1);
visits.put("about", 2);
visits.put("contact", 3);

System.out.println(visits); // prints in the order keys were inserted

{home=1, about=2, contact=3}

Access-Order Mode: A Simple LRU Cache

LinkedHashMap has a lesser-known constructor overload that switches it into access order instead of insertion order — every get() or put() moves that entry to the end. Combined with overriding removeEldestEntry(), this is enough to build a working least-recently-used (LRU) cache in a handful of lines.

A minimal LRU cache built on LinkedHashMap

Java

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

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

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

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

LruCache<Integer, String> cache = new LruCache<>(2);
cache.put(1, "a");
cache.put(2, "b");
cache.get(1);        // "1" is now the most recently used
cache.put(3, "c");   // capacity exceeded, evicts the least recently used ("2")

System.out.println(cache);

{1=a, 3=c}

Note

Entry 2 was evicted, not 1, because calling get(1) moved it to the most-recently-used position before the new entry was inserted.

Aspect	HashMap	LinkedHashMap	TreeMap
Ordering	None — unpredictable	Insertion order (or access order)	Sorted by key
get/put time	O(1) average	O(1) average	O(log n)
Null keys	One allowed	One allowed	Not allowed
Backed by	Hash table	Hash table + linked list	Red-black tree
Best for	Fastest general-purpose lookups	Predictable iteration order, LRU caches	Sorted iteration, range queries

Tip

Reach for HashMap by default, switch to LinkedHashMap when you need predictable iteration order without paying for sorting, and use TreeMap only when you genuinely need entries kept in sorted order.

TreeMap keeps keys sorted (natural order or a custom Comparator) at O(log n) per operation
firstKey()/ceilingKey() and similar methods support range-style lookups
LinkedHashMap keeps HashMap's O(1) performance while preserving insertion order
LinkedHashMap's access-order constructor plus removeEldestEntry() gives you a simple LRU cache