Maps: HashMap & TreeMap

Key-value storage, iteration, getOrDefault, merge, computeIfAbsent, TreeMap and LinkedHashMap.

A map stores key → value pairs, and finds a value by its key in an instant. Phone books, product catalogues keyed by SKU, word counts, caches, configuration settings and JSON objects are all maps. Map is arguably the most useful data structure in everyday Java.

`HashMap` basics#

MapBasics.java

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

public class MapBasics {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("banana", 20);
        System.out.println(stock.put("apple", 45));   // replaces; returns the old value

        System.out.println(stock.get("apple"));
        System.out.println(stock.get("mango"));          // missing key: null
        System.out.println(stock.getOrDefault("mango", 0));
        System.out.println(stock.containsKey("banana") + " " + stock.containsValue(20));
        System.out.println(stock.size());

        stock.remove("banana");
        System.out.println(stock);
    }
}

Output

50
45
null
0
true true
2
{apple=45}

Key rules:

Keys are unique; values can repeat. Putting an existing key overwrites its value.
get returns null for a missing key. Prefer getOrDefault or containsKey when absence is possible.
HashMap operations are O(1) on average, and it has no guaranteed order.
One null key and any number of null values are allowed in a HashMap (but avoid them; they make get ambiguous).

Iterating over a map#

Iterate.java

import java.util.Map;
import java.util.TreeMap;

public class Iterate {
    public static void main(String[] args) {
        Map<String, Double> prices = new TreeMap<>(Map.of("tea", 30.0, "coffee", 60.0, "juice", 80.0));

        for (Map.Entry<String, Double> e : prices.entrySet()) {   // keys AND values
            System.out.println(e.getKey() + " costs " + e.getValue());
        }

        for (String item : prices.keySet()) System.out.print(item + " ");
        System.out.println();

        double total = 0;
        for (double p : prices.values()) total += p;
        System.out.println("Total: " + total);

        prices.forEach((k, v) -> System.out.print(k + "=" + v + "; "));
        System.out.println();
    }
}

Output

coffee costs 60.0
juice costs 80.0
tea costs 30.0
coffee juice tea
Total: 170.0
coffee=60.0; juice=80.0; tea=30.0;

Because this is a TreeMap, every view (entrySet, keySet, values) comes out sorted by key. You will compare the three main map types shortly.

Tip: iterate over entrySet() when you need both key and value. Looping over keySet() and calling get(key) each time does a second lookup per key.

Counting and grouping: `merge` and `computeIfAbsent`#

Two methods make the most common map tasks one-liners:

WordCount.java

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

public class WordCount {
    public static void main(String[] args) {
        String text = "the cat and the hat and the bat";

        Map<String, Integer> counts = new TreeMap<>();
        for (String w : text.split(" ")) {
            counts.merge(w, 1, Integer::sum);     // new key -> 1, else old + 1
        }
        System.out.println(counts);

        Map<Character, List<String>> byFirstLetter = new TreeMap<>();
        for (String w : List.of("apple", "avocado", "banana", "blueberry", "cherry")) {
            byFirstLetter.computeIfAbsent(w.charAt(0), k -> new ArrayList<>()).add(w);
        }
        System.out.println(byFirstLetter);
    }
}

Output

{and=2, bat=1, cat=1, hat=1, the=3}
{a=[apple, avocado], b=[banana, blueberry], c=[cherry]}

merge(key, value, fn): if the key is absent, store value; otherwise store fn(oldValue, value).
computeIfAbsent(key, k -> create): return the existing value, or create, store and return a new one. It is perfect for "map of lists".

Other handy methods:

Method	Does
`putIfAbsent(k, v)`	put only if the key is missing
`computeIfPresent(k, fn)`	update an existing value (removes it if `fn` returns null)
`compute(k, fn)`	compute a new value from key and old value (old may be null)
`replaceAll(fn)`	transform every value
`entrySet().removeIf(...)`	delete entries matching a condition

`HashMap` vs `LinkedHashMap` vs `TreeMap`#

ThreeMaps.java

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public class ThreeMaps {
    public static void main(String[] args) {
        String[] keys = {"zeta", "alpha", "mid"};
        Map<String, Integer> linked = new LinkedHashMap<>();
        Map<String, Integer> tree = new TreeMap<>();
        Map<String, Integer> hash = new HashMap<>();
        for (int i = 0; i < keys.length; i++) {
            linked.put(keys[i], i);
            tree.put(keys[i], i);
            hash.put(keys[i], i);
        }
        System.out.println("Linked: " + linked);   // insertion order
        System.out.println("Tree:   " + tree);     // sorted by key
        System.out.println("Hash has " + hash.size() + " entries in no guaranteed order");
    }
}

Output

Linked: {zeta=0, alpha=1, mid=2}
Tree:   {alpha=1, mid=2, zeta=0}
Hash has 3 entries in no guaranteed order

	`HashMap`	`LinkedHashMap`	`TreeMap`
Order	none	insertion (or access) order	sorted by key
get/put	O(1)	O(1)	O(log n)
Null keys	one	one	no
Key requirements	`equals` + `hashCode`	`equals` + `hashCode`	`Comparable` or `Comparator`

Use HashMap by default, LinkedHashMap when order of insertion matters (e.g. JSON output, LRU caches), and TreeMap when you need sorted keys or range queries. For enum keys, use EnumMap.

`TreeMap` navigation#

TaxSlabs.java

import java.util.TreeMap;

public class TaxSlabs {
    public static void main(String[] args) {
        // income threshold -> tax rate (simplified example slabs)
        TreeMap<Integer, Double> slabs = new TreeMap<>();
        slabs.put(0, 0.0);
        slabs.put(400_000, 0.05);
        slabs.put(800_000, 0.10);
        slabs.put(1_200_000, 0.15);

        for (int income : new int[]{250_000, 950_000, 2_000_000}) {
            double rate = slabs.floorEntry(income).getValue();   // highest threshold <= income
            System.out.println(income + " -> " + rate * 100 + "%");
        }
        System.out.println(slabs.firstKey() + " " + slabs.lastKey());
        System.out.println(slabs.headMap(800_000));        // keys < 800000
        System.out.println(slabs.ceilingKey(500_000));     // smallest key >= 500000
    }
}

Output

250000 -> 0.0%
950000 -> 10.0%
2000000 -> 15.0%
0 1200000
{0=0.0, 400000=0.05}
800000

floorEntry turns "find the band this value falls into" into a single O(log n) call.

Immutable maps#

Java

Map<String, Integer> codes = Map.of("IN", 91, "US", 1, "UK", 44);   // up to 10 pairs
Map<String, Integer> many = Map.ofEntries(Map.entry("FR", 33), Map.entry("DE", 49));
Map<String, Integer> copy = Map.copyOf(someMap);

These are unmodifiable, reject null keys and values, and have unspecified iteration order.

How `HashMap` works (in brief)#

The key's hashCode() picks a bucket in an internal array.
Inside the bucket, equals() finds the exact key.
When the map gets about 75% full (the load factor), the array doubles and entries are redistributed.
Buckets with many colliding keys turn into small balanced trees (Java 8+), so worst-case lookups stay O(log n).

Therefore keys must have consistent equals and hashCode, and must not change while in the map. Strings, wrappers, enums and records make excellent keys.

RecordKeys.java

import java.time.LocalDate;
import java.util.HashMap;
import java.util.Map;

public class RecordKeys {
    record Booking(String room, LocalDate date) { }

    public static void main(String[] args) {
        Map<Booking, String> bookings = new HashMap<>();
        bookings.put(new Booking("A101", LocalDate.of(2026, 10, 2)), "Asha");

        Booking query = new Booking("A101", LocalDate.of(2026, 10, 2));   // a different object
        System.out.println(bookings.get(query));                          // found: records compare by value
        System.out.println(bookings.containsKey(new Booking("A101", LocalDate.of(2026, 10, 3))));
    }
}

Output

Asha
false

A practical example: an inventory#

Inventory.java

import java.util.Map;
import java.util.TreeMap;

public class Inventory {
    private final Map<String, Integer> stock = new TreeMap<>();

    void receive(String sku, int qty) {
        stock.merge(sku, qty, Integer::sum);
    }

    boolean sell(String sku, int qty) {
        int available = stock.getOrDefault(sku, 0);
        if (available < qty) return false;
        stock.computeIfPresent(sku, (k, v) -> v - qty == 0 ? null : v - qty);   // null removes
        return true;
    }

    public static void main(String[] args) {
        Inventory inv = new Inventory();
        inv.receive("PEN", 10);
        inv.receive("INK", 2);
        inv.receive("PEN", 5);
        System.out.println(inv.stock);
        System.out.println(inv.sell("INK", 2) + " " + inv.sell("PEN", 100));
        System.out.println(inv.stock);
    }
}

Output

{INK=2, PEN=15}
true false
{PEN=15}

Common mistakes#

map.get(k) + 1 on a missing key: a NullPointerException from unboxing null. Use merge or getOrDefault.
Relying on HashMap order.
Using mutable objects as keys and changing them after insertion.
Modifying a map while iterating over it (other than through iterator.remove() or entrySet().removeIf), which throws ConcurrentModificationException.
Sharing a plain HashMap between threads. Use ConcurrentHashMap (concurrency lessons).

What's next#

Sorted sets and maps need to know how to order elements. Next we look closely at Comparable vs Comparator, the two ways to define order in Java.

HashMap basics#

Iterating over a map#

Counting and grouping: merge and computeIfAbsent#

HashMap vs LinkedHashMap vs TreeMap#

TreeMap navigation#

Immutable maps#

How HashMap works (in brief)#

A practical example: an inventory#

Common mistakes#

What's next#

Quick quiz

`HashMap` basics#

Counting and grouping: `merge` and `computeIfAbsent`#

`HashMap` vs `LinkedHashMap` vs `TreeMap`#

`TreeMap` navigation#

How `HashMap` works (in brief)#