HashMap vs LinkedHashMap in Java: Key Differences, Performance & Use Cases

A developer’s guide to choosing the right Java Map

Java developers reach for a HashMap almost instinctively whenever a key-value store is needed. But there’s a close cousin — LinkedHashMap — that solves a different class of problems. Understanding the difference will help you pick the right tool every time.

1. The Quick Answer

Both HashMap and LinkedHashMap implement the Map<K, V> interface and store key-value pairs with O(1) average time for get and put. The single biggest difference is:

• HashMap — no guaranteed iteration order.
• LinkedHashMap — maintains a doubly linked list alongside the hash table, preserving either insertion order or access order.

2. How HashMap Works

A HashMap stores entries in an array of buckets. The bucket index is derived from the key’s hash code. When two keys land in the same bucket (a collision), Java chains them using a linked list or, since Java 8, a balanced tree when a bucket grows large.

Because insertion order depends on hash codes — which can be anything — iterating over a HashMap gives you entries in an unpredictable sequence.

Example

Map<String, Integer> map = new HashMap<>();
map.put("banana", 2);
map.put("apple",  1);
map.put("cherry", 3);
// Iteration order is NOT guaranteed — could be anything:
// cherry=3, apple=1, banana=2

3. How LinkedHashMap Works

A LinkedHashMap wraps a HashMap and additionally wires every entry into a doubly linked list. This costs one extra pointer per entry (before + after), but gives you deterministic iteration.

There are two modes, controlled by the third constructor argument:

• Insertion order (default) — new LinkedHashMap<>(). Entries come out in the order they were put in.
• Access order — new LinkedHashMap<>(cap, 0.75f, true). A get() or put() on a key moves it to the tail, making the head always the least-recently-used entry.

Insertion-order example

Map<String, Integer> map = new LinkedHashMap<>();
map.put("banana", 2);
map.put("apple",  1);
map.put("cherry", 3);
// Iteration always gives: banana=2, apple=1, cherry=3

Access-order (LRU) example

Map<String, Integer> cache = new LinkedHashMap<>(16, 0.75f, true);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
cache.get("a");  // "a" moves to tail — most recently used
// Iteration order: b=2, c=3, a=1  (a is now freshest)

4. Side-by-Side Comparison

5. The LRU Cache Pattern

The most powerful use of LinkedHashMap is building a self-evicting LRU cache by overriding removeEldestEntry:

int capacity = 3;
Map<Integer, Integer> lru = new LinkedHashMap<>(capacity, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;  // evict LRU entry when over capacity
    }
};
lru.put(1, 10);
lru.put(2, 20);
lru.put(3, 30);
lru.get(1);     // access key 1 — moves to tail
lru.put(4, 40); // over capacity — key 2 (LRU) is evicted automatically
// Cache now contains: {3=30, 1=10, 4=40}

This is a complete, production-ready LRU cache in ~6 lines — no manual linked list management required.

6. Performance Considerations

For the vast majority of applications the performance difference is negligible. Both offer O(1) average-case get/put/remove. However, keep these points in mind:

• Memory: LinkedHashMap uses roughly 2× the memory per entry due to the extra linked list pointers.
• Iteration: LinkedHashMap is actually faster to iterate because it walks a compact linked list rather than scanning all buckets (many of which may be empty).
• Concurrency: Neither is thread-safe. Wrap with Collections.synchronizedMap() or use ConcurrentHashMap for concurrent access.

7. When to Use Each

Use HashMap when:

• You don’t care about iteration order
• You’re optimizing for raw memory or speed
• You’re building a frequency counter, index, or any lookup table

Use LinkedHashMap when:

• You need to maintain insertion order (e.g., JSON-like ordered maps)
• You’re building an LRU cache
• You want deterministic iteration for testing or logging
• You’re implementing an ordered pipeline of steps

Conclusion

HashMap is your default, all-purpose workhorse. LinkedHashMap is the upgrade you reach for the moment order matters — especially for caching. Because LinkedHashMap extends HashMap, the API is identical; switching between them is a one-line change in your constructor call.

The next time you find yourself manually sorting map entries or hand-rolling an LRU cache, remember: LinkedHashMap already has you covered.