11.4 Map: HashMap, LinkedHashMap, and TreeMap

Overview

Map is a collection that stores data as key-value pairs. Think of it like a real dictionary: you look up a word (key) and find its definition (value). Maps provide instant value lookup by key, making them ideal for caching, counting frequencies, grouping data, and configuration storage.

Key characteristics:

• Keys must be unique— adding the same key replaces the existing value
• Values may be duplicated
• Map does not extend Collection, but is part of the collection framework

---

1. HashMap

HashMap is the most commonly used Map. It uses hashing to provide O(1) average performance for get and put. The iteration order is not guaranteed.

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> scores = new HashMap<>();

// Adding entries
scores.put("Alice", 95);
scores.put("Bob",   87);
scores.put("Carol", 92);

// Updating (same key → replaces value)
scores.put("Alice", 98);  // Alice's score updated

System.out.println(scores);            // {Alice=98, Bob=87, Carol=92} (order varies)
System.out.println(scores.size());     // 3

// Retrieving
System.out.println(scores.get("Bob"));         // 87
System.out.println(scores.get("Unknown"));     // null (key not found)

// Checking existence
System.out.println(scores.containsKey("Carol")); // true
System.out.println(scores.containsValue(87));    // true

// Removing
scores.remove("Bob");
System.out.println(scores); // {Alice=98, Carol=92}

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

// Keys and values separately
for (String key : scores.keySet()) System.out.println(key);
for (int value : scores.values()) System.out.println(value);

// forEach lambda (Java 8+)
scores.forEach((name, score) ->
        System.out.printf("%-10s: %d%n", name, score));

---

2. LinkedHashMap

LinkedHashMap preserves insertion order(or access order if configured). Same O(1) performance as HashMap, but iteration follows the order entries were added.

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

Map<String, Integer> ordered = new LinkedHashMap<>();
ordered.put("banana", 3);
ordered.put("apple",  5);
ordered.put("cherry", 2);

System.out.println(ordered); // {banana=3, apple=5, cherry=2} — insertion order!

// Access-order LinkedHashMap (LRU cache base)
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 3; // keep only 3 entries (LRU cache)
    }
};

lru.put("a", 1);
lru.put("b", 2);
lru.put("c", 3);
lru.get("a");    // access "a" — moves it to end
lru.put("d", 4); // adds "d", "b" is evicted (least recently used)
System.out.println(lru); // {c=3, a=1, d=4}

---

3. TreeMap

TreeMap stores entries sorted by key(natural order or custom Comparator). Implemented as a Red-Black tree — all operations are O(log n). Implements NavigableMap for range queries.

import java.util.TreeMap;
import java.util.NavigableMap;

TreeMap<String, Integer> tree = new TreeMap<>();
tree.put("cherry", 5);
tree.put("apple",  3);
tree.put("banana", 7);
tree.put("date",   2);

System.out.println(tree); // {apple=3, banana=7, cherry=5, date=2} — always sorted by key!

// NavigableMap methods
System.out.println(tree.firstKey());  // apple
System.out.println(tree.lastKey());   // date

System.out.println(tree.floorKey("blueberry"));   // banana (largest key <= "blueberry")
System.out.println(tree.ceilingKey("blueberry")); // cherry (smallest key >= "blueberry")
System.out.println(tree.lowerKey("cherry"));      // banana (strictly < "cherry")
System.out.println(tree.higherKey("cherry"));     // date   (strictly > "cherry")

// Range view
System.out.println(tree.subMap("apple", true, "cherry", true)); // {apple=3, banana=7, cherry=5}
System.out.println(tree.headMap("cherry"));  // {apple=3, banana=7} (keys < "cherry")
System.out.println(tree.tailMap("banana"));  // {banana=7, cherry=5, date=2} (keys >= "banana")

---

4. Useful Map Methods (Java 8+)

Modern Java added many powerful methods to Map:

import java.util.HashMap;
import java.util.Map;
import java.util.List;
import java.util.ArrayList;

Map<String, Integer> stock = new HashMap<>();
stock.put("apple",  10);
stock.put("banana", 5);

// getOrDefault: returns default if key not found (avoids null check)
int appleCount  = stock.getOrDefault("apple",  0); // 10
int grapeCount  = stock.getOrDefault("grape",  0); // 0 (not null!)
System.out.println("Apple: " + appleCount + ", Grape: " + grapeCount);

// putIfAbsent: only adds if key does not exist
stock.putIfAbsent("apple",  999); // ignored — apple already exists
stock.putIfAbsent("cherry", 8);   // added — cherry is new
System.out.println(stock.get("apple"));  // 10 (unchanged)
System.out.println(stock.get("cherry")); // 8

// computeIfAbsent: compute and store value if key is absent
Map<String, List<String>> groups = new HashMap<>();
groups.computeIfAbsent("fruits", k -> new ArrayList<>()).add("apple");
groups.computeIfAbsent("fruits", k -> new ArrayList<>()).add("banana"); // key exists, no recompute
groups.computeIfAbsent("vegs",   k -> new ArrayList<>()).add("carrot");
System.out.println(groups); // {fruits=[apple, banana], vegs=[carrot]}

// computeIfPresent: update only if key exists
stock.computeIfPresent("apple", (key, val) -> val + 5); // apple: 10 + 5 = 15
stock.computeIfPresent("grape", (key, val) -> val + 5); // no-op (grape absent)
System.out.println(stock.get("apple")); // 15

// compute: always compute (present or absent)
stock.compute("apple", (key, val) -> val == null ? 1 : val + 1);

// merge: merge a new value with existing one
Map<String, Integer> wordCount = new HashMap<>();
String[] words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
for (String word : words) {
    wordCount.merge(word, 1, Integer::sum); // if absent: put 1, else sum
}
System.out.println(wordCount); // {apple=3, banana=2, cherry=1}

// replaceAll: transform all values
stock.replaceAll((key, val) -> val * 2); // double all stock quantities

---

5. Choosing the Right Map

Feature	HashMap	LinkedHashMap	TreeMap
Order	None	Insertion (or access) order	Sorted by key
Performance (get/put)	O(1) average	O(1) average	O(log n)
Null keys	Yes (one null)	Yes (one null)	No (throws NPE)
Range queries	No	No	Yes
Best for	Fast lookup	Ordered maps, LRU cache	Sorted iteration, range queries

---

6. Practical Example: Word Frequency Counter

import java.util.*;
import java.util.stream.*;

public class WordFrequencyCounter {

    public static Map<String, Long> countWords(String text) {
        return Arrays.stream(text.toLowerCase()
                .replaceAll("[^a-z\\s]", "") // remove punctuation
                .split("\\s+"))
                .filter(w -> !w.isEmpty())
                .collect(Collectors.groupingBy(
                        w -> w,
                        LinkedHashMap::new, // preserve insertion order
                        Collectors.counting()
                ));
    }

    public static List<Map.Entry<String, Long>> topN(Map<String, Long> freq, int n) {
        return freq.entrySet().stream()
                .sorted(Map.Entry.<String, Long>comparingByValue().reversed())
                .limit(n)
                .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        String text = "Java is great. Java is powerful. Spring is built on Java. " +
                      "Java is used for web, mobile, and enterprise applications.";

        Map<String, Long> freq = countWords(text);

        System.out.println("Top 5 words:");
        topN(freq, 5).forEach(e ->
                System.out.printf("  %-15s : %d%n", e.getKey(), e.getValue()));

        // Using merge for manual counting (alternative approach)
        Map<String, Integer> manualCount = new HashMap<>();
        for (String word : text.toLowerCase().split("\\W+")) {
            if (!word.isEmpty()) {
                manualCount.merge(word, 1, Integer::sum);
            }
        }
        System.out.println("\n'java' appears: " + manualCount.get("java") + " times");
    }
}

---

7. Practical Example: Student Grade Grouping

import java.util.*;
import java.util.stream.*;

public class GradeGrouper {

    record Student(String name, int score) {}

    public static String getGrade(int score) {
        if (score >= 90) return "A";
        if (score >= 80) return "B";
        if (score >= 70) return "C";
        if (score >= 60) return "D";
        return "F";
    }

    public static void main(String[] args) {
        List<Student> students = List.of(
            new Student("Alice",   95),
            new Student("Bob",     82),
            new Student("Charlie", 76),
            new Student("Diana",   91),
            new Student("Eve",     68),
            new Student("Frank",   85),
            new Student("Grace",   93)
        );

        // Group by grade using streams
        Map<String, List<String>> byGrade = students.stream()
                .collect(Collectors.groupingBy(
                        s -> getGrade(s.score()),
                        TreeMap::new,  // sorted by grade (A, B, C...)
                        Collectors.mapping(Student::name, Collectors.toList())
                ));

        byGrade.forEach((grade, names) ->
                System.out.println("Grade " + grade + ": " + names));

        // Score statistics per grade
        Map<String, IntSummaryStatistics> stats = students.stream()
                .collect(Collectors.groupingBy(
                        s -> getGrade(s.score()),
                        Collectors.summarizingInt(Student::score)
                ));

        System.out.println("\nGrade Statistics:");
        stats.forEach((grade, s) ->
                System.out.printf("  Grade %-2s | Count: %d | Avg: %.1f | Range: %d-%d%n",
                        grade, s.getCount(), s.getAverage(), s.getMin(), s.getMax()));
    }
}

---

Pro Tips

getOrDefault vs null check:

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);

// Old way (verbose)
Integer val = map.get("b");
int result = (val != null) ? val : 0;

// Modern way (clean)
int result = map.getOrDefault("b", 0);

computeIfAbsent for grouping:

// Classic grouping pattern using computeIfAbsent
Map<String, List<String>> groups = new HashMap<>();
String key = "fruits";
groups.computeIfAbsent(key, k -> new ArrayList<>()).add("apple");
// Equivalent to:
// groups.putIfAbsent(key, new ArrayList<>());
// groups.get(key).add("apple");
// But computeIfAbsent is one line and doesn't create unnecessary lists

equals/hashCode for custom key objects:

When using a custom class as a Map key, always override both equals() and hashCode()(or use record). Without this, two logically equal keys will be treated as different, causing phantom entries.