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());
    }
  }
}