# Advanced HashMap Series: HashMap vs LinkedHashMap vs TreeMap

In large-scale backend systems, choosing the right `Map` isn’t just about code correctness—it’s about *cost models, access patterns, memory layouts*, and downstream behavior during iteration or serialization.

This blog takes a surgical lens to dissect **HashMap**, **LinkedHashMap**, and **TreeMap** — not with textbook gloss, but with the precision expected when you're designing caching systems, audit pipelines, or ordered index layers in production-grade architectures.

## HashMap – We Won’t Re-Explain It

Already broke this down in [this post](https://theharshtech.hashnode.dev/moms-are-hashmapping-geniuses-part-1-hashmap-hashing-collision-and-an-organized-kitchen) — internals, hashing, treeification, and bucket handling.

Let’s skip the theory and focus on what matters now:

### Nuances & Gotcha[s](#)

* **Equality Chaos**: `equals()` and `hashCode()` must align *perfectly*. Get that wrong and you'll never find your key again.
    
* **Mutation Footgun**: You mutate a key after putting it in? Good luck retrieving it.
    
* **O(n) in the shadows**: All it takes is a few bad hashcodes and you fall back to linked lists — welcome to the worst-case.
    
* **No Iteration Guarantees**: Order of entries is like Schrödinger’s cat. Don’t assume anything.
    

### Advantages

* Blazing fast — O(1) on average.
    
* Lightweight, lean, and GC-friendly.
    
* Allows one `null` key (yes, really).
    
* Perfect for dense reads and writes where order doesn’t matter.
    

### Disadvantages

* Chaos in iteration.
    
* Zero predictability for UI/state/order-based flows[.](#)
    
* Not safe across threads — unless externally synchronized.
    

### Real-World Use Cases

* Caching layers under a custom eviction policy.
    
* Word frequency maps, dedup sets.
    
* ID → Value mappings where access speed trumps all else.
    

---

## LinkedHashMap – Determinism Without Drama

### What It Is

`LinkedHashMap` is your `HashMap` with memory — literally. It threads a doubly linked list through all entries to preserve **insertion order** or **access order**, depending on constructor config.

```plaintext
LinkedHashMap<String, String> accessOrdered = new LinkedHashMap<>(16, 0.75f, true);
```

That `true` means *access-order* mode. This is how LRU caches get built.

### Advantages

* Predictable iteration — no surprises.
    
* Can be made LRU-like with minimal code.
    
* Maintains `HashMap`’s average-case O(1) performance.
    

### Disadvantages

* Slight memory overhead from linkage nodes.
    
* Not designed for huge collections with heavy churn — GC pressure can build.
    
* Still not thread-safe.
    

### Nuances & Gotchas

* Access order only updates on *get()* — not on `containsKey()` or iteration.
    
* You can override `removeEldestEntry()` for eviction — but be *very* precise or you’ll evict aggressively.
    

### Real-World Use Cases

* LRU Caches (your classic `get()` triggers reordering, oldest gets evicted).
    
* Maintaining user input order (e.g., form fields).
    
* Displaying data as received — configs, audit events, etc.
    

```plaintext
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
```

---

## TreeMap – When You Need Order *and* Range Logic

### What It Is

`TreeMap` is built on a Red-Black Tree and keeps keys **sorted**, either by natural order or a custom `Comparator`. All operations are `O(log n)`, but what you gain is *predictability* and *range querying*.

```plaintext
TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder());
```

You get `ceilingKey()`, `floorEntry()`, `subMap()` — critical for slicing ordered data.

### Advantages

* Sorted key iteration by default.
    
* Clean support for range queries (submaps, head/tail maps).
    
* Great when keys represent a timeline, ranking, or hierarchy.
    

### Disadvantages

* No null keys allowed. Throws `NullPointerException`.
    
* Higher GC load due to tree structure.
    
* Slower write/read perf compared to HashMap/LinkedHashMap.
    

### Nuances & Gotchas

* Comparator must be *consistent with equals* or you'll have phantom bugs.
    
* Ideal for sorted *keys*, not necessarily sorted *values*.
    
* Red-Black Tree rotations can become costly under extreme insert/delete churn.
    

### Real-World Use Cases

* Sorted leaderboards, range-based slicing (`topN`, `from→to` segments).
    
* Time-series index mapping (`timestamp → metric`).
    
* Interval-matching configs (e.g., price slabs, scoring bands).
    

```plaintext
TreeMap<Integer, String> pricing = new TreeMap<>();
pricing.put(100, "Basic");
pricing.put(500, "Pro");
pricing.put(1000, "Enterprise");

System.out.println(pricing.ceilingEntry(600));  // 1000=Enterprise
System.out.println(pricing.floorEntry(600));    // 500=Pro
```

---

## Comparison Snapshot — Read This Before You Choose

| Feature | HashMap | LinkedHashMap | TreeMap |
| --- | --- | --- | --- |
| Key Order | ❌ None | ✅ Insertion / Access | ✅ Sorted |
| Avg `put/get` | O(1) | O(1) | O(log n) |
| Null Keys | ✅ One | ✅ One | ❌ None |
| Memory | Least | Medium | Most |
| Eviction Ready | ❌ No | ✅ Yes (override) | ❌ No |
| Range Query | ❌ No | ❌ No | ✅ Yes |
| Best For | Speed | Ordered Iteration | Sorted Data |

---

## When to Use What — Architecture-Driven Decision Table

| Scenario | Best Fit | Why |
| --- | --- | --- |
| You want raw speed, no order needed | `HashMap` | Lean, fast, and gets out of your way |
| You need insertion/access order | `LinkedHashMap` | Minimal upgrade from HashMap with guaranteed ordering |
| You need sorted keys or range queries | `TreeMap` | Red-Black Tree ensures sort + range power |
| Building an LRU cache | `LinkedHashMap` | Just set `accessOrder=true`, override eviction |
| Handling config with tiered matching | `TreeMap` | Use `floorEntry()`, `subMap()` to match slabs |
| Displaying values exactly as fed | `LinkedHashMap` | Key order preserved — useful for UIs or logs |

---

## Final Byte

These three may live in the same package, but they behave like different species.

You don’t choose them based on what worked last time — you choose based on *how the map will be used, scaled, iterated, and evolved*.

Because in production, *the wrong map doesn’t just slow you down — it rewrites the bug report you’re going to get next week.*

## What’s Next in the Series

Next up, we’ll dive deep into a topic that looks harmless until it starts corrupting your data structures mid-flight:

> **Thread Safety in HashMaps: What Breaks, Why It Breaks, and How to Design Around It**

We'll explore:

* How concurrent writes silently break `HashMap`
    
* The difference between unsafe and *deliberately safe* designs
    
* When to reach for `ConcurrentHashMap`, and when that’s not enough
    
* Custom strategies: copy-on-write, segmentation, and lock-free tricks
    

Stay tuned…