Java LinkedHashMap is a HashMap that also links its entries in a doubly linked list, so iterating over it returns the entries in the order we inserted them, or in access order when we ask for it. Lookups by key still take constant time, as in a HashMap.
We use LinkedHashMap when the order of the keys matters to the reader of our data, for example the fields of a JSON response, the columns of a CSV export or a list of recently opened files. Since Java 21 it implements SequencedMap, so it also gives us the first and the last entry in one call.
The following example stores fruit stock in a LinkedHashMap and shows the operations this article covers.
LinkedHashMap<String, Integer> stock = new LinkedHashMap<>();
stock.put("apple", 5);
stock.put("banana", 3);
stock.put("cherry", 8);
Set<String> keys = stock.keySet(); // [apple, banana, cherry]
Integer oldApple = stock.put("apple", 6); // 5, apple keeps its position
Map.Entry<String, Integer> first = stock.firstEntry(); // apple=6
Map.Entry<String, Integer> last = stock.lastEntry(); // cherry=8
SequencedMap<String, Integer> reversed = stock.reversed(); // {cherry=8, banana=3, apple=6}Notice that updating apple did not move it to the end. We start with the linked list behind that behavior, compare insertion order with access order, and build a small LRU cache with removeEldestEntry().
1. How LinkedHashMap Keeps Its Order
A LinkedHashMap extends HashMap, so it stores every entry in the same array of buckets and finds a key by its hash code. Each entry also carries two extra references, before and after, which chain all entries into one doubly linked list. The map keeps references to the head and the tail of that list.
Iteration walks the linked list from head to tail and never touches the bucket array. That is why the order is predictable, whereas a plain HashMap returns its entries in bucket order, which depends on the hash codes and the table size. The three common Map implementations differ mainly in that order.
| Feature | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
| Iteration order | None guaranteed | Insertion order, or access order | Sorted by key |
| get(), put(), remove() | O(1) on average | O(1) on average | O(log n) |
| Null key | One allowed | One allowed | Not with natural ordering |
| Extra memory per entry | None | Two references (before, after) | Three references and a color flag |
| Implements SequencedMap (Java 21) | No | Yes | Yes, through SortedMap |
When we need the keys sorted rather than kept in arrival order, TreeMap is the right class. The Java Collections overview shows where all three fit in the framework.
2. Insertion-Ordered LinkedHashMap
By default, a LinkedHashMap keeps insertion order. A new key goes to the tail of the list, and putting an existing key again only replaces the value, so the key keeps its old position. If we want a key at the end, we either remove it and put it again or call putLast().
LinkedHashMap<String, Integer> columns = new LinkedHashMap<>();
columns.put("id", 1);
columns.put("name", 2);
columns.put("email", 3);
columns.put("id", 10);
String afterUpdate = columns.toString(); // "{id=10, name=2, email=3}"
columns.remove("name");
columns.put("name", 2);
String afterReinsert = columns.toString(); // "{id=10, email=3, name=2}"
columns.putLast("id", 10);
String afterPutLast = columns.toString(); // "{email=3, name=2, id=10}"Like HashMap, a LinkedHashMap accepts one null key and any number of null values. Copying another map with new LinkedHashMap<>(source) keeps the iteration order of the source map, which is handy when we receive a sorted map and want an ordered, mutable copy.
Say a reporting app exports orders to CSV, and the user picks the columns in a settings page. If the app stores the chosen columns in a HashMap, the header row can come out as email, id, name on one release and in another order after a JDK upgrade. With a LinkedHashMap, the columns appear in the order the user picked them, on every run.
3. First, Last and Reversed Entries With SequencedMap
Java 21 added the SequencedMap interface (JEP 431), and LinkedHashMap implements it. Before Java 21, getting the last entry of a LinkedHashMap meant iterating over the whole map. The sequenced collections API gives us both ends of the map in constant time.
| Method | What it does on a LinkedHashMap |
|---|---|
| firstEntry(), lastEntry() | Returns the first or the last entry, or null if the map is empty |
| pollFirstEntry(), pollLastEntry() | Removes and returns the first or the last entry |
| putFirst(k, v), putLast(k, v) | Inserts the entry at the front or the end, and moves the key there if it already exists |
| reversed() | Returns a reverse-ordered view that is backed by the map |
| sequencedKeySet(), sequencedValues(), sequencedEntrySet() | Returns views that also support reversed(), getFirst() and getLast() |
LinkedHashMap<String, Integer> queue = new LinkedHashMap<>();
queue.put("anna", 1);
queue.put("bob", 2);
queue.put("carl", 3);
Map.Entry<String, Integer> next = queue.pollFirstEntry(); // anna=1
queue.putFirst("dina", 0);
String order = queue.toString(); // "{dina=0, bob=2, carl=3}"
String lastKey = queue.sequencedKeySet().getLast(); // "carl"
List<String> backwards = List.copyOf(queue.reversed().keySet()); // [carl, bob, dina]The entries returned by firstEntry() and lastEntry() are snapshots, so calling setValue() on them throws UnsupportedOperationException. To change a value, we call put() on the map. The reversed() view is live, so writing through it changes the original map.
4. Access-Ordered LinkedHashMap
A LinkedHashMap can also order its entries from the least recently accessed to the most recently accessed. We switch this mode on with the three-argument constructor and accessOrder set to true. After that, every access moves the entry to the tail of the list.
The methods put(), putIfAbsent(), get(), getOrDefault(), compute(), computeIfAbsent(), computeIfPresent() and merge() count as an access when the entry exists afterwards. Calls such as containsKey() and any operation on the keySet(), values() or entrySet() views do not change the order.
LinkedHashMap<String, Integer> views = new LinkedHashMap<>(16, 0.75f, true);
views.put("phone", 1);
views.put("laptop", 2);
views.put("watch", 3);
Integer laptop = views.get("laptop"); // 2, laptop moves to the end
boolean hasPhone = views.containsKey("phone"); // true, order unchanged
Integer tablet = views.getOrDefault("tablet", 0); // 0, no entry, order unchanged
String accessOrder = views.toString(); // "{phone=1, watch=3, laptop=2}"A shopping site shows a “Recently viewed” strip. Every time a user opens a product page, the app calls get() or put() for that product, and the newest product ends up at the tail. Reading views.reversed().keySet() gives the products from the newest to the oldest, ready for display.
In access order, even get() changes the internal list, so an access-ordered map needs synchronization for reads too when several threads share it.
5. Building an LRU Cache With removeEldestEntry()
An LRU (least recently used) cache keeps a fixed number of entries and drops the one that nobody used for the longest time. An access-ordered LinkedHashMap already keeps that entry at the head. The map calls the protected removeEldestEntry() method after each insert, and if the method returns true, the map removes the head entry.
class LruCache<K, V> extends LinkedHashMap<K, V> {
private final int maxEntries;
LruCache(int maxEntries) {
super(16, 0.75f, true);
if (maxEntries < 1) {
throw new IllegalArgumentException("maxEntries must be at least 1");
}
this.maxEntries = maxEntries;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxEntries;
}
}The following example caches currency rates for a checkout page, with room for two entries. Reading USD makes it the most recently used entry, so adding GBP evicts EUR.
LruCache<String, Double> rates = new LruCache<>(2);
rates.put("USD", 1.0);
rates.put("EUR", 0.92);
Double usd = rates.get("USD"); // 1.0
rates.put("GBP", 0.79);
String cached = rates.toString(); // "{USD=1.0, GBP=0.79}"
boolean hasEur = rates.containsKey("EUR"); // falseThe default implementation of removeEldestEntry() returns false, so a plain LinkedHashMap never evicts anything. The hook also works with insertion order, which gives a FIFO cache that evicts the oldest inserted entry instead of the least recently used one.
The LruCache class is not thread-safe. For a cache shared by request threads, we either wrap it with Collections.synchronizedMap(new LruCache<>(100)) or use a cache library. Caffeine gives size-based eviction, expiry and statistics without a global lock, which the synchronized wrapper cannot do.
6. Creating a LinkedHashMap With the Right Capacity
The int argument of new LinkedHashMap<>(100) is the initial table capacity, not the number of entries we plan to store. With the default load factor of 0.75, the map rounds the table up to 128 buckets and resizes after 96 entries, before it reaches 100. Java 19 added the static factory LinkedHashMap.newLinkedHashMap(int), which takes the expected number of entries and computes the capacity for us.
LinkedHashMap<String, Integer> presized = LinkedHashMap.newLinkedHashMap(100); // holds 100 entries without resizing
LinkedHashMap<String, Integer> byCapacity = new LinkedHashMap<>(128); // table capacity 128
LinkedHashMap<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true); // access order
LinkedHashMap<String, Integer> copy = new LinkedHashMap<>(Map.of("a", 1)); // copies the entries
int copied = copy.size(); // 1The remaining constructors match HashMap. Only the three-argument form can switch on access order, and every other constructor creates an insertion-ordered map.
7. LinkedHashMap Performance and Thread Safety
The basic operations get(), put(), containsKey() and remove() run in constant time on average, as in HashMap. Each insert and removal also updates two links, and each entry holds two more references, so a LinkedHashMap is a little slower to write and uses a little more memory than a HashMap of the same size.
Iteration is the one place where LinkedHashMap can be faster. It follows the linked list, so the time depends only on the number of entries. A HashMap walks its whole bucket array, so iterating over a large, mostly empty table costs time for the empty buckets as well.
A LinkedHashMap is not synchronized, and its iterators are fail-fast, which means they throw ConcurrentModificationException when the map changes structurally during iteration. The JDK has no concurrent map that keeps insertion order, so shared access needs one of three approaches.
- Wrap the map with Collections.synchronizedMap() and hold the wrapper’s lock while iterating. The article on synchronizing a HashMap shows the pattern.
- Use ConcurrentHashMap when the order does not matter.
- Use ConcurrentSkipListMap when sorted order is enough instead of insertion order.
Map<String, Integer> shared = Collections.synchronizedMap(new LinkedHashMap<>());
shared.put("first", 1);
shared.put("second", 2);
List<String> snapshot;
synchronized (shared) {
snapshot = List.copyOf(shared.keySet());
}
List<String> safeCopy = snapshot; // [first, second]8. LinkedHashMap FAQs
Thread safety, speed and ordering rules come up most often when developers ask about LinkedHashMap.
8.1. Is LinkedHashMap thread-safe?
No. Several threads that write to the same LinkedHashMap can corrupt the linked list. Wrap it with Collections.synchronizedMap(), as shown in section 7, or use a concurrent map when the order is not needed.
8.2. Is HashMap faster than LinkedHashMap?
Slightly, for writes. A LinkedHashMap updates two extra links on every insert and removal, while lookups cost the same. Iteration over a LinkedHashMap can be faster, because it does not visit empty buckets.
8.3. Does putting an existing key change the order of a LinkedHashMap?
No, not in insertion order. The value is replaced and the key stays where it was. In access order, put() counts as an access and moves the key to the end, and in both modes putLast() moves the key to the end.
8.4. How do we get the first and last entry of a LinkedHashMap?
On Java 21 and later, we call firstEntry() and lastEntry(). On older versions, the first entry is map.entrySet().iterator().next(), and the last entry requires iterating to the end.
8.5. How do we sort a LinkedHashMap by value?
We stream the entries, sort them with Map.Entry.comparingByValue() and collect them into a new LinkedHashMap, because the map itself cannot be reordered in place.
Map<String, Integer> scores = Map.of("anna", 7, "bob", 9, "carl", 5);
LinkedHashMap<String, Integer> byScore = scores.entrySet().stream()
.sorted(Map.Entry.comparingByValue())
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (a, b) -> a, LinkedHashMap::new));
String sorted = byScore.toString(); // "{carl=5, anna=7, bob=9}"The article on sorting a map by values covers descending order and ties.
9. Conclusion
A LinkedHashMap is a HashMap plus a doubly linked list through its entries. It keeps insertion order by default, and updating an existing key leaves the order unchanged.
Since Java 21, the SequencedMap methods give us the first and last entries, a reversed view and putFirst()/putLast(). With access order and removeEldestEntry(), the same class becomes an LRU cache in about ten lines, as long as we add synchronization or switch to a cache library when threads share it.
10. References
Happy Learning !!
