Skip to content
Tutorials Center
My learning

Topics

Lesson 85 of 201 ยท Collections

LinkedHashMap and LinkedHashSet

Learn Java LinkedHashMap and LinkedHashSet - predictable insertion order, access order, an LRU cache with removeEldestEntry, and the Java 21 sequenced methods.

HashMap and HashSet are fast, but they scramble your data: iterate over them and the elements come out in bucket order, not in the order you added them. Often that's fine. Sometimes it isn't: a settings file should be written back in the same order it was read, a report should list categories in the order they first appeared, and a JSON response looks broken when its fields shuffle.

LinkedHashMap and LinkedHashSet fix this at a very small cost. They are a HashMap and a HashSet with one extra feature: every entry is also linked into a doubly linked list that remembers order. You keep O(1) lookups and gain predictable iteration. LinkedHashMap can even reorder itself on every read, which makes it the standard building block for LRU caches. This lesson covers both classes, access order, a working cache, and the sequenced methods added in Java 21.

How they work

Picture a normal hash table (see How HashMap Works Inside), and then thread a second chain through all of its entries: each entry has a before and an after pointer. Lookups still go through the buckets; iteration simply follows the chain from the oldest entry to the newest.

TEXT
buckets:   [0]      [1]        [2]      [3]
            |        |                   |
          "kiwi"   "apple"             "fig"

order chain:  head -> "apple" <-> "fig" <-> "kiwi" <- tail

The cost is two extra references per entry, so a little more memory, and slightly slower inserts and removals. Lookups are just as fast as in HashMap, and iteration is actually faster for sparse maps, because it walks only the entries instead of every bucket.

LinkedHashMap keeps insertion order

Use it exactly like a HashMap. The only visible difference is the order:

Java HashMap vs LinkedHashMap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Three rules about insertion order:

  • Updating an existing key with put changes the value but not the position.
  • Removing a key and adding it again moves it to the end.
  • Copying with new LinkedHashMap<>(otherMap) uses the other map's iteration order. Copy a HashMap and you capture its bucket order; copy a TreeMap and you capture sorted order.

A common use is counting while remembering first appearance, for example tallying words so the report lists them in the order the text introduced them:

Java Counting in order of first appearance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

merge(word, 1, Integer::sum) puts 1 for a new word or adds 1 to the existing count. It's covered with the other map methods in HashMap.

LinkedHashSet keeps insertion order too

LinkedHashSet is to HashSet what LinkedHashMap is to HashMap. Its best-known use is removing duplicates while keeping the original order, which neither a HashSet (scrambles) nor a TreeSet (sorts) can do:

Java Order-preserving deduplication

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Stream.distinct() on an ordered stream does the same job, keeping the first occurrence of each element. Both are O(n). Adding an element that's already present does not move it; it stays where it first appeared.

Access order: most recently used last

LinkedHashMap has a second ordering mode. Pass true as the third constructor argument and the chain is ordered by access instead of insertion: every time you read or write an entry, it moves to the end. The least recently used entry is always first.

Java
new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder)
new LinkedHashMap<>(16, 0.75f, true)   // access order
Java Watching access order move entries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

What counts as an access: get, getOrDefault, put and putIfAbsent on an existing key, and the compute/merge/replace family. What doesn't: containsKey, containsValue, and iterating over the map or its views.

In access-order mode, get changes the map's structure (it moves an entry). Calling get while you iterate over the same map therefore throws ConcurrentModificationException. Iterate over entrySet() and use the entry you already have instead of looking it up again.

Building an LRU cache

A cache has limited room, so when it's full something must go. The least recently used (LRU) policy evicts the entry nobody has touched for the longest time. Access order already keeps that entry at the front; all that's missing is a rule to drop it.

LinkedHashMap calls a protected hook, removeEldestEntry(Map.Entry eldest), after every put and putAll. It returns false by default. Override it to return true when the map is too big, and the map removes the eldest entry for you:

Java A complete LRU cache in a few lines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

That's a real, working LRU cache: O(1) lookups, O(1) eviction, no extra bookkeeping. For a cache that's shared between threads, wrap it with Collections.synchronizedMap(...) or, in production systems, use a dedicated caching library such as Caffeine, which adds concurrency, expiry by time and statistics.

You don't have to evict by size. removeEldestEntry can look at the eldest entry itself, for example to drop entries that are older than a time limit:

Java
@Override
protected boolean removeEldestEntry(Map.Entry<String, Session> eldest) {
    return eldest.getValue().lastSeen().isBefore(Instant.now().minus(Duration.ofMinutes(30)));
}

Keep in mind that the hook only runs during put, and it removes at most one entry per call.

Sequenced methods (Java 21)

Java 21 added the SequencedCollection, SequencedSet and SequencedMap interfaces for collections with a defined order (see The Collections Framework). LinkedHashSet and LinkedHashMap implement them, so you can finally reach the first and last elements directly instead of iterating:

LinkedHashSet LinkedHashMap What it does
getFirst(), getLast() firstEntry(), lastEntry() Peek at the ends
removeFirst(), removeLast() pollFirstEntry(), pollLastEntry() Remove and return an end
addFirst(e), addLast(e) putFirst(k, v), putLast(k, v) Insert at an end, moving it if already present
reversed() reversed() A reverse-ordered view
sequencedKeySet(), sequencedValues(), sequencedEntrySet() Views that support the methods above
Java First, last, reversed and moving to an end

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Notice the difference between put and putLast: put on an existing key leaves it where it is, while putLast moves it to the end. The same goes for add versus addLast on a LinkedHashSet.

The entries returned by firstEntry() and lastEntry() are snapshots: calling setValue on them throws UnsupportedOperationException. And reversed() returns a view, not a copy, so changes through it affect the original map.

Before Java 21, getting the last element of a LinkedHashSet meant iterating through the whole thing. If you work on older code bases you'll see loops or stream().reduce((a, b) -> b) doing exactly that. On Java 21 and later, use getLast().

When to choose them

Need Choose
Fastest map or set, order doesn't matter HashMap / HashSet
Iteration in insertion order LinkedHashMap / LinkedHashSet
Most recently used tracking, LRU caches LinkedHashMap with accessOrder = true
Sorted order, ranges, nearest key TreeMap / TreeSet

A few practical notes:

  • Sizing works as for HashMap: use LinkedHashMap.newLinkedHashMap(n) and LinkedHashSet.newLinkedHashSet(n) (Java 19+) when you know the expected number of entries.
  • Both classes allow one null key (or element) and null values, and neither is thread-safe.
  • Many libraries choose LinkedHashMap when they need a map whose order you can rely on. JSON libraries, for example, typically use it so that fields come out in the order they were read.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A LinkedHashMap in insertion order contains keys a, b, c. You call put("a", 5). What is the key order now?

    Updating an existing key with put keeps its position. Only removing it and adding it again (or putLast) moves it to the end.
  2. 2. A LinkedHashMap is created with accessOrder = true and holds keys x, y, z. You call get("x") and then containsKey("y"). What is the order?

    get counts as an access and moves x to the end. containsKey is not an access, so y stays where it is.
  3. 3. When does LinkedHashMap call removeEldestEntry?

    The map calls it after inserting through put or putAll. Return true to have the eldest entry removed.
  4. 4. What does new ArrayList<>(new LinkedHashSet<>(List.of(3, 1, 3, 2, 1))) contain?

    LinkedHashSet drops the duplicates and keeps each element at its first position, so the order of first appearance is 3, 1, 2.
  5. 5. A LinkedHashSet holds [a, b, c]. What does it hold after addFirst("c")?

    The Java 21 addFirst moves an existing element to the front. A plain add would leave the set unchanged.

Summary

  • LinkedHashMap and LinkedHashSet are hash-based collections that also link their entries in a list, giving predictable iteration with O(1) lookups.
  • In insertion order, updating a key keeps its position; removing and re-adding moves it to the end.
  • LinkedHashSet removes duplicates while keeping first-appearance order.
  • new LinkedHashMap<>(16, 0.75f, true) orders by access: get and put move an entry to the end, so the least recently used entry is first.
  • Override removeEldestEntry to evict automatically, which turns an access-ordered map into an LRU cache.
  • Since Java 21 both classes are sequenced: getFirst/getLast, firstEntry/lastEntry, addFirst/putLast (which move existing entries), poll methods and reversed() views.

Next: TreeMap and TreeSet, where you'll keep keys sorted and ask for the nearest, smallest and largest values and whole ranges.