Java LinkedHashMap

The Java LinkedHashMap Class

The LinkedHashMap class is a Map implementation that combines the features of a HashMap and a LinkedList.

It is a hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion order).

Key Characteristics of LinkedHashMap

• Key-Value Pairs: It stores items in key/value pairs.
• Unique Keys: Keys must be unique.
• Maintains Insertion Order: When you iterate over a LinkedHashMap, the entries will appear in the order they were added. This is its main advantage over HashMap.
• Fast Performance: It provides constant time performance (O(1)) for get and put operations, just like HashMap. This performance is likely to be slightly below that of HashMap, due to the added expense of maintaining the linked list.
• Allows null: A LinkedHashMap can have one null key and multiple null values.

How LinkedHashMap Works

A LinkedHashMap uses a hash table for storage, just like a HashMap, which gives it the fast O(1) performance. In addition, it embeds a doubly-linked list that connects all the entries in the order they were inserted.

When an entry is added, it's added to the hash table for fast lookups and also added to the end of the linked list to maintain the insertion order.

When to Use LinkedHashMap

LinkedHashMap is the perfect choice when you need to map keys to values and:

1. You require the entries to be stored in the order they were inserted.
2. You require high-speed access, insertion, and deletion.

It's a great middle-ground between the unordered, high-performance HashMap and the sorted, slower TreeMap. A common use case is creating a simple, fixed-size cache (using its removeEldestEntry method).

LinkedHashMap Example

Here is an example demonstrating the insertion-order behavior of a LinkedHashMap.

import java.util.LinkedHashMap;
import java.util.Map;

public class Main {
  public static void main(String[] args) {
    // Create a LinkedHashMap
    LinkedHashMap<String, Integer> itemPrices = new LinkedHashMap<>();
    // Add items
    itemPrices.put("Apple", 1);
    itemPrices.put("Bread", 3);
    itemPrices.put("Milk", 2);
    // The entries are iterated in the order they were inserted
    System.out.println("LinkedHashMap: " + itemPrices);
    // Accessing an element re-inserts it if accessOrder is true
    // (by default it is false)
    itemPrices.get("Apple");
    System.out.println("After accessing Apple: " + itemPrices);
    // Loop through the map
    System.out.println("--- Looping through items ---");
    for (Map.Entry<String, Integer> entry : itemPrices.entrySet()) {
      System.out.println("Item: " + entry.getKey() + ", Price: $" + entry.getValue());
    }
  }
}

Advanced: Creating an LRU Cache

One of the most powerful and common use cases for LinkedHashMap is building a Least Recently Used (LRU) Cache.

A cache holds recently used data for quick access, but memory is limited. An LRU cache automatically drops the oldest, least-used data when it gets full.

You can achieve this in LinkedHashMap by:

1. Using a special constructor parameter (accessOrder = true) so that every time an entry is read using get(), it is moved to the end of the list (making it the "most recently used").
2. Overriding the removeEldestEntry method to tell the map to drop the oldest entry when the size exceeds a certain limit.

import java.util.LinkedHashMap;
import java.util.Map;

public class Main {
  public static void main(String[] args) {
    final int MAX_ENTRIES = 3;
    // capacity, load factor, accessOrder (true = access order, false = insertion order)
    LinkedHashMap<String, String> lruCache = new LinkedHashMap<String, String>(16, 0.75f, true) {
      @Override
      protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > MAX_ENTRIES; // Remove oldest if size exceeds 3
      }
    };
    lruCache.put("A", "Apple");
    lruCache.put("B", "Banana");
    lruCache.put("C", "Cherry");
    System.out.println("Initial Cache: " + lruCache);
    // Access "A". Because accessOrder is true, "A" moves to the end of the line!
    lruCache.get("A");
    // Add "D". Since the max size is 3, the oldest entry ("B") will be evicted!
    lruCache.put("D", "Date");
    // Output will be: {C=Cherry, A=Apple, D=Date}
    System.out.println("Updated Cache: " + lruCache);
  }
}