TreeMap & LinkedHashMap

TreeMap

TreeMap is a SortedMap implementation backed by a red-black tree (a self-balancing binary search tree). It keeps keys in sorted order according to their natural ordering or a custom Comparator.

Key characteristics:

Keys are sorted (ascending order by default)
O(log n) for get, put, remove
No null keys (throws NullPointerException)
Based on red-black tree: guaranteed O(log n)

import java.util.*;

public class TreeMapDemo {
    public static void main(String[] args) {
        // Creating TreeMap - keys sorted by natural order
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("Banana", 3);
        map.put("Apple", 5);
        map.put("Cherry", 2);
        map.put("Date", 8);
        map.put("Elderberry", 1);

        System.out.println("Sorted map: " + map);
        // {Apple=5, Banana=3, Cherry=2, Date=8, Elderberry=1}

        // Navigation methods
        System.out.println("First key: " + map.firstKey()); // Apple
        System.out.println("Last key: " + map.lastKey()); // Elderberry
        System.out.println("First entry: " + map.firstEntry()); // Apple=5
        System.out.println("Last entry: " + map.lastEntry()); // Elderberry=1

        // floorKey - greatest key <= given key
        System.out.println("floorKey(D): " + map.floorKey("D")); // Date
        System.out.println("floorKey(Ac): " + map.floorKey("Ac")); // Apple

        // ceilingKey - smallest key >= given key
        System.out.println("ceilingKey(D): " + map.ceilingKey("D")); // Date
        System.out.println("ceilingKey(Db): " + map.ceilingKey("Db")); // Elderberry

        // lowerKey - greatest key < given key (strictly less)
        System.out.println("lowerKey(Cherry): " + map.lowerKey("Cherry")); // Banana

        // higherKey - smallest key > given key (strictly greater)
        System.out.println("higherKey(Cherry): " + map.higherKey("Cherry")); // Date

        // SubMap, headMap, tailMap
        System.out.println("headMap(Cherry): " + map.headMap("Cherry")); // {Apple, Banana}
        System.out.println("tailMap(Cherry): " + map.tailMap("Cherry")); // {Cherry, Date, Elderberry}
        System.out.println("subMap(Banana, Date): " + map.subMap("Banana", "Date")); // {Banana, Cherry}

        // descendingMap
        System.out.println("Descending: " + map.descendingMap());
        // {Elderberry=1, Date=8, Cherry=2, Banana=3, Apple=5}

        // pollFirstEntry / pollLastEntry - remove and return
        Map.Entry<String, Integer> first = map.pollFirstEntry();
        System.out.println("Removed first: " + first); // Apple=5
    }
}

When to use TreeMap:

You need keys in sorted order
You need navigation methods (floor, ceiling, higher, lower)
You need range views (subMap, headMap, tailMap)
You need the smallest or largest key efficiently

LinkedHashMap

LinkedHashMap extends HashMap by maintaining a doubly linked list across all entries. This preserves either insertion order or access order (LRU order).

Two modes:

Insertion order (default): entries iteration follows insertion order
Access order: entries iteration follows last access order (useful for LRU caches)

import java.util.*;

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        // Insertion order (default)
        LinkedHashMap<String, Integer> insertion = new LinkedHashMap<>();
        insertion.put("Banana", 3);
        insertion.put("Apple", 5);
        insertion.put("Cherry", 2);
        insertion.put("Date", 8);

        System.out.println("Insertion order: " + insertion);
        // {Banana=3, Apple=5, Cherry=2, Date=8} - same as insertion order

        // Access order - for LRU cache
        LinkedHashMap<String, Integer> access = new LinkedHashMap<>(16, 0.75f, true);
        access.put("A", 1);
        access.put("B", 2);
        access.put("C", 3);

        System.out.println("Before access: " + access); // {A=1, B=2, C=3}
        access.get("A"); // access A
        System.out.println("After accessing A: " + access); // {B=2, C=3, A=1}

        // LRU Cache implementation
        LruCache<String, String> cache = new LruCache<>(3);
        cache.put("key1", "value1");
        cache.put("key2", "value2");
        cache.put("key3", "value3");
        cache.get("key1"); // access key1
        cache.put("key4", "value4"); // evicts key2 (least recently used)
        System.out.println("LRU Cache: " + cache);

        // Override removeEldestEntry for automatic eviction
        LinkedHashMap<String, Integer> bounded = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
                return size() > 3;
            }
        };
        bounded.put("a", 1);
        bounded.put("b", 2);
        bounded.put("c", 3);
        bounded.put("d", 4); // evicts "a"
        System.out.println("Bounded map: " + bounded); // {b=2, c=3, d=4}
    }

    // Simple LRU Cache using LinkedHashMap
    static class LruCache<K, V> extends LinkedHashMap<K, V> {
        private final int maxSize;

        public LruCache(int maxSize) {
            super(16, 0.75f, true); // access order
            this.maxSize = maxSize;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    }
}

When to use LinkedHashMap:

You need insertion order preserved
You need an LRU cache (access order + removeEldestEntry)
You need predictable iteration order without sorting

Methods

TreeMap Navigation Methods

TreeMap's NavigableMap interface provides powerful navigation methods.

import java.util.*;

public class TreeMapMethodsDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "Ten");
        map.put(20, "Twenty");
        map.put(30, "Thirty");
        map.put(40, "Forty");
        map.put(50, "Fifty");

        // Exact key search
        System.out.println("get(30): " + map.get(30)); // Thirty
        System.out.println("containsKey(20): " + map.containsValue("Twenty")); // true

        // Nearest key navigation
        System.out.println("\n--- Navigation ---");
        System.out.println("floorEntry(25): " + map.floorEntry(25)); // 20=Twenty
        System.out.println("ceilingEntry(25): " + map.ceilingEntry(25)); // 30=Thirty
        System.out.println("lowerEntry(30): " + map.lowerEntry(30)); // 20=Twenty
        System.out.println("higherEntry(30): " + map.higherEntry(30)); // 40=Forty

        // Floor vs lower: floor <=, lower <
        System.out.println("\nfloorKey(30): " + map.floorKey(30)); // 30 (includes equal)
        System.out.println("lowerKey(30): " + map.lowerKey(30)); // 20 (excludes equal)

        // Ceiling vs higher: ceiling >=, higher >
        System.out.println("ceilingKey(30): " + map.ceilingKey(30)); // 30 (includes equal)
        System.out.println("higherKey(30): " + map.higherKey(30)); // 40 (excludes equal)

        // First and last
        System.out.println("\nFirst: " + map.firstKey() + " = " + map.firstEntry().getValue());
        System.out.println("Last: " + map.lastKey() + " = " + map.lastEntry().getValue());

        // Range views
        System.out.println("\n--- Range Views ---");
        System.out.println("headMap(30): " + map.headMap(30)); // {10, 20}
        System.out.println("tailMap(30): " + map.tailMap(30)); // {30, 40, 50}
        System.out.println("subMap(20, 40): " + map.subMap(20, 40)); // {20, 30}
        System.out.println("subMap(20, true, 40, false): " + map.subMap(20, true, 40, false));

        // Descending
        System.out.println("\nDescending: " + map.descendingMap());
        System.out.println("Descending key set: " + map.descendingKeySet());

        // Poll entries
        System.out.println("pollFirstEntry: " + map.pollFirstEntry()); // 10=Ten
        System.out.println("pollLastEntry: " + map.pollLastEntry()); // 50=Fifty
        System.out.println("After polls: " + map);
    }
}

Comparison of navigation methods:

Method	Returns
floorKey(k)	greatest key <= k, or null
ceilingKey(k)	smallest key >= k, or null
lowerKey(k)	greatest key < k, or null
higherKey(k)	smallest key > k, or null

When to Use

When to Use Each Map Implementation

Map	Ordering	Performance	Null Keys	Use Case
HashMap	None	O(1) avg	One null key	General purpose, fast lookup
LinkedHashMap	Insertion/Access order	O(1) avg	One null key	LRU cache, predictable iteration
TreeMap	Sorted by key	O(log n)	No null keys	Sorted iteration, navigation, ranges

import java.util.*;

public class MapComparisonDemo {
    public static void main(String[] args) {
        // Use HashMap when: fast lookup, no ordering needed
        Map<String, Integer> cache = new HashMap<>();
        cache.put("user:1", 100);
        cache.put("user:2", 200);
        int user1 = cache.getOrDefault("user:1", 0); // O(1)

        // Use LinkedHashMap when: insertion order matters
        LinkedHashMap<String, Integer> config = new LinkedHashMap<>();
        config.put("database.url", 1);
        config.put("database.user", 2);
        config.put("database.pass", 3);
        for (Map.Entry<String, Integer> entry : config.entrySet()) {
            System.out.println("Config: " + entry.getKey() + " = " + entry.getValue());
        }

        // Use TreeMap when: sorted keys needed
        TreeMap<String, Integer> sortedScores = new TreeMap<>();
        sortedScores.put("Alice", 95);
        sortedScores.put("Bob", 87);
        sortedScores.put("Charlie", 92);
        System.out.println("Sorted scores: " + sortedScores);
        System.out.println("Top score: " + sortedScores.lastEntry());
        System.out.println("Bottom score: " + sortedScores.firstEntry());

        // Use LinkedHashMap with access order for LRU
        LinkedHashMap<String, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return size() > 3;
            }
        };
        lru.put("a", "1");
        lru.put("b", "2");
        lru.put("c", "3");
        lru.get("a"); // access "a"
        lru.put("d", "4"); // evicts "b"
        System.out.println("LRU: " + lru);

        // Use TreeMap for range queries
        TreeMap<Integer, String> events = new TreeMap<>();
        events.put(2020, "Pandemic");
        events.put(2021, "Recovery");
        events.put(2022, "Growth");
        events.put(2023, "Innovation");
        events.put(2024, "AI Boom");
        System.out.println("Events 2021-2023: " + events.subMap(2021, 2024));
        System.out.println("Most recent: " + events.lastEntry());
    }
}

Decision framework:

Need O(1) lookup with no ordering? → HashMap
Need predictable iteration order? → LinkedHashMap
Need sorted keys or navigation? → TreeMap
Need LRU cache? → LinkedHashMap (access order + removeEldestEntry)

Practice Problems

0/2solved

intermediateFind Kth Smallest Element

Given a TreeSet of integers and an integer k, return the kth smallest element. Use TreeMap's navigation methods.

Solution

import java.util.*;

public class KthSmallest {
    public static int kthSmallest(TreeSet<Integer> set, int k) {
        if (k <= 0 || k > set.size()) throw new IllegalArgumentException("Invalid k");
        Iterator<Integer> it = set.iterator();
        for (int i = 1; i < k; i++) {
            it.next();
        }
        return it.next();
    }
}

intermediateLRU Cache

Implement an LRU (Least Recently Used) cache using LinkedHashMap with access order. It should have get(key) and put(key, value) methods with O(1) time complexity.

Solution

import java.util.*;

public class LRUCache {
    private int capacity;
    private LinkedHashMap<Integer, Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > LRUCache.this.capacity;
            }
        };
    }

    public int get(int key) {
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }
}

Flashcards

Question

What is TreeMap and what data structure does it use?

Click to reveal answer

Answer

TreeMap is a SortedMap backed by a red-black tree. It keeps keys sorted and provides O(log n) for get, put, and remove. It also supports navigation methods like floorKey, ceilingKey, higherKey, lowerKey.

Question

What is LinkedHashMap and what are its two ordering modes?

Click to reveal answer

Answer

LinkedHashMap extends HashMap with a doubly linked list. It supports insertion order (default) and access order (accessOrder=true). Access order mode is used for LRU caches.

Question

When would you use TreeMap over HashMap?

Click to reveal answer

Answer

When you need keys in sorted order, navigation methods (floor, ceiling), range views (subMap, headMap, tailMap), or the smallest/largest key. TreeMap costs O(log n) vs HashMap O(1).

Question

What is Java TreeMap and LinkedHashMap?

Click to reveal answer

Answer

Java TreeMap and LinkedHashMap is a key concept in Java programming.

Question

When to use Java TreeMap and LinkedHashMap?

Click to reveal answer

Answer

Use Java TreeMap and LinkedHashMap when building production systems that require reliability, scalability, and maintainability.

Revision Notes

Key Takeaways

1.TreeMap keeps keys sorted using a red-black tree (O(log n))
2.LinkedHashMap preserves insertion or access order (O(1))
3.Use LinkedHashMap with access order for LRU caches
4.TreeMap's navigation methods find nearest keys efficiently

Interview Tips

•Explain TreeMap's O(log n) guarantee vs HashMap's O(1) average
•Demonstrate how to implement an LRU cache with LinkedHashMap
•Know the difference between floorKey/ceilingKey and lowerKey/higherKey
•Discuss when sorted order justifies the O(log n) cost

Cheat Sheet