skip to content

How do you choose among HashMap, LinkedHashMap, and TreeMap (and the equivalent Set variants)?

level: middleimportance: must knowfreq 70%

answer

  1. HashMap = O(1), no order, default
  2. LinkedHashMap = insertion/access order, LRU cache
  3. TreeMap = sorted, O(log n), Navigable range queries
  4. Set siblings mirror the maps, minus access order
  5. TreeMap: no null key under natural ordering

basics

~20 s

HashMap is the default: fast, no ordering. LinkedHashMap keeps insertion order (or access order, for LRU caches). TreeMap keeps keys sorted and lets you do range queries, but it's a bit slower. Same idea for HashSet / LinkedHashSet / TreeSet.

solid answer

~40 s

All three implement Map; the difference is ordering and cost. HashMap gives average O(1) get/put with no ordering guarantee — the default choice. LinkedHashMap is a HashMap plus a linked list threading the entries, so it iterates in insertion order (or access order if you enable it, which is how you build an LRU cache); it costs slightly more memory for the predictable order. TreeMap is a red-black tree keeping keys in sorted order, giving O(log n) operations and navigation methods (firstKey, floorKey, ceilingKey, subMap) for range queries — pick it when you need sorted iteration or 'nearest key' lookups. The Set siblings (HashSet/LinkedHashSet/TreeSet) follow the same ordering/cost trade-offs, minus access order. Decision: need range/sorted? TreeMap. Need predictable iteration order or LRU? LinkedHashMap. Otherwise HashMap.

code

java · 12 lines
java
// Sorted + range query:
NavigableMap<Integer,String> tree = new TreeMap<>();
tree.put(10,"a"); tree.put(20,"b"); tree.put(30,"c");
tree.floorKey(25);            // 20  (largest key <= 25)
tree.subMap(10,true,20,true); // {10=a, 20=b}

// LRU cache via access-order LinkedHashMap:
Map<Integer,String> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override protected boolean removeEldestEntry(Map.Entry<Integer,String> e) {
        return size() > 100;   // evict least-recently-used beyond 100
    }
};

go deeper

for a junior

Knows HashMap is the default and that TreeMap sorts keys while LinkedHashMap keeps insertion order.

for a middle

States the cost/order table, maps requirements to the right variant, and knows the Set siblings mirror the maps except for access order.

for a senior

Explains the red-black tree O(log n) trade-off, NavigableMap range methods, the access-order LRU trick, and null-key rules.

for a principal

Weighs ordering guarantees in API contracts, anticipates hash-collision worst cases (treeification), and avoids over-ordering for cost/clarity at scale.

## The shared contract `HashMap`, `LinkedHashMap`, and `TreeMap` all implement **`Map`** (key→value, unique keys). Their `Set` siblings — `HashSet`, `LinkedHashSet`, `TreeSet` — implement **`Set`** and are literally backed by the corresponding maps. So the ordering and cost below apply to the Set variants too, apart from access order: `LinkedHashSet` has no constructor for it. The question is always: **what ordering do I need, and what cost will I pay for it?** ## HashMap — the default A **hash table**: it computes a key's `hashCode()`, maps it to a bucket, and stores the entry there. Lookups, inserts, and removals are **average O(1)** (constant time), assuming a decent hash spread. There is **no ordering** — iteration order is unspecified and can change as the table resizes. Keys rely on correct `hashCode()`/`equals()`. One `null` key is allowed. This is the right choice unless you have a specific ordering need. *Worst case:* if many keys collide into one bucket, that bucket degrades; since Java 8 a long collision chain converts into a balanced tree, giving O(log n) lookups in that bucket when keys have distinct hash codes or are `Comparable`, and O(n) only when they share one hash and have no order. ## LinkedHashMap — predictable order A HashMap **plus a doubly-linked list** threaded through all entries, recording the order they were added. Iteration then follows that **insertion order** — useful when you want reproducible output or to preserve the order data arrived. It keeps average O(1) operations; you pay a little extra memory (the link pointers) for the predictability. Iteration takes time proportional to size alone, where `HashMap`'s also grows with capacity, so an oversized initial capacity hurts it less. It has a second mode: **access-order** (constructed with `accessOrder=true`). Every `get`/`put` moves the touched entry to the end, so the *least recently used* entry sits at the front. Override `removeEldestEntry` and you have a ready-made **LRU cache** (evict the eldest when over capacity). Since Java 21 `LinkedHashMap` also reads and removes its ends (`firstEntry`, `pollFirstEntry`), so `TreeMap` is not needed for that alone. ## TreeMap — sorted keys & range queries A **red-black tree** (a self-balancing binary search tree) that keeps keys in **sorted order** — either their natural order (`Comparable`) or a supplied `Comparator`. Operations are **O(log n)** rather than O(1), the price for keeping everything sorted. In return you get the **`NavigableMap`** powers: `firstKey`/`lastKey`, `floorKey` (largest key ≤ x), `ceilingKey` (smallest key ≥ x), `headMap`/`tailMap`/`subMap` (range views). Choose it when you need sorted iteration, 'find the nearest key', or range scans. Note: under natural ordering TreeMap rejects a `null` key with `NullPointerException`, because it must compare keys; a null-tolerant `Comparator` such as `Comparator.nullsFirst(...)` accepts one. ## The decision 1. **Need keys sorted, or range / nearest-key queries?** → **TreeMap** (O(log n)). 2. **Need predictable iteration order, or an LRU cache?** → **LinkedHashMap**. 3. **Otherwise** → **HashMap** (fastest, no order). Apply the same ordering logic to **HashSet / LinkedHashSet / TreeSet**. A common mistake is reaching for TreeMap 'to be safe' when you never iterate in order — you pay O(log n), and under natural ordering lose null-key support, for nothing. ## Quick cost table | | get/put | order | null key | |---|---|---|---| | HashMap | avg O(1) | none | one allowed | | LinkedHashMap | avg O(1) | insertion (or access) | one allowed | | TreeMap | O(log n) | sorted | rejected under natural ordering |

  • How do you build an LRU cache with the standard library?
    Use a LinkedHashMap constructed with accessOrder=true and override removeEldestEntry to return true once size exceeds the capacity. Access-order moves touched entries to the tail, so the eldest (front) is the least recently used and gets evicted.
  • Why might TreeMap be wrong even though it 'keeps things sorted nicely'?
    If you never iterate in sorted order or do range queries, you pay O(log n) per operation instead of O(1), use more comparisons, and, under natural ordering, lose null-key support — all for an ordering you don't use. Prefer HashMap unless ordering/range is a real requirement.

HashMap is a pile of labeled folders you grab instantly but in no order. LinkedHashMap is the same pile with a string tied through them in the order you filed them, so you can read them back in sequence. TreeMap is a filing cabinet kept alphabetized — slightly slower to file, but you can flip straight to 'everything between M and P'.

  • Saying HashMap preserves insertion order — it does not; that's LinkedHashMap.
  • Believing TreeMap is O(1) — it's O(log n).
  • Using TreeMap where a HashMap suffices, paying for unused ordering.
  • Forgetting TreeMap rejects null keys under natural ordering.
  • Thinking LinkedHashMap sorts entries — it only preserves insertion/access order, not sort order.

NavigableMap navigation methods
Java 1.6

Assumes JDK 27. LinkedHashMap's end methods arrived in Java 21 and are the same at JDK 25; tree bins date from Java 8.

context