LinkedHashMap and TreeMap: Ordered Maps

While HashMap is optimized for speed, LinkedHashMap and TreeMap are optimized for Order.

1. LinkedHashMap: Caching and Consistency

LinkedHashMap extends HashMap but adds a Doubly Linked List that threads through all of its entries.

1.1 Maintenance of Order

It supports two types of ordering:

1. Insertion Order (Default): Elements are retrieved in the order they were put in.
2. Access Order: Elements are moved to the end of the list whenever they are get() or put(). This is the foundation for implementing an LRU (Least Recently Used) Cache.

1.2 Implementing an LRU Cache

By overriding removeEldestEntry, you can create a zero-code cache:

public class MyCache<K, V> extends LinkedHashMap<K, V> {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 100; // Evict when size exceeds 100
    }
}

2. TreeMap: The Red-Black Tree

TreeMap implements the SortedMap interface. It stores keys in their natural order or as determined by a custom Comparator.

2.1 The Red-Black Logic

• Guaranteed Performance: $O(\log n)$ for get, put, and remove.
• Structure: A self-balancing binary search tree.
• No Nulls: Unlike HashMap, TreeMap prohibits null keys because it must compare entries to position them.

2.2 Key Features

• firstKey() / lastKey(): Constant time access to the range boundaries.
• subMap(from, to): Extremely efficient range queries.

Comparison Summary