JAVA / COLLECTIONS
TreeMap, LinkedHashMap and map ordering choices
Pick HashMap, LinkedHashMap or TreeMap from the ordering a task needs, use NavigableMap range lookups, and build an access-order LRU cache.
What you will learn
- Choose HashMap for pure lookup, LinkedHashMap for arrival order, TreeMap for sorted keys
- Answer nearest-key and range questions with floorEntry, ceilingKey, subMap and headMap
- Build an LRU cache from LinkedHashMap access order plus removeEldestEntry
- Remember TreeMap keys match by compare() == 0, never by equals, and reject null
Understanding TreeMap, LinkedHashMap and map ordering choices
All three classes implement Map, so the calling code is identical; what differs is where the order lives. HashMap keeps nodes in a bucket array, so the sequence you see while iterating is just that array being walked from slot 0 upward, an artifact that moves when keys change or the table doubles. LinkedHashMap is a HashMap subclass that threads a doubly-linked list through those same nodes, spending two extra references per entry to remember the order entries arrived. TreeMap does no hashing at all: it is a red-black tree held in key order, so every get, put and containsKey costs O(log n) comparisons rather than one hash probe.
That structural difference is the whole decision. If nothing ever iterates the map, HashMap is cheapest in time and memory. If the map gets printed, serialized, diffed or asserted on, LinkedHashMap buys a reproducible order for very little, and its iteration walks the list in time proportional to the number of entries instead of the capacity of the table. Reach for TreeMap when the question itself is about order, such as first and last key, the greatest key below a value, or every key in a range: a HashMap can only answer those by sorting all keys again at O(n log n) per query, while the tree answers in O(log n).
The subtle part is that TreeMap redefines what the same key means. HashMap and LinkedHashMap identify keys by hashCode and equals; TreeMap asks only compareTo or the supplied Comparator and treats compare(a, b) == 0 as already present, never calling equals at all. So a case-insensitive comparator turns 'Host' and 'host' into one entry, a comparator that looks at only part of the key silently merges rows, and a null key throws NullPointerException because there is nothing to compare. TreeMap even type-checks on the very first put, so a key class that forgot to implement Comparable fails with ClassCastException immediately rather than on some later insertion.
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;
public class MapOrdering {
public static void main(String[] args) {
int[] ids = {30, 4, 21, 12};
Map<Integer, String> hash = new HashMap<>();
Map<Integer, String> linked = new LinkedHashMap<>();
NavigableMap<Integer, String> tree = new TreeMap<>();
for (int id : ids) {
hash.put(id, "row" + id);
linked.put(id, "row" + id);
tree.put(id, "row" + id);
}
System.out.println("hash " + hash.keySet()); // bucket layout, not a promise
System.out.println("linked " + linked.keySet());
System.out.println("tree " + tree.keySet());
System.out.println("firstKey " + tree.firstKey() + ", lastKey " + tree.lastKey());
System.out.println("floorEntry(20) " + tree.floorEntry(20));
System.out.println("ceilingKey(13) " + tree.ceilingKey(13));
System.out.println("headMap(21) " + tree.headMap(21));
System.out.println("subMap(4, 22) " + tree.subMap(4, 22));
System.out.println("descending " + tree.descendingMap());
}
}Iteration order is a property of the implementation you pick, not of the Map interface: HashMap offers none you may rely on, LinkedHashMap replays insertion or access order, and TreeMap keeps keys sorted by a comparison.
Worked examples
LRU cache from access order
Shows how the three-argument LinkedHashMap constructor plus removeEldestEntry evicts the least recently used key.
import java.util.LinkedHashMap;
import java.util.Map;
public class LruByAccessOrder {
public static void main(String[] args) {
Map<String, Integer> cache = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
return size() > 3;
}
};
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
System.out.println("after puts " + cache.keySet());
cache.get("a");
System.out.println("after get a " + cache.keySet());
cache.put("d", 4);
System.out.println("after put d " + cache.keySet());
cache.containsKey("c");
System.out.println("after cKey c " + cache.keySet());
}
}Example explained
Line 1The third constructor argument switches the map to access order, so get moves the entry it found to the tail of the internal list.
Line 2removeEldestEntry runs after every insertion and receives the head entry, so returning size() > 3 caps the cache at three keys.
Line 3Putting d appends it and then evicts b, because get a had already moved a past b, leaving b as the least recently used entry.
Line 4containsKey leaves the order alone: LinkedHashMap overrides get and getOrDefault to record an access, but not containsKey.
A comparator decides which keys are the same
Demonstrates that TreeMap key identity comes from the Comparator, not from equals, so a case-insensitive order merges entries.
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class ComparatorIsIdentity {
public static void main(String[] args) {
Map<String, Integer> tree = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
tree.put("Host", 1);
tree.put("host", 2);
tree.put("Accept", 3);
Map<String, Integer> hash = new HashMap<>();
hash.put("Host", 1);
hash.put("host", 2);
hash.put("Accept", 3);
System.out.println("tree = " + tree);
System.out.println("tree size = " + tree.size() + ", hash size = " + hash.size());
System.out.println("HOST found: tree = " + tree.containsKey("HOST")
+ ", hash = " + hash.containsKey("HOST"));
}
}Example explained
Line 1The comparator reports 0 for host against Host, so the second put is an update: the value becomes 2 while the stored key object stays the first one, Host.
Line 2The same three puts leave three entries in the HashMap, where hashCode and equals decide identity and the two spellings differ.
Line 3containsKey also goes through the comparator, which is why HOST is found in the tree and missing from the hash map.
Line 4This map is intentionally inconsistent with equals, which the Map contract permits, but only pick it when merging by comparator is the behaviour you want.
Updates, re-insertion and null keys
Shows that updating a value never moves an insertion-ordered entry, and that TreeMap refuses the null key LinkedHashMap accepts.
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;
public class OrderAndNulls {
public static void main(String[] args) {
Map<String, Integer> linked = new LinkedHashMap<>();
linked.put("a", 1);
linked.put("b", 2);
linked.put("c", 3);
linked.put("a", 99);
System.out.println("update a " + linked.keySet());
linked.remove("b");
linked.put("b", 2);
System.out.println("re-add b " + linked.keySet());
linked.put(null, 0);
System.out.println("null key " + linked.keySet());
try {
new TreeMap<String, Integer>().put(null, 0);
} catch (NullPointerException e) {
System.out.println("TreeMap NullPointerException on put(null, 0)");
}
}
}Example explained
Line 1put on an existing key only swaps the value; the node is not re-linked, so a keeps the position it took on first insertion.
Line 2remove followed by put builds a new node that is appended, which is the only way to move a key in an insertion-ordered map.
Line 3LinkedHashMap inherits HashMap's tolerance of one null key, and that key iterates wherever it was first inserted.
Line 4TreeMap calls compare(key, key) on the first put as a type and null check, so a null key fails even on an empty map.
Important notes
headMap, tailMap and subMap are live windows onto the TreeMap, not copies: removing through the view removes from the map, and putting a key outside the range throws IllegalArgumentException.
In access-order mode, get is a structural modification because it bumps modCount, so calling get on anything but the newest entry while iterating keySet throws ConcurrentModificationException; containsKey does not.
Common mistakes
Treating HashMap's printed order as stable: keys 1 to 10 come out ascending by accident, then adding 20 makes it appear between 4 and 5 because it shares a slot with 4 in a 16-slot table, and the golden-file test or the shipped report silently changes order.
Giving TreeMap a comparator that compares only part of the key, such as Comparator.comparing(Person::lastName): two people with the same last name become one entry, the second put overwrites the first value while keeping the first key, and rows disappear with no error.
Passing an ordered map through Collectors.toMap or new HashMap<>(ordered): both hand back a HashMap and the insertion order is gone, so you must use the four-argument toMap with LinkedHashMap::new as the map supplier.
Try it yourself
Change, predict, then run
Build a TreeMap<Integer, String> of grade cutoffs 0=F, 60=D, 70=C, 80=B, 90=A and print floorEntry for the scores 0, 59, 72, 90 and 100. Then put the same five pairs into a LinkedHashMap and see what you would have to write to answer the same question without a sorted key order.
Open the Java workspaceCheck your understanding
You parse a CSV header row into a map from column name to column index, use it for a lookup on every data row, and finally write the file back out with its columns in the original order. Which implementation fits, and why?
- LinkedHashMap, because its linked list replays the order the columns were added while each lookup stays a single hash probe
- TreeMap, because it is the only Map with a defined iteration order, so the columns come back out in the right sequence
- HashMap, because for a fixed set of keys the iteration order does not change, so the header order survives
- LinkedHashMap with access order enabled, because reading a column keeps the ordering up to date
Show answer
LinkedHashMap keeps the header order in a list beside the hash table, so per-row lookups stay O(1) and the output order is exactly the input order. TreeMap does define an order, but it is the sorted order of the column names, so the file would come back out alphabetically; HashMap's order follows the bucket layout, which depends on capacity and insertion history rather than your header; and access order would reshuffle the columns every time a row is read.