What are the features of LinkedHashMap?

LinkedHashMap combines the characteristics of HashMap and LinkedList.

Features:

• Order of storage: Unlike HashMap, LinkedHashMap maintains the insertion order of elements. There is also an option to maintain access order — the order in which elements are accessed.
• Performance: The performance of basic operations (get, put, remove) is close to HashMap (average O(1)), as it uses a hash table. Additional overhead is associated with maintaining a doubly linked list.
• Internal structure: Consists of a hash table (similar to HashMap) and a doubly linked list that connects all elements in the order of their addition or last access. Each node in the hash table also stores references to the previous and next elements in the list.
• Usage: Often used when it is necessary to maintain the order of element addition, for example, to implement a cache with Least Recently Used (LRU) eviction.

Example of using for an LRU cache:

// Example implementation of an LRU cache using LinkedHashMap
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int cacheSize;

    public LRUCache(int cacheSize) {
        // Initialize LinkedHashMap with accessOrder = true
        super(cacheSize, 0.75f, true); 
        this.cacheSize = cacheSize;
    }

    // Override method to remove the oldest (least used) element when size exceeds limit
    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
}