Contents

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:

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

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:

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 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:

// 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);

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:

// 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.

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:

// | Implementation | Key order | get/put | Null key | Use when | // |-----------------|-----------------|----------|----------|------------------------| // | HashMap | None | O(1) | 1 null | General purpose | // | LinkedHashMap | Insertion/Access| O(1) | 1 null | Ordered iteration, LRU | // | TreeMap | Sorted | O(log n) | No null | Range queries, sorted | // | EnumMap | Enum ordinal | O(1) | No null | Enum keys | // | Hashtable | None | O(1) | No null | Legacy — avoid | // | ConcurrentHashMap| None | O(1) | No null | Concurrent access | // 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);