LinkedHashMap
Sometimes an application needs the fast key-based lookup of a HashMap, but it also needs the entries to be processed in a predictable order. This is where LinkedHashMap becomes useful.
LinkedHashMap is a Map implementation that combines hash-based key-value storage with a linked structure that maintains a predictable iteration order. By default, that order is the insertion order.
Core Idea: LinkedHashMap gives you HashMap-style key-based lookup while maintaining a predictable order for iteration.
Why Does LinkedHashMap Exist?
Imagine processing product records received from an external system. You want to remove duplicate keys, retrieve records quickly by ID, and still display the records in the same order in which they were added.
Map<Integer, String> products =
new LinkedHashMap<>();
products.put(101, "Laptop");
products.put(102, "Keyboard");
products.put(103, "Mouse");
System.out.println(products);
Unlike HashMap, LinkedHashMap guarantees predictable iteration order. The entries are visited in their insertion order by default.
Simple analogy: Think of LinkedHashMap as a dictionary that remembers the order in which each word was first added.
LinkedHashMap Hierarchy
LinkedHashMap extends HashMap and implements the Map contract.
Map
|
+-- HashMap
|
+-- LinkedHashMap
This means LinkedHashMap provides the familiar Map operations while adding predictable iteration ordering.
Creating a LinkedHashMap
import java.util.LinkedHashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.put(103, "Priya");
System.out.println(employees);
}
}
Using Map as the reference type keeps the code focused on the required abstraction.
Adding Elements with put()
LinkedHashMap uses put() to create or update mappings.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.put(103, "Priya");
Each key identifies one mapping, while its value stores the associated information.
Duplicate Keys
Like HashMap, LinkedHashMap does not allow multiple mappings for the same key.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.put(101, "Bibhu Kumar");
System.out.println(
employees.get(101)
);
The second put() replaces the existing value associated with key 101.
Key Rule: Keys are unique. Values may be duplicated.
Duplicate Values
Different keys can point to the same value.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Developer");
employees.put(102, "Developer");
employees.put(103, "Tester");
System.out.println(employees);
Both 101 and 102 can map to Developer because Map uniqueness applies to keys, not values.
Insertion Order
The most important feature of LinkedHashMap is its predictable insertion-order iteration.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(103, "Priya");
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
for (Map.Entry<Integer, String> entry
: employees.entrySet()) {
System.out.println(
entry.getKey()
+ " = "
+ entry.getValue()
);
}
The entries are iterated as 103, 101, and 102 because that is the order in which the keys were first inserted.
Important: LinkedHashMap maintains insertion order by default. It does not automatically sort entries by key or value.
What Happens When an Existing Key Is Updated?
Updating an existing key replaces its value. In the default insertion-order mode, the key retains its original position.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.put(103, "Priya");
employees.put(101, "Bibhu Kumar");
System.out.println(employees);
Key 101 remains in its original insertion position. Updating its value does not make it a newly inserted key for normal insertion-order behavior.
Remember: Replacing the value of an existing key does not normally move that key to the end when the map is using insertion-order mode.
Access-Order Mode
LinkedHashMap has a particularly interesting feature: it can also maintain entries according to access order.
LinkedHashMap<Integer, String> employees =
new LinkedHashMap<>(
16,
0.75f,
true
);
The third constructor argument enables access-order mode. In this mode, accessing an existing entry can move it toward the end of the iteration order.
Access-Order Example
LinkedHashMap<Integer, String> employees =
new LinkedHashMap<>(
16,
0.75f,
true
);
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.put(103, "Priya");
employees.get(101);
System.out.println(employees);
After accessing key 101, the access-order behavior can move that entry toward the end of the iteration sequence.
Advanced Insight: Access-order mode is particularly useful for implementing cache-like structures because recently accessed entries can be tracked naturally.
Insertion Order vs Access Order
| Feature | Insertion Order | Access Order |
|---|---|---|
| Default mode | Yes | No |
| Order based on | First insertion | Recent access activity |
| Existing key accessed | Position normally remains unchanged | Entry can move toward the end |
| Typical use | Predictable output and processing order | Cache-style access tracking |
Getting a Value
LinkedHashMap supports the normal Map get() method.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
String name =
employees.get(101);
System.out.println(name);
The value associated with key 101 is returned.
containsKey()
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
if (employees.containsKey(101)) {
System.out.println(
"Employee exists"
);
}
containsKey() checks whether a mapping exists for the specified key.
containsValue()
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
if (employees.containsValue("Rahul")) {
System.out.println(
"Value found"
);
}
Value lookup generally requires examining multiple entries and is not the primary strength of a hash-based Map.
Removing Elements
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.remove(101);
System.out.println(employees);
remove() deletes the mapping associated with the specified key.
putIfAbsent()
putIfAbsent() adds a mapping only when the key is not already mapped to a value.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.putIfAbsent(
101,
"Rahul"
);
System.out.println(
employees.get(101)
);
The existing value remains unchanged because key 101 already has a mapping.
getOrDefault()
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
String name =
employees.getOrDefault(
999,
"Unknown"
);
System.out.println(name);
This method provides a fallback value when the requested key does not have a mapping.
Iterating Through LinkedHashMap
Because LinkedHashMap maintains predictable ordering, iteration is especially useful when the order of processing matters.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.put(103, "Priya");
for (Map.Entry<Integer, String> entry
: employees.entrySet()) {
System.out.println(
entry.getKey()
+ " = "
+ entry.getValue()
);
}
The entries are processed in their maintained order.
Iterating Through Keys
for (Integer id : employees.keySet()) {
System.out.println(id);
}
keySet() provides a view of the keys and follows the map's iteration order.
Iterating Through Values
for (String name : employees.values()) {
System.out.println(name);
}
values() provides the values in the same iteration sequence represented by the map.
Using forEach()
employees.forEach(
(id, name) ->
System.out.println(
id + " = " + name
)
);
This is a concise way to process each mapping.
entrySet(), keySet(), and values()
| Method | Returns | Best Use |
|---|---|---|
| keySet() | Set of keys | When only keys are needed. |
| values() | Collection of values | When only values are needed. |
| entrySet() | Set of key-value entries | When both keys and values are needed. |
LinkedHashMap and Null
LinkedHashMap inherits the relevant null-handling behavior of HashMap. It permits one null key and multiple null values.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(null, "Unknown");
employees.put(101, null);
employees.put(102, null);
System.out.println(employees);
Remember: One null key is allowed, while multiple different keys can map to null values.
HashMap vs LinkedHashMap
| Feature | HashMap | LinkedHashMap |
|---|---|---|
| Key-value storage | Yes | Yes |
| Duplicate keys | Not allowed | Not allowed |
| Duplicate values | Allowed | Allowed |
| Insertion order | Not guaranteed | Maintained |
| Access-order mode | No | Yes |
| Average get() | O(1) | O(1) |
| Average put() | O(1) | O(1) |
| Memory overhead | Generally lower | Generally higher |
| Typical use | Fast key-based lookup without ordering requirements | Fast key-based lookup with predictable ordering |
LinkedHashMap vs TreeMap
| Feature | LinkedHashMap | TreeMap |
|---|---|---|
| Key-value storage | Yes | Yes |
| Insertion order | Maintained | No |
| Sorted keys | No | Yes |
| Typical basic lookup | O(1) average | O(log n) |
| Ordering mechanism | Linked insertion/access order | Comparable or Comparator |
| Typical use | Unique keys with predictable insertion order | Sorted keys and navigation operations |
Using LinkedHashMap to Remove Duplicate Keys
Suppose a sequence of records contains repeated IDs, and you want to keep the first occurrence order while ensuring that each ID appears only once.
Map<Integer, String> employees =
new LinkedHashMap<>();
employees.put(101, "Bibhu");
employees.put(102, "Rahul");
employees.put(101, "Bibhu Kumar");
employees.put(103, "Priya");
System.out.println(employees);
The keys remain unique, while the order of the first insertion of each key is preserved. The value associated with 101 is updated to Bibhu Kumar.
Building an Ordered Lookup Table
LinkedHashMap works well when you need both quick lookup and deterministic processing order.
Map<String, Integer> priorities =
new LinkedHashMap<>();
priorities.put("Critical", 1);
priorities.put("High", 2);
priorities.put("Medium", 3);
priorities.put("Low", 4);
for (Map.Entry<String, Integer> entry
: priorities.entrySet()) {
System.out.println(
entry.getKey()
+ " = "
+ entry.getValue()
);
}
The Map provides fast lookup by priority name while maintaining the meaningful order in which the priorities were defined.
LinkedHashMap for Cache-Like Behavior
One of LinkedHashMap's most interesting advanced uses is implementing a simple cache structure with access-order mode.
LinkedHashMap<Integer, String> cache =
new LinkedHashMap<>(
16,
0.75f,
true
) {
@Override
protected boolean removeEldestEntry(
Map.Entry<Integer, String> eldest
) {
return size() > 3;
}
};
This pattern can automatically remove the eldest entry when the cache exceeds a chosen size. With access-order enabled, the structure can be used as the foundation for a simple least-recently-used style cache.
Industry Insight: LinkedHashMap is useful for cache-like designs because it can track access order and provides the removeEldestEntry() extension point.
Understanding removeEldestEntry()
The removeEldestEntry() method allows a subclass to decide whether the oldest entry should be removed after a new mapping is inserted.
@Override
protected boolean removeEldestEntry(
Map.Entry<Integer, String> eldest
) {
return size() > 100;
}
In this example, the Map can be limited to approximately 100 entries by returning true once the size exceeds the configured limit.
This feature is powerful, but production caching requirements may call for a dedicated caching library or framework when advanced eviction policies, expiration, concurrency, or observability are needed.
Performance Considerations
LinkedHashMap generally provides the same average-case hash-based complexity as HashMap for core operations, but it maintains additional links to preserve ordering.
| Operation | Typical Average Complexity | Notes |
|---|---|---|
| put() | O(1) | Hash-based insertion or update plus ordering maintenance. |
| get() | O(1) | Hash-based lookup. |
| containsKey() | O(1) | Hash-based key lookup. |
| remove() | O(1) | Hash lookup plus link maintenance. |
| containsValue() | O(n) | May require scanning values. |
| Iteration | O(n) | Traverses the maintained linked order. |
The exact performance depends on hashing, collisions, collection size, and implementation details. The main trade-off is simple: LinkedHashMap uses more memory than HashMap to provide predictable ordering.
Initial Capacity and Load Factor
LinkedHashMap supports constructors that allow you to configure initial capacity and load factor.
LinkedHashMap<Integer, String> employees =
new LinkedHashMap<>(
100,
0.75f
);
If you have a reasonable estimate of the number of mappings, choosing an appropriate initial capacity can reduce unnecessary resizing.
Common Beginner Mistakes
- Confusing insertion order with sorted order: LinkedHashMap preserves insertion order by default; it does not sort keys.
- Assuming updating a key moves it: In insertion-order mode, replacing an existing value does not normally move the key.
- Using LinkedHashMap when order is irrelevant: HashMap may be a simpler and lower-overhead choice.
- Using LinkedHashMap when sorted keys are required: TreeMap is designed for sorted key ordering.
- Ignoring access-order mode: The three-argument constructor can change iteration behavior significantly.
- Using mutable custom keys: Changing hash-relevant key state after insertion can break expected lookup behavior.
- Assuming thread safety: LinkedHashMap is not inherently thread-safe.
- Treating LinkedHashMap as a complete caching solution: Simple cache behavior is possible, but advanced production caching may require dedicated infrastructure.
Best Practices
- Use LinkedHashMap when key-based lookup and predictable iteration order are both important.
- Use insertion-order mode for deterministic processing and output.
- Use access-order mode when recently accessed entries need to be tracked.
- Use immutable or stable objects as keys whenever practical.
- Use entrySet() when both keys and values are required during iteration.
- Use HashMap when ordering is irrelevant.
- Use TreeMap when sorted key ordering or navigational operations are required.
- Do not assume LinkedHashMap provides thread safety.
Interview Insights
Question: What is LinkedHashMap?
Answer: LinkedHashMap is a Map implementation that uses hash-based lookup while maintaining a predictable iteration order, which is insertion order by default.
Question: How is LinkedHashMap different from HashMap?
Answer: Both provide hash-based key-value operations, but LinkedHashMap additionally maintains predictable iteration order and therefore has additional memory overhead.
Question: What is access-order mode?
Answer: Access-order mode makes the iteration sequence reflect recent access activity, allowing entries that are accessed to move toward the end of the ordering.
Question: What is removeEldestEntry() used for?
Answer: It provides a hook for removing the eldest entry after insertion, making LinkedHashMap useful for simple size-limited cache implementations.
Question: Does LinkedHashMap sort keys?
Answer: No. It maintains insertion order by default. TreeMap should be used when keys must remain sorted.
Question: Does updating an existing key change its insertion position?
Answer: In insertion-order mode, replacing the value normally does not change the key's position. Access-order mode behaves differently.
Quick Revision
| Concept | Key Point |
|---|---|
| LinkedHashMap | Hash-based Map that maintains predictable iteration order. |
| Keys | Must be unique. |
| Values | Can be duplicated. |
| Default order | Insertion order. |
| Access-order mode | Can order entries based on access activity. |
| put() | Adds or updates a mapping. |
| get() | Retrieves a value by key. |
| containsKey() | Checks whether a key exists. |
| Null key | One null key is allowed. |
| Null values | Multiple null values are allowed. |
| Average get/put/remove | Typically O(1). |
| Memory | Generally higher than HashMap because ordering links are maintained. |
| HashMap alternative | Use when ordering does not matter. |
| TreeMap alternative | Use when sorted key order is required. |
LinkedHashMap is an excellent example of a small change in requirements leading to a different collection choice. When you need HashMap-style key-based access but also need deterministic iteration, LinkedHashMap provides exactly that combination. Its access-order capability also makes it a useful building block for simple cache designs. In the next chapter, we will explore TreeMap, which takes the Map concept further by maintaining keys in sorted order and providing powerful navigation operations.