HashMap vs TreeMap vs LinkedHashMap

Three flavours

HashMap — no ordering guarantee, O(1) average get/put, the default choice. LinkedHashMap — preserves insertion order (or access order, configurable) at a small extra cost. TreeMap — keeps keys sorted (natural order or a Comparator), O(log n) operations, backed by a red-black tree.

Side by side

Same keys inserted in the same order, three different iteration results.

Map<String, Integer> h = new HashMap<>();
Map<String, Integer> l = new LinkedHashMap<>();
Map<String, Integer> t = new TreeMap<>();
for (var m : List.of(h, l, t)) { m.put("c", 3); m.put("a", 1); m.put("b", 2); }

System.out.println(l.keySet()); // [c, a, b]  (insertion order)
System.out.println(t.keySet()); // [a, b, c]  (sorted)

Rule of thumb

Start with HashMap. Switch to LinkedHashMap only if predictable iteration order matters (e.g. an LRU cache). Switch to TreeMap only if you need the keys sorted or range queries like firstKey()/headMap().