Java LinkedHashMap

In the last lesson you learned about Java HashMap. It is fast, but it does not keep your pairs in any order: the order you put things in is not the order you get them out. When that order matters, Java gives us the LinkedHashMap.

🤔 The problem with no order

Picture you are building a small “recently viewed” list for an online store. A shopper looks at a shoe, then a bag, then a watch. You store each item in a map so you can also keep its price. Later you want to show the items back in the exact order they were viewed. Shoe first, then bag, then watch.

If you reach for a plain HashMap, you get a surprise.

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Double> viewed = new HashMap<>();
        viewed.put("shoe", 49.99);
        viewed.put("bag", 89.00);
        viewed.put("watch", 199.00);

        System.out.println(viewed);   // order is scrambled
    }
}

Here is why the order comes out wrong:

• You added shoe, bag, watch in that order.
• HashMap stores pairs by their hash code, not by when you added them.
• So the printout comes back in some internal order.
• Your “recently viewed” list looks random.

{bag=89.0, shoe=49.99, watch=199.0}

You needed a predictable order, and HashMap gives you a shuffle. A LinkedHashMap fixes this in one line of change.

🧩 What is a LinkedHashMap?

A LinkedHashMap is a map that keeps its keys in insertion order. Here is what that means:

• Insertion order is the order in which you added the keys.
• The first key you put in is the first one you see when you loop.
• It behaves exactly like a HashMap, with that one extra promise about order.

Here is the same example, with just the type swapped.

import java.util.LinkedHashMap;

public class Main {
    public static void main(String[] args) {
        LinkedHashMap<String, Double> viewed = new LinkedHashMap<>();
        viewed.put("shoe", 49.99);
        viewed.put("bag", 89.00);
        viewed.put("watch", 199.00);

        System.out.println(viewed);   // ✅ stays in insertion order
    }
}

Here is what changed and what you get:

• We only changed HashMap to LinkedHashMap. Everything else is the same.
• Now the order is exactly what we added: shoe, then bag, then watch.
• The map remembers the path you took.

{shoe=49.99, bag=89.0, watch=199.0}

⚙️ How does it keep the order?

A LinkedHashMap is a HashMap with a small extra. It is backed by a hash table plus a linked list.

• The hash table is the same fast stuff from HashMap. It makes get and put quick, jumping straight to the right spot.
• The linked list is a thin thread running through every entry, joining them in the order you added them.
• Each entry points to the one before it and the one after it.
• When you loop, Java walks that thread from start to end. So you get hash table speed and a predictable order at once.
• The cost is tiny. Each entry uses a little more memory for the two extra pointers.

💡 Same methods as HashMap

Because a LinkedHashMap is a HashMap underneath, every method you know works the same:

• put, get, remove, getOrDefault, containsKey, merge, keySet, entrySet all behave the same.
• Nothing new to memorise.

Let’s prove it with a quick run.

import java.util.LinkedHashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> ages = new LinkedHashMap<>();
        ages.put("Alex", 25);
        ages.put("Riya", 30);
        ages.put("Arjun", 28);

        ages.put("Alex", 26);                 // same key replaces the value
        ages.remove("Arjun");                 // deletes that pair

        System.out.println(ages.get("Riya"));
        System.out.println(ages.getOrDefault("Sam", 0));

        for (Map.Entry<String, Integer> entry : ages.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

Reading it top to bottom:

• Putting “Alex” again replaces the old value, because keys are still unique.
• remove("Arjun") drops that pair.
• get and getOrDefault behave exactly as before.
• The loop still prints in insertion order, Alex then Riya. Updating a value does not change a key’s place in line.

30
0
Alex -> 26
Riya -> 30

🔁 Access-order mode

So far the map kept keys in the order you added them. There is a second mode that reorders keys by use. This is called access order.

• Every time you touch a key with get or put, that key jumps to the end of the line as “most recently used”.
• Keys you have not touched in a while drift toward the front.
• You turn this on with a three-argument constructor and pass true for the last value.

import java.util.LinkedHashMap;

public class Main {
    public static void main(String[] args) {
        // initial size 16, load factor 0.75, accessOrder = true
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
        map.put("a", 1);
        map.put("b", 2);
        map.put("c", 3);

        map.get("a");                 // ✅ touching "a" moves it to the end

        System.out.println(map);
    }
}

Here is what happens:

• We added a, b, c in that order.
• We called get("a"). In access order, reading “a” counts as using it.
• So “a” moves to the back. Now the order runs b, c, a.
• The thing you used most recently sits last. That single behaviour leads to something useful.

{b=2, c=3, a=1}

🗃️ A simple LRU cache

Access order leads straight to a famous tool, the LRU cache.

• LRU stands for “least recently used”.
• A cache is a small box that holds a limited number of items for quick reuse.
• When the box is full and a new item arrives, you throw out the one you have not used for the longest time.
• In access-order mode, that least recently used key is always at the front.
• You override one method, removeEldestEntry, to say “drop the front entry once we go over the limit”.

import java.util.LinkedHashMap;
import java.util.Map;

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    LruCache(int capacity) {
        super(16, 0.75f, true);          // access order on
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;        // ✅ drop the oldest when too big
    }
}

public class Main {
    public static void main(String[] args) {
        LruCache<String, Integer> cache = new LruCache<>(3);
        cache.put("a", 1);
        cache.put("b", 2);
        cache.put("c", 3);

        cache.get("a");                  // use "a", so "b" is now the oldest
        cache.put("d", 4);               // over capacity, evict the oldest

        System.out.println(cache);
    }
}

Let’s walk through it:

• The cache holds at most three items. We add a, b, c, filling it.
• get("a") marks “a” as recently used, pushing “b” to the front as the oldest.
• put("d", 4) takes the map to four entries, so removeEldestEntry returns true.
• The front entry, “b”, is evicted. We are left with a, c, d.
• removeEldestEntry runs automatically after every put. Java handles the eviction for you.

{c=3, a=1, d=4}

📊 HashMap vs LinkedHashMap vs TreeMap

These three maps share the same methods. The only real question is what order you want and how fast you need it.

The short rule: use HashMap when order does not matter, LinkedHashMap when you want the order you put things in, and TreeMap when you want keys sorted automatically.

🛠️ When should you use it?

Reach for a LinkedHashMap whenever you need a map and a predictable iteration order:

• A “recently viewed” or “recently opened” list, where the order you added items is the order you show them.
• Reading a config file or form fields, where you want to keep the same order they appeared.
• Building an LRU cache, using access-order mode and removeEldestEntry.
• Any time you print or export a map and want the same output every run, not a shuffle.
• If you do not care about order, plain HashMap is slightly faster and lighter, so prefer it there.
• If you need keys sorted, that is TreeMap’s job, the next lesson.

⚠️ Common Mistakes

Slip-ups people hit with LinkedHashMap:

• Expecting sorted order. LinkedHashMap keeps insertion order, not sorted order. If you add keys out of order, they stay out of order. For sorted keys you need a TreeMap.

// ❌ wrong: a LinkedHashMap does NOT sort keys
LinkedHashMap<Integer, String> m = new LinkedHashMap<>();
m.put(3, "three");
m.put(1, "one");
m.put(2, "two");
System.out.println(m);   // {3=three, 1=one, 2=two}, the order you added

// ✅ right: use TreeMap when you want keys sorted
TreeMap<Integer, String> sorted = new TreeMap<>();
sorted.put(3, "three");
sorted.put(1, "one");
sorted.put(2, "two");
System.out.println(sorted);   // {1=one, 2=two, 3=three}

• Forgetting to turn on access order for an LRU cache. The default constructor uses insertion order. If you want the most recently used key to move to the end, you must pass true as the third constructor argument.

// ❌ insertion order: get() does NOT move the key, so LRU eviction is wrong
LinkedHashMap<String, Integer> cache = new LinkedHashMap<>();

// ✅ access order: get() and put() move keys to the end
LinkedHashMap<String, Integer> cache = new LinkedHashMap<>(16, 0.75f, true);

• Assuming it is thread-safe. Like HashMap, a LinkedHashMap is not safe for several threads writing at once. If many threads share one, wrap it or use a concurrent map.

✅ Best Practices

Habits for using LinkedHashMap well:

• Pick it for order, not speed. Use it when predictable iteration order matters. For pure speed with no order needs, plain HashMap is a touch lighter.
• Declare both types. LinkedHashMap<String, Integer> makes the key and value types clear and lets the compiler catch mistakes.
• Reuse the HashMap methods you know. getOrDefault, merge, and entrySet all work the same, so use them just as you did with HashMap.
• Only switch on access order when you really mean it. The three-argument constructor with true is for LRU-style behaviour. Leave it off if you just want insertion order.
• For an LRU cache, subclass and override removeEldestEntry. It is the clean, built-in way to cap the size and evict the oldest entry automatically.

🧩 What You’ve Learned

Nicely done. Let’s recap LinkedHashMap.

• ✅ A LinkedHashMap is a map that keeps keys in insertion order, fixing HashMap’s lack of order.
• ✅ It is backed by a hash table plus a linked list, so you get HashMap speed plus a predictable order.
• ✅ It has the same methods as HashMap. Just swap the type and everything works.
• ✅ Access-order mode (the three-argument constructor with true) moves a key to the end each time you use it.
• ✅ That mode plus removeEldestEntry gives you a simple LRU cache in a few lines.

🚀 What’s Next?

A LinkedHashMap remembers the order you added keys. But what if you want the keys kept in sorted order automatically, no matter how you add them? Java has the TreeMap for that. Let’s learn it next.

Java TreeMap