Java TreeMap and LinkedHashMap: Sorted and Ordered Maps

HashMap is the default Map choice, but two alternatives fill important gaps: TreeMap keeps keys in sorted order (by natural ordering or a Comparator) and supports range queries via the NavigableMap interface, while LinkedHashMap preserves insertion order (or access order for LRU caches). Knowing when to reach for each of these prevents both over-engineering and under-engineering your data structure choices.

Share

Contents

TreeMap Basics: Sorted Keys

TreeMap is a red-black tree implementation of NavigableMap. All operations are O(log n), and keys are always kept in sorted order: by natural ordering or a supplied Comparator. Unlike HashMap, it does not permit null keys:

Java
import java.util.*;

// TreeMap — Red-Black tree, keys always sorted, O(log n) all operations
TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Charlie", 85);
scores.put("Alice",   92);
scores.put("Bob",     78);
scores.put("Diana",   95);

// Iteration always in key-sorted order
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// Alice: 92
// Bob: 78
// Charlie: 85
// Diana: 95

// First and last keys
System.out.println(scores.firstKey()); // "Alice"
System.out.println(scores.lastKey());  // "Diana"

// Custom comparator — reverse alphabetical
TreeMap<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder());
reverseMap.putAll(scores);
System.out.println(reverseMap.firstKey()); // "Diana"

// Keys with null — TreeMap does NOT allow null keys (NPE on compare)
// Values can be null

NavigableMap: Range and Floor/Ceiling

The NavigableMap interface adds relative navigation methods to a sorted map. floorKey() finds the greatest key ≤ a target, ceilingKey() finds the smallest key ≥ a target, and headMap() / tailMap() / subMap() return live views of key ranges:

Java
TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(10, "ten");
tm.put(20, "twenty");
tm.put(30, "thirty");
tm.put(40, "forty");
tm.put(50, "fifty");

// floor — greatest key <= given key
System.out.println(tm.floorKey(25));    // 20
System.out.println(tm.floorEntry(25));  // 20=twenty

// ceiling — smallest key >= given key
System.out.println(tm.ceilingKey(25));  // 30

// lower — strictly less than
System.out.println(tm.lowerKey(30));    // 20

// higher — strictly greater than
System.out.println(tm.higherKey(30));   // 40

// Range views — backed by the original map (live)
SortedMap<Integer, String> head = tm.headMap(30);    // keys < 30
System.out.println(head); // {10=ten, 20=twenty}

SortedMap<Integer, String> tail = tm.tailMap(30);    // keys >= 30
System.out.println(tail); // {30=thirty, 40=forty, 50=fifty}

NavigableMap<Integer, String> sub = tm.subMap(20, true, 40, true); // [20, 40]
System.out.println(sub); // {20=twenty, 30=thirty, 40=forty}

// Poll first/last (removes and returns)
Map.Entry<Integer, String> first = tm.pollFirstEntry(); // removes {10=ten}
Map.Entry<Integer, String> last  = tm.pollLastEntry();  // removes {50=fifty}

// Descending view
NavigableMap<Integer, String> desc = tm.descendingMap();
System.out.println(desc.firstKey()); // 40 (was 50, now removed)

// Practical: find the price tier for a given amount
TreeMap<Integer, String> priceTiers = new TreeMap<>();
priceTiers.put(0,     "Free");
priceTiers.put(10,    "Basic");
priceTiers.put(50,    "Pro");
priceTiers.put(200,   "Enterprise");

int spend = 75;
String tier = priceTiers.floorEntry(spend).getValue();
System.out.println(tier); // "Pro" — greatest tier threshold <= 75

LinkedHashMap: Insertion and Access Order

LinkedHashMap augments HashMap with a doubly-linked list through its entries, preserving either insertion order (default) or access order (when constructed with accessOrder=true). All operations remain O(1); iteration is predictable:

Java
// LinkedHashMap — HashMap + doubly-linked list for order; O(1) operations
// Default: insertion order
LinkedHashMap<String, Integer> lhm = new LinkedHashMap<>();
lhm.put("banana", 2);
lhm.put("apple",  5);
lhm.put("cherry", 1);

// Iteration in insertion order
for (String key : lhm.keySet()) {
    System.out.println(key); // banana, apple, cherry
}

// Updating an existing key does NOT change its position
lhm.put("banana", 10); // position stays first
System.out.println(lhm.keySet()); // [banana, apple, cherry]

// Access order — LinkedHashMap(capacity, loadFactor, accessOrder=true)
LinkedHashMap<String, Integer> accessOrder =
    new LinkedHashMap<>(16, 0.75f, true); // true = access order
accessOrder.put("a", 1);
accessOrder.put("b", 2);
accessOrder.put("c", 3);

accessOrder.get("a"); // access "a" — moves it to end
System.out.println(accessOrder.keySet()); // [b, c, a]

accessOrder.get("b"); // access "b" — moves it to end
System.out.println(accessOrder.keySet()); // [c, a, b]

// LinkedHashMap preserves null keys and null values (like HashMap)
lhm.put(null, 0);
lhm.put("nullable", null);

LRU Cache with LinkedHashMap

With accessOrder=true, each get() or put() moves the entry to the tail of the linked list. Overriding removeEldestEntry() to return true when the size exceeds a threshold evicts the least-recently-used (head) entry automatically:

Java
// LinkedHashMap.removeEldestEntry() — hook for eviction policy
// Build an LRU cache by overriding this method

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

    public LruCache(int capacity) {
        // accessOrder=true — get() moves the entry to the end
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // Return true to remove eldest when over capacity
        return size() > capacity;
    }
}

// Usage
LruCache<Integer, String> cache = new LruCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
System.out.println(cache.keySet()); // [1, 2, 3]

cache.get(1); // access 1 — moves it to end (recently used)
System.out.println(cache.keySet()); // [2, 3, 1]

cache.put(4, "four"); // triggers eviction of eldest (2)
System.out.println(cache.keySet()); // [3, 1, 4]
System.out.println(cache.containsKey(2)); // false — evicted

// Thread-safe LRU cache
Map<K, V> syncLru = Collections.synchronizedMap(new LruCache<>(100));
The classic LRU cache pattern using LinkedHashMap with access order is a production-proven approach. For concurrent environments, wrap it in Collections.synchronizedMap(), or use a dedicated library like Caffeine for high-throughput scenarios.

Map Implementation Comparison

Choosing the right Map comes down to ordering and performance needs. HashMap is the general default; use LinkedHashMap when iteration order matters, TreeMap for sorted keys or range queries, and EnumMap when all keys are enum constants. Map.of() is best for small immutable maps:

ImplementationKey orderget/putNull keyUse when
HashMapNoneO(1)1 nullGeneral purpose
LinkedHashMapInsertion/AccessO(1)1 nullOrdered iteration, LRU
TreeMapSortedO(log n)No nullRange queries, sorted
EnumMapEnum ordinalO(1)No nullEnum keys
HashtableNoneO(1)No nullLegacy: avoid
ConcurrentHashMapNoneO(1)No nullConcurrent access
Java
// EnumMap — when all keys are from the same enum
enum Direction { NORTH, SOUTH, EAST, WEST }
EnumMap<Direction, String> labels = new EnumMap<>(Direction.class);
labels.put(Direction.NORTH, "Up");
labels.put(Direction.SOUTH, "Down");
// Iteration in enum declaration order; more compact than HashMap

// Immutable maps — Java 9+
Map<String, Integer> immutable = Map.of("a", 1, "b", 2, "c", 3);
Map<String, Integer> immutable2 = Map.ofEntries(
    Map.entry("alice", 90),
    Map.entry("bob",   85));
// Map.of() does not allow null keys or values, and order is unspecified

// Copy immutable snapshot from mutable
Map<String, Integer> snapshot = Map.copyOf(mutableMap);

Related articles

All Java articles →
NavigableMap and NavigableSet: floor, ceiling, range queriesJava NavigableMap and NavigableSet: floor, ceiling, lower, higher, headMap, tailMap, subMap, descendingMap, and range queries with TreeMap and TreeSet.Java ConcurrentHashMap: Thread-Safe MapsJava ConcurrentHashMap deep dive: internal structure, concurrent operations, compute methods, and best practices for thread-safe maps.Java Stream API: filter, map, reduce, collect & MoreJava Stream API: filter, map, reduce, collect, sorted, parallel streams, primitive streams, and best practices with practical examples.Java Set: HashSet, LinkedHashSet, TreeSet and Set OperationsJava Set: HashSet, LinkedHashSet, TreeSet, set operations union, intersection, difference, and choosing the right Set implementation.