In Java, the LinkedHashMap is a part of the Java Collections Framework and extends the HashMap class. One of the key distinctions of LinkedHashMap is that it maintains a predictable iteration order, unlike HashMap, which does not guarantee any specific order.

Ordered Iteration in LinkedHashMap

Technical Explanation

LinkedHashMap is implemented by combining a linked list with a hash table. This combination ensures that the order of insertion is preserved when iterating over the keys, values, or entries. This is achieved through a doubly-linked list that runs through all entries. Each entry in the LinkedHashMap contains references to the previous and the next entries, allowing for ordered iteration.

Example

Here's a simple example to illustrate how ordered iteration in a LinkedHashMap works:

1import java.util.LinkedHashMap;
2import java.util.Map;
3
4public class LinkedHashMapExample {
5    public static void main(String[] args) {
6        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
7        map.put("Banana", 2);
8        map.put("Apple", 3);
9        map.put("Orange", 5);
10
11        for (Map.Entry<String, Integer> entry : map.entrySet()) {
12            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
13        }
14    }
15}

Output:

Key: Banana, Value: 2
Key: Apple, Value: 3
Key: Orange, Value: 5

As shown in the example above, the order of the entries when iterated is the same as the order in which the elements were inserted into the map.

Modes of Ordering

Insertion Order

By default, LinkedHashMap maintains the insertion order. This means that if the keys are inserted in the order of A, B, and C, they will be retrieved in that same order during iteration.

Access Order

LinkedHashMap has an optional mode that allows for ordering by access. If the access-order mode is enabled (by passing true as a second argument in the constructor), the iteration order will be based on the last access rather than insertion.

Example with Access Order:

1LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
2map.put("Banana", 2);
3map.put("Apple", 3);
4map.put("Orange", 5);
5
6// Access the "Banana" key
7map.get("Banana");
8
9for (String key : map.keySet()) {
10    System.out.println(key);
11}

Output:

Apple
Orange
Banana

In this example, although Banana was inserted first, it's printed last because it was accessed (by map.get("Banana")) after all elements were initially inserted.

Characteristics of LinkedHashMap

Here's a quick summary of the characteristics of LinkedHashMap:

Practical Uses of LinkedHashMap

Caching

The LinkedHashMap, especially with access order, is particularly useful for cache implementations. The access-order mode allows for the creation of LRU (Least Recently Used) caches, which automatically prune the least accessed entries. Overriding the removeEldestEntry method can help in implementing LRU Cache logic:

1LinkedHashMap<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
2    @Override
3    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
4        return size() > 5;
5    }
6};

This example code will ensure that once the map exceeds a size of 5, it will remove the eldest, i.e., least recently accessed entry.

Order-Preserving Tasks

Whenever maintaining order of elements is critical, like when elements are processed in the order they arrived or were last accessed, LinkedHashMap is an ideal choice.

Key Consistency with HashMap

While LinkedHashMap inherits from HashMap, it should be noted that if insertion order and equals behavior are consistent, a LinkedHashMap should behave equivalently to a typical HashMap.

This characteristic makes LinkedHashMap a powerful and flexible data structure for various ordering-related tasks while still maintaining the efficiency of hash-based access. Whether you aim to maintain order by design or need to facilitate an LRU cache system, LinkedHashMap offers a capability that sets it apart from a standard HashMap, showcasing both functionality and efficiency in Java collections.