LinkedHashMap<K, V> is an implementation of Java's Map interface that combines hash-based lookup with a predictable iteration order. Like HashMap, it is designed for efficient key-based operations. Unlike a plain HashMap, it also maintains an order in which entries are visited.

This is useful when an application needs both quick lookup and stable display order. For example, a shopping cart may need to display products in the order the customer added them, while a “recently viewed” panel may need to keep the most recently accessed products at the end.

LinkedHashMap supports two ordering modes:

• Insertion order: entries are visited in the order in which they were inserted.
• Access order: entries are arranged according to access activity, making the structure useful for least-recently-used (LRU) cache designs.

The class extends HashMap, inheriting its general hash-table approach while adding links between entries to maintain the selected order.

2. Why Order Matters

A regular HashMap does not guarantee insertion order or sorted order. Its iteration sequence depends on its internal buckets, hashes, and capacity. That may be acceptable for internal lookup, but it becomes a problem when the order is visible to users or must remain predictable.

Consider a shopping cart where a customer adds a notebook, a pen, and then an eraser. A user-friendly cart may be expected to show the products in that same order. A HashMap does not promise this behavior. A LinkedHashMap using its default constructor preserves the insertion order.

The key benefit is that the map retains the familiar key-value API while making iteration order predictable.

3. How LinkedHashMap Stores Entries

LinkedHashMap extends HashMap. It uses a hash table for lookup and adds a doubly linked list that connects entries in the order they should be visited.

Each linked entry has references to the previous and next entries in that ordering. Conceptually, the structure combines two separate mechanisms:

• Hash buckets determine where lookup searches for a key.
• The linked list determines the order in which iteration visits entries.

When a new key-value pair is inserted, the map locates the appropriate bucket using hashing and also links the new entry into the order list. When an entry is removed, it is removed from both the bucket structure and the linked list. In access-order mode, an access to an existing entry can move that entry to the tail of the list.

The list does not replace the hash table. It overlays ordering information on top of the hash-based storage.

4. Lookup, Insertion, and Removal

Because LinkedHashMap inherits the hash-table approach, its typical key-based operations have expected O(1) performance when keys are distributed well.

4.1 Lookup with get()

A lookup uses the hash table to find the appropriate bucket and then searches candidate entries. It does not need to walk the linked order list to find the key.

In insertion-order mode, a normal get() does not rearrange the entries. In access-order mode, a successful access to an existing entry moves that entry to the most-recently-used end of the linked list.

4.2 Insertion with put()

For a new key, put() stores the mapping and adds it to the end of the linked order. In insertion-order mode, this means the new entry becomes the latest inserted entry.

Putting a value for a key that already exists replaces the mapping's value rather than creating a duplicate key. In access-order mode, putting an existing key counts as an access and can move the entry to the tail.

4.3 Removal with remove()

Removing an entry deletes the mapping and unlinks it from the ordering list. Since the entry maintains links to its neighbors, unlinking it is a constant-time list operation once the entry has been located through the map.

5. Insertion Order and Access Order

The constructor determines which ordering mode is used. The no-argument constructor uses insertion order. The three-argument constructor has the form:

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

The capacity and load-factor arguments have roles similar to those in HashMap. The accessOrder argument selects the ordering policy:

• false selects insertion order.
• true selects access order.

5.1 Insertion-order mode

In insertion-order mode, entries appear in the order in which new mappings were inserted. Replacing the value of an existing key does not create a new entry or ordinarily move it to a different position.

This mode is appropriate for ordered carts, predictable reports, and other interfaces where the order of addition matters.

5.2 Access-order mode

In access-order mode, entries are ordered by access activity. Accessing an existing entry moves it to the end of the list, which represents the most recently used end. The entry at the head is the least recently used.

The physical bucket placement of an entry does not need to change when its position in the ordering list changes. The map can update its access order while still using the hash table for lookup.

5.3 Which operations count as accesses?

In the access-order behavior described by the source lesson, get() and put() of an existing key count as accesses. Insertion of a new key adds it to the end. Operations such as containsKey(), containsValue(), and iteration through the collection views do not reorder entries.

Access-order mode is useful when the most recently used entries should be kept easy to identify, especially for cache eviction policies.

6. Building a Bounded LRU Cache

An LRU cache keeps recently used entries and removes the entry that has gone the longest without being accessed when the cache exceeds its size limit. Access-order LinkedHashMap provides the ordering mechanism needed for a simple LRU policy.

The method removeEldestEntry(Map.Entry<K,V> eldest) can be overridden to decide whether the oldest entry should be removed after a new mapping is inserted. If the method returns true, the eldest entry is evicted.

A bounded cache generally follows this logic:

1. Configure the map for access order.
2. Set a maximum number of entries.
3. Insert new mappings normally.
4. After insertion, check whether the map has exceeded the maximum.
5. Evict the eldest entry when the size is too large.

6. Whiteboard

   Loading diagram...

   
   

6.1 Why the size check is usually size() > maximum

removeEldestEntry() is consulted after the new entry has already been inserted. As a result, the map can temporarily contain one more entry than the intended maximum. A check using size() > maximum removes the eldest entry once the limit has been exceeded.

6.2 Keep the eviction check inexpensive

The removeEldestEntry() method is consulted after insertions, so the decision should be cheap. A simple size comparison is appropriate for a basic bounded cache. Scanning all entries every time would add unnecessary work.

The eldest entry passed to the method can also be inspected if an eviction rule depends on its key or value rather than size alone. A named subclass can be used when the cache behavior needs to be reused.

6.3 Limits of a simple LRU map

A LinkedHashMap-based LRU cache is a useful simple design, but LinkedHashMap is not synchronized. In access-order mode, even a read such as get() changes the ordering list. Concurrent accesses therefore require careful coordination. For demanding concurrent cache workloads, a cache library designed for concurrency may be more suitable.

7. When to Use LinkedHashMap

Choose LinkedHashMap when you need a predictable encounter order alongside hash-based lookup.

Common use cases include:

• Shopping carts: preserve the order in which items were added.
• Recently viewed products: move viewed products to the recent end and discard old entries when a limit is reached.
• Small session caches: keep a bounded set of recently used sessions.
• Ordered output: generate predictable reports or display records in insertion order.
• Order-sensitive processing: preserve insertion order when downstream processing or presentation depends on it.

LinkedHashMap is not the right tool when keys must always be sorted according to their natural order or a comparator; TreeMap is designed for that purpose. It may also be unnecessary for extremely large maps where iteration order has no value and the additional per-entry links consume significant memory.

8. Performance Characteristics

For ordinary workloads, LinkedHashMap has similar expected complexity to HashMap for core key-based operations.

These are typical high-level expectations, not unconditional guarantees for all key distributions or implementations.

8.1 Iteration can be efficient

LinkedHashMap iteration walks the linked list and visits each entry in the defined order. A HashMap iterator may scan the bucket array, including empty buckets, before following bucket chains. Consequently, when a map has a large capacity but relatively few entries, LinkedHashMap iteration can be more efficient in practice despite both operations being described at a high level as O(n).

8.2 Memory overhead

Each linked entry stores ordering references in addition to the data required by the hash-table entry. That adds memory overhead compared with HashMap. The exact number of bytes depends on JVM architecture, object layout, compressed references, and implementation version, so fixed byte estimates should be treated as approximate rather than universal.

For a modest map, the overhead may be insignificant. For a very large map, it can become meaningful. Use LinkedHashMap when the ordering guarantee provides real value, not automatically for every key-value lookup.

9. LinkedHashMap vs HashMap vs TreeMap

The right choice depends on the requirement, not just on which class has the most features. If order is irrelevant, HashMap is often simpler and more memory-efficient. If insertion order matters, use LinkedHashMap. If key sorting is required, use TreeMap.

10. Thread Safety

LinkedHashMap is not synchronized by default. Multiple threads should not modify a shared instance without an appropriate synchronization strategy.

A synchronized wrapper can coordinate access to a map, but iteration and compound actions still require following the wrapper's synchronization rules. Access-order mode deserves particular care because get() can change the list order; it is not necessarily a read-only operation from a structural perspective.

For concurrent LRU caching, consider a cache library built for concurrent workloads rather than assuming a synchronized wrapper automatically delivers an efficient concurrent cache. ConcurrentHashMap provides concurrent lookup and update behavior but does not maintain insertion or access order.

11. Common Mistakes

Mistake 1: Expecting HashMap to preserve insertion order

A HashMap does not promise this. Use LinkedHashMap when insertion order is a requirement.

Mistake 2: Assuming LinkedHashMap sorts keys

Insertion order and sorted order are different. Use TreeMap when keys must be sorted.

Mistake 3: Confusing insertion order with access order

The default constructor uses insertion order. Access-order mode must be requested explicitly through the constructor that accepts accessOrder.

Mistake 4: Thinking access order automatically evicts entries

Access-order mode only maintains recency order. A size limit and an eviction policy, such as overriding removeEldestEntry(), are needed to bound the map.

Mistake 5: Using >= without understanding the eviction timing

Because the eldest-entry decision is made after insertion, checking whether the size is greater than the maximum is the usual pattern for a strict maximum.

Mistake 6: Ignoring memory overhead

Linked ordering requires extra references per entry. If ordering has no value, HashMap may be a better choice for a large data set.

Mistake 7: Assuming LinkedHashMap is thread-safe

It is not synchronized by default. Access-order lookups can mutate the order list, so concurrent access requires deliberate design.

12. Best Practices

1. Use the default LinkedHashMap constructor when insertion order is the requirement.
2. Enable access order only when the application needs recency-based ordering.
3. Use removeEldestEntry() for a simple bounded LRU-style map, and keep the decision inexpensive.
4. Prefer HashMap when iteration order is irrelevant.
5. Prefer TreeMap when sorted keys or range-based operations are required.
6. Account for the extra memory used by linked entry references when working with very large maps.
7. Do not depend on an ordering guarantee unless the chosen implementation documents it.
8. Treat access-order get() as an operation that can update recency state.
9. Coordinate shared access explicitly; do not assume the map is thread-safe.
10. Use a concurrency-focused cache library for demanding concurrent LRU workloads.

13. Quick Revision

• LinkedHashMap extends HashMap and implements the Map interface.
• It combines hash-based lookup with a doubly linked list of entries.
• The default mode preserves insertion order.
• Access-order mode moves accessed entries toward the most-recently-used end.
• get() and put() of an existing key count as accesses in access-order mode; membership checks and iteration do not reorder entries in the source lesson's described behavior.
• removeEldestEntry() can support a simple bounded LRU cache.
• Since eviction is checked after insertion, a size-based policy commonly checks size() > maximum.
• Core key operations have expected O(1) behavior under typical conditions.
• Iteration walks the linked list and can be efficient for sparse maps.
• Extra ordering links consume more memory than a plain HashMap.
• LinkedHashMap is not synchronized by default.
• Use HashMap for general unordered lookup and TreeMap for sorted keys.

14. Conclusion

LinkedHashMap is a useful choice when a Java application needs the efficient key-based lookup of a hash map and a predictable order for iteration. Its linked list records either insertion order or access order, depending on how the map is constructed.

The access-order mode also makes a simple bounded LRU cache possible when combined with removeEldestEntry(). The trade-offs are additional memory for the linked entries and the need to coordinate access in multithreaded programs. Choose LinkedHashMap when order matters, HashMap when it does not, and TreeMap when keys must be sorted.