Introduction to LinkedHashMap

LinkedHashMap is a class in Java’s Collections Framework that combines the power of a HashMap with a linked list to maintain the insertion order or access order of entries.

It belongs to the package:

java.util

and was introduced in Java 1.4.

A LinkedHashMap is very useful when you want to store key-value pairs like a HashMap, but also need the entries to be returned in the same order they were inserted or recently accessed.

---

Class Hierarchy

LinkedHashMap is part of the following hierarchy:

java.lang.Object
   ↳ java.util.AbstractMap<K, V>
        ↳ java.util.HashMap<K, V>
             ↳ java.util.LinkedHashMap<K, V>

This means that LinkedHashMap is a subclass of HashMap and therefore inherits all its properties — hashing, constant-time lookup, and key uniqueness — but adds a linked list to maintain predictable iteration order.

---

Definition and Declaration

public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V>

Here:

• K – type of keys maintained by this map.
• V – type of mapped values.

---

Key Characteristics of LinkedHashMap

1. Order of Elements
   • Unlike HashMap, which does not maintain any order, a LinkedHashMap maintains a doubly-linked list that preserves:
     • Insertion order (default), or
     • Access order (if configured).
2. Unique Keys
   • Just like HashMap, each key in a LinkedHashMap must be unique.
3. Null Values and Keys
   • LinkedHashMap allows one null key and multiple null values.
4. Performance
   • The time complexity for put(), get(), remove(), and containsKey() is O(1), just like HashMap.
5. Predictable Iteration
   • Since it maintains order, iteration over entries is predictable and stable.
6. Load Factor and Capacity
   • Like HashMap, it uses an internal hash table structure and has configurable capacity and load factor.

---

Internal Working of LinkedHashMap

LinkedHashMap internally uses:

• A hash table (like HashMap) to store entries.
• A doubly-linked list that connects all entries in the order they were inserted or accessed.

Each entry in a LinkedHashMap is represented as an object of an internal static class:

static class Entry<K, V> extends HashMap.Node<K, V> {
    Entry<K, V> before;
    Entry<K, V> after;
}

Here:

• before and after are references that form the linked list.
• These pointers preserve the iteration order.

When you add a new key-value pair using put(), the following happens:

1. The key’s hash code is computed.
2. The entry is inserted into the appropriate bucket (hash table).
3. It is linked to the previous entry in the insertion order list.

---

Constructors of LinkedHashMap

1. Default Constructor LinkedHashMap<K, V> map = new LinkedHashMap<>(); Creates an empty map with default capacity (16) and load factor (0.75).
2. With Initial Capacity LinkedHashMap<K, V> map = new LinkedHashMap<>(32); Creates a map with specified capacity.
3. With Capacity and Load Factor LinkedHashMap<K, V> map = new LinkedHashMap<>(32, 0.8f);
4. With Access Order LinkedHashMap<K, V> map = new LinkedHashMap<>(16, 0.75f, true); The third argument (true) enables access-order iteration instead of insertion-order.
5. From Another Map LinkedHashMap<K, V> map = new LinkedHashMap<>(existingMap);

---

Example 1: Basic Usage with Insertion Order

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

public class LinkedHashMapExample {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();

        map.put(3, "Banana");
        map.put(1, "Apple");
        map.put(2, "Mango");

        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }
    }
}

Output:

3 => Banana
1 => Apple
2 => Mango

Explanation:
The output preserves the insertion order, even though the keys are not sorted numerically.

---

Example 2: Access Order

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

public class AccessOrderExample {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);

        map.put(1, "A");
        map.put(2, "B");
        map.put(3, "C");

        // Access some elements
        map.get(1);
        map.get(3);

        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }
    }
}

Output:

2 => B
1 => A
3 => C

Explanation:
Here, the map was created with accessOrder = true, so entries are reordered every time they are accessed.
The least recently accessed entry (2) appears first.

This mechanism is often used to build LRU (Least Recently Used) caches.

---

Example 3: Implementing LRU Cache Using LinkedHashMap

LinkedHashMap provides a protected method removeEldestEntry(Map.Entry<K, V> eldest) which can be overridden to automatically remove the oldest entry when a certain size limit is exceeded.

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // access order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // remove oldest when size exceeds capacity
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");

        cache.get(1); // Access key 1 (makes it most recently used)
        cache.put(4, "D"); // Evicts least recently used entry (key 2)

        System.out.println(cache);
    }
}

Output:

{3=C, 1=A, 4=D}

Explanation:
When inserting 4, the least recently used key (2) is automatically removed.

---

Important Methods

Method	Description
put(K key, V value)	Adds a key-value pair to the map.
get(Object key)	Retrieves the value for the given key.
remove(Object key)	Removes the mapping for the given key.
containsKey(Object key)	Checks if a key exists.
containsValue(Object value)	Checks if a value exists.
size()	Returns number of entries.
clear()	Removes all mappings.
keySet()	Returns a Set of all keys.
values()	Returns a Collection of all values.
entrySet()	Returns a Set of key-value pairs.

---

Difference Between HashMap and LinkedHashMap

Feature	HashMap	LinkedHashMap
Order	Unordered	Maintains insertion or access order
Iteration	Random	Predictable and ordered
Performance	Slightly faster (no linked list)	Slightly slower (maintains links)
Use Case	When order doesn’t matter	When predictable iteration is needed
Cache Support	Not suitable	Ideal for implementing LRU cache

---

Example 4: Maintaining Predictable Order for Display

import java.util.LinkedHashMap;

public class OrderExample {
    public static void main(String[] args) {
        LinkedHashMap<String, Double> products = new LinkedHashMap<>();

        products.put("Laptop", 75000.0);
        products.put("Mouse", 1500.0);
        products.put("Keyboard", 2500.0);

        System.out.println("Product list in insertion order:");
        products.forEach((k, v) -> System.out.println(k + " = " + v));
    }
}

Output:

Product list in insertion order:
Laptop = 75000.0
Mouse = 1500.0
Keyboard = 2500.0

---

Performance Considerations

• Time Complexity:
  Most operations — insertion, lookup, and deletion — are O(1) on average.
• Space Complexity:
  Slightly higher than HashMap due to the extra linked list pointers.
• Iteration Performance:
  Since the order is maintained, iteration is slightly slower than in HashMap, but still efficient.

---

When to Use LinkedHashMap

Use LinkedHashMap when you need:

1. Fast lookups like HashMap.
2. Predictable iteration order (insertion or access).
3. Implementation of caching (like LRU cache).
4. Maintaining ordered data without sorting.

---

Summary

Property	LinkedHashMap
Maintains Order	Yes (insertion or access)
Allows Null Keys	Yes (one)
Allows Null Values	Yes (multiple)
Thread Safe	No (use Collections.synchronizedMap() for thread safety)
Time Complexity	O(1) average for basic operations
Internal Structure	Hash table + doubly linked list