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 exactly
  5. TreeMap rejects null keys

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

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 everything below applies symmetrically to the Set variants. 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; modern Java converts a long collision chain into a balanced tree, bounding the worst case at O(log n) per bucket rather than O(n). ## 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. 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). ## 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: TreeMap does **not** allow a `null` key (it must compare keys). ## 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 identical 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 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 | not allowed |

  • 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 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 these in an interview costs you the question

  • 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 forbids null keys.
  • Thinking LinkedHashMap sorts entries — it only preserves insertion/access order, not sort order.

context

resolving links…