SyntaxPilot
Courses/Java/Lesson 32

Java · Lesson 32 of 51 · 14 min

Collections 3: HashMap internals, TreeMap

queued

These are the notes for Java episode 32. At the fest help desk we need a student's whole profile from her email. Two parallel lists (emails in one, names in another) drift apart and are slow to search, so we invent the map: every key is tied to its value. Then we open up a HashMap to see buckets, the hash formula, collisions, the load factor, resizing and treeification, meet two traps (changing a key, removing inside a loop), and finish with LinkedHashMap and TreeMap. Every example was run with javac 21.

The problem: two lists drift apart

The obvious way to store "email → name" is two lists in the same order, matched by position.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> emails = new ArrayList<>(
                List.of("asha@mail.in", "ravi@mail.in", "meena@mail.in"));
        List<String> names = new ArrayList<>(
                List.of("Asha Rao", "Ravi Kumar", "Meena Iyer"));
        emails.remove("asha@mail.in");      // Asha cancels...
        // ...but someone forgot names.remove(...)
        int i = emails.indexOf("meena@mail.in");
        System.out.println("Meena's name: " + names.get(i));
    }
}

Output:

Meena's name: Ravi Kumar

No error, no crash, just the wrong person. Removing from one list but not the other shifts every later row. Nothing connects an email to its name except the position.

And it's slow

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

public class Main {
    public static void main(String[] args) {
        List<String> emails = new ArrayList<>();
        Map<String, Integer> index = new HashMap<>();
        for (int i = 0; i < 20_000; i++) {
            emails.add("s" + i + "@mail.in");
            index.put("s" + i + "@mail.in", i);
        }

        long t = System.nanoTime();
        for (int i = 0; i < 20_000; i++) emails.indexOf("s" + i + "@mail.in");
        System.out.println("List indexOf: " + (System.nanoTime() - t) / 1_000_000 + " ms");

        t = System.nanoTime();
        for (int i = 0; i < 20_000; i++) index.get("s" + i + "@mail.in");
        System.out.println("HashMap get:  " + (System.nanoTime() - t) / 1_000_000 + " ms");
    }
}

Output:

List indexOf: 856 ms
HashMap get:  11 ms

(Times vary by machine; the gap does not.) indexOf checks every item from the start: O(n) per lookup, O(n²) for n lookups. The map jumps straight to the right bucket.

The fix: a map (key → value)

At a railway cloak room In Java
Your token number, unique the key (an email)
Your bag the value (the profile)
The token tells staff which rack the key's hashCode() picks a bucket
Same token again → the old bag is swapped put on an existing key replaces the value

A key together with its value is an entry. A collection of entries is a map. Map<K, V> is the interface; HashMap builds it with buckets.

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

public class Main {
    public static void main(String[] args) {
        Map<String, String> fest = new HashMap<>();
        fest.put("asha@mail.in", "Asha Rao");
        fest.put("ravi@mail.in", "Ravi Kumar");
        fest.put("meena@mail.in", "Meena Iyer");
        fest.remove("asha@mail.in");
        System.out.println(fest.get("meena@mail.in"));
        System.out.println(fest.put("ravi@mail.in", "Ravi K."));
        System.out.println(fest.get("kabir@mail.in"));
        System.out.println(fest.size() + " " + fest.containsKey("ravi@mail.in"));
    }
}

Output:

Meena Iyer
Ravi Kumar
null
2 true
Method What it does On a missing key
put(k, v) store or replace; returns the old value returns null
get(k) the value for k returns null
remove(k) removes the entry; returns its value returns null
containsKey(k) is k there? false
getOrDefault(k, d) the value, or d returns d
size() number of entries

Counting with a map: the null trap

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

public class Main {
    public static void main(String[] args) {
        String[] orders = { "chai", "samosa", "chai", "vada pav", "chai", "samosa" };
        Map<String, Integer> count = new HashMap<>();
        for (String item : orders) {
            int n = count.get(item);        // how many so far?
            count.put(item, n + 1);
        }
        System.out.println(count);
    }
}

Output:

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null
    at Main.main(Main.java:9)

The first "chai" isn't in the map yet, so get returns null. Assigning that Integer to an int unboxes it (episode 28): calling intValue() on null throws NullPointerException.

Fix: getOrDefault or merge

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

public class Main {
    public static void main(String[] args) {
        String[] orders = { "chai", "samosa", "chai", "vada pav", "chai", "samosa" };
        Map<String, Integer> count = new HashMap<>();
        for (String item : orders) {
            count.put(item, count.getOrDefault(item, 0) + 1);
        }
        System.out.println(count);
        Map<String, Integer> again = new HashMap<>();
        for (String item : orders) again.merge(item, 1, Integer::sum);
        System.out.println(again.get("chai") + " " + again.getOrDefault("dosa", 0));
    }
}

Output:

{chai=3, samosa=2, vada pav=1}
3 0
  • getOrDefault(item, 0) gives 0 for a new item.
  • merge(item, 1, Integer::sum): if the key is new, store 1; otherwise combine the old value and 1 with Integer::sum. Integer::sum is a method reference (episode 36).

Inside a HashMap

A HashMap is an array of buckets (the array is called the table). A new HashMap starts with 16 buckets.

key ──hashCode()──► h ──spread: h ^ (h >>> 16)──► & (16 - 1) ──► bucket 0..15
  1. hashCode() turns the key into an int (it can be negative).
  2. Spread: h ^ (h >>> 16) mixes the high 16 bits into the low 16 bits, so keys that differ only in high bits don't pile into one bucket.
  3. Index: & (n - 1) keeps the low bits. Because the table size n is always a power of two, this equals h mod n, but faster.

The same formula, written by hand:

public class Main {
    static int bucket(Object key, int tableSize) {
        int h = key.hashCode();
        return (h ^ (h >>> 16)) & (tableSize - 1);   // what HashMap does
    }
    public static void main(String[] args) {
        String[] keys = { "asha@mail.in", "ravi@mail.in", "meena@mail.in",
                          "kabir@mail.in", "Aa", "BB" };
        for (String k : keys) {
            System.out.println(k + " -> bucket " + bucket(k, 16));
        }
    }
}

Output:

asha@mail.in -> bucket 6
ravi@mail.in -> bucket 15
meena@mail.in -> bucket 5
kabir@mail.in -> bucket 11
Aa -> bucket 0
BB -> bucket 0

Collisions

Two different keys in the same bucket is a collision. "Aa" and "BB" even have the same hash code:

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

public class Main {
    public static void main(String[] args) {
        System.out.println("Aa".hashCode() + " " + "BB".hashCode());
        System.out.println("Aa".equals("BB"));
        Map<String, Integer> m = new HashMap<>();
        m.put("Aa", 1);
        m.put("BB", 2);              // same bucket: a collision
        System.out.println(m.get("Aa") + " " + m.get("BB") + " " + m.size());
    }
}

Output:

2112 2112
false
1 2 2

The bucket keeps a small chain (a linked list of entries). get("BB") goes to bucket 0, then calls equals on each key in the chain until one matches. hashCode finds the bucket, equals finds the entry. A collision costs time, never correctness.

Keeping chains short

Mechanism When What happens
Load factor 0.75 size > capacity × 0.75 (16 × 0.75 = 12) the 13th entry triggers a resize: 32 buckets, every entry moved to its new bucket (rehash)
Treeify (Java 8+) a chain longer than 8, and the table has at least 64 buckets the chain becomes a red-black tree: O(log n) in that bucket

Average get/put/remove: O(1). If every key returned the same hashCode(), all entries would share one bucket and the map would degrade.

A HashMap allows one null key (it goes to bucket 0) and any number of null values.

Iterating a map

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

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put("asha@mail.in", "Asha");
        m.put("ravi@mail.in", "Ravi");
        m.put("meena@mail.in", "Meena");
        for (Map.Entry<String, String> e : m.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }
        for (String k : m.keySet()) System.out.print(k.charAt(0) + " ");
        System.out.println(m.values());
    }
}

Output:

meena@mail.in -> Meena
asha@mail.in -> Asha
ravi@mail.in -> Ravi
m a r [Meena, Asha, Ravi]
  • entrySet(): every entry; use getKey() and getValue(). Best when you need both.
  • keySet(): just the keys. values(): just the values.
  • The order is bucket order (5, 6, 15 here), not insertion order.

Trap 1: changing a key after putting it

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

public class Main {
    public static void main(String[] args) {
        Map<List<String>, String> team = new HashMap<>();
        List<String> key = new ArrayList<>(List.of("Asha", "Ravi"));
        team.put(key, "Robotics");
        System.out.println(team.get(key));
        key.add("Meena");                     // change the key after putting it
        System.out.println(team.get(key));
        System.out.println(team.size() + " " + team.containsKey(key));
    }
}

Output:

Robotics
null
1 false

The entry was filed under the old hash code. Adding Meena changed the list's hash code, so get looks in a different bucket. The entry is still there (size is 1) but unreachable. Use immutable keys: String, Integer, enums, records with immutable fields.

Trap 2: removing inside a for-each loop

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("chai", 0); stock.put("samosa", 12); stock.put("idli", 0);
        for (String item : stock.keySet()) {
            if (stock.get(item) == 0) stock.remove(item);
        }
        System.out.println(stock);
    }
}

Output:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.HashMap$HashIterator.nextNode(HashMap.java:1605)
    at java.base/java.util.HashMap$KeyIterator.next(HashMap.java:1628)
    at Main.main(Main.java:8)

The for-each loop uses a hidden iterator. When the map changes behind its back, the iterator fails fast with ConcurrentModificationException. Remove through the iterator itself (episode 30):

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("chai", 0); stock.put("samosa", 12); stock.put("idli", 0);
        Iterator<Map.Entry<String, Integer>> it = stock.entrySet().iterator();
        while (it.hasNext()) {
            if (it.next().getValue() == 0) it.remove();
        }
        System.out.println(stock);
    }
}

Output:

{samosa=12}

LinkedHashMap and TreeMap: choosing an order

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

public class Main {
    public static void main(String[] args) {
        String[] menu = { "samosa", "chai", "vada pav", "idli", "bun maska" };
        Map<String, Integer> h = new HashMap<>();
        Map<String, Integer> l = new LinkedHashMap<>();
        Map<String, Integer> t = new TreeMap<>();
        for (String s : menu) {
            h.put(s, s.length()); l.put(s, s.length()); t.put(s, s.length());
        }
        System.out.println("HashMap:       " + h.keySet());
        System.out.println("LinkedHashMap: " + l.keySet());
        System.out.println("TreeMap:       " + t.keySet());
    }
}

Output:

HashMap:       [bun maska, chai, samosa, idli, vada pav]
LinkedHashMap: [samosa, chai, vada pav, idli, bun maska]
TreeMap:       [bun maska, chai, idli, samosa, vada pav]
  • HashMap: bucket order, no promise.
  • LinkedHashMap: insertion order (a linked chain runs through the entries).
  • TreeMap: keys sorted, kept in a red-black tree; keys must be Comparable or you pass a Comparator (episode 34).

TreeMap tools: slabs and ranges

A delivery app's fee depends on the bill slab: from Rs 0 → Rs 40, from Rs 199 → Rs 25, from Rs 499 → free.

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, Integer> fee = new TreeMap<>();
        fee.put(0, 40);       // orders from Rs 0: delivery Rs 40
        fee.put(199, 25);     // from Rs 199: Rs 25
        fee.put(499, 0);      // from Rs 499: free
        for (int bill : new int[] { 150, 199, 350, 800 }) {
            int f = fee.floorEntry(bill).getValue();
            System.out.println("Bill " + bill + " -> fee " + f);
        }
        System.out.println(fee.firstKey() + " " + fee.lastKey() + " " + fee.headMap(499));
        System.out.println(fee.ceilingKey(200) + " " + fee.floorKey(200));
    }
}

Output:

Bill 150 -> fee 40
Bill 199 -> fee 25
Bill 350 -> fee 25
Bill 800 -> fee 0
0 499 {0=40, 199=25}
499 199
Method Returns
floorEntry(x) / floorKey(x) largest key ≤ x
ceilingEntry(x) / ceilingKey(x) smallest key ≥ x
firstKey() / lastKey() smallest / largest key
headMap(x) entries with keys < x
tailMap(x) entries with keys ≥ x

All are O(log n).

Which map?

Map Order get/put Notes
HashMap none O(1) average the default; one null key
LinkedHashMap insertion O(1) average a bit more memory
TreeMap sorted keys O(log n) floor/ceiling/headMap; no null key

Common mistakes (and the real error messages)

Mistake What you see Why Fix
int n = count.get(item); NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null missing key → null, then unboxing getOrDefault(item, 0) or merge
map.remove(k) inside for (String k : map.keySet()) java.util.ConcurrentModificationException the map changed mid-loop Iterator.remove()
changing a key object after put no error; get returns null its hash changed, wrong bucket immutable keys
two parallel lists no error; wrong person lists drift apart Map<K, V>
expecting HashMap to keep insertion order no error; bucket order buckets decide the order LinkedHashMap / TreeMap

Mini project: chai stall day report

Count orders, keep the menu order for the bill, and print the items alphabetically with a price slab discount.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> price = Map.of("chai", 15, "samosa", 20, "vada pav", 25, "idli", 40);
        String[] orders = { "chai", "samosa", "chai", "vada pav", "chai", "idli", "samosa", "chai" };

        Map<String, Integer> count = new LinkedHashMap<>();     // keeps the order items first appeared
        for (String o : orders) count.merge(o, 1, Integer::sum);

        int total = 0;
        for (Map.Entry<String, Integer> e : count.entrySet()) {
            int amount = e.getValue() * price.get(e.getKey());
            total += amount;
            System.out.println(e.getKey() + " x" + e.getValue() + " = Rs " + amount);
        }
        TreeMap<Integer, Integer> discount = new TreeMap<>(Map.of(0, 0, 100, 5, 200, 10));   // percent
        int pct = discount.floorEntry(total).getValue();
        System.out.println("Total Rs " + total + ", discount " + pct + "%, pay Rs " + (total - total * pct / 100));
        System.out.println("A to Z: " + new TreeMap<>(count));
    }
}

Output:

chai x4 = Rs 60
samosa x2 = Rs 40
vada pav x1 = Rs 25
idli x1 = Rs 40
Total Rs 165, discount 5%, pay Rs 157
A to Z: {chai=4, idli=1, samosa=2, vada pav=1}

Practice

  1. Count each word in "to be or not to be" with merge.
  2. Find the first non-repeating character in "swiss".
  3. Map roll numbers to marks and print them sorted by roll number.
  4. Income tax slabs (0 → 0%, 300000 → 5%, 700000 → 10%): find the rate for 450000 with floorEntry.
Solutions
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> words = new LinkedHashMap<>();
        for (String w : "to be or not to be".split(" ")) words.merge(w, 1, Integer::sum);
        System.out.println(words);

        Map<Character, Integer> freq = new LinkedHashMap<>();
        for (char c : "swiss".toCharArray()) freq.merge(c, 1, Integer::sum);
        for (Map.Entry<Character, Integer> e : freq.entrySet())
            if (e.getValue() == 1) { System.out.println(e.getKey()); break; }

        Map<Integer, Integer> marks = new TreeMap<>(Map.of(23, 81, 7, 92, 15, 67));
        System.out.println(marks);

        TreeMap<Integer, Integer> tax = new TreeMap<>(Map.of(0, 0, 300000, 5, 700000, 10));
        System.out.println(tax.floorEntry(450000).getValue() + "%");
    }
}

Output:

{to=2, be=2, or=1, not=1}
w
{7=92, 15=67, 23=81}
5%

Quick quiz

Map<String, Integer> m = new TreeMap<>();
m.put("b", 1);
m.put("a", 2);
System.out.print(m.put("b", 3) + " ");
System.out.print(m.get("c") + " ");
System.out.println(m);

A) null null {b=3, a=2} B) 1 null {a=2, b=3} C) 1 0 {a=2, b=3} D) 3 null {a=2, b=1}

Answer

B. put on an existing key returns the old value, 1. get on a missing key returns null. A TreeMap prints its keys sorted.

1 null {a=2, b=3}

Interview questions

  1. How does HashMap work internally? An array of buckets. hashCode() is spread (h ^ (h >>> 16)) and masked with n - 1 to pick a bucket; collisions are chained; equals finds the entry inside the bucket.
  2. What is the default capacity and load factor? 16 and 0.75; the map resizes (doubles and rehashes) when size exceeds capacity × load factor.
  3. What changed in Java 8? A bucket's chain longer than 8 (with a table of at least 64) is converted to a red-black tree, so a bad bucket is O(log n), not O(n).
  4. Why must the capacity be a power of two? So hash & (n - 1) equals hash % n, which is faster, and resizing splits each bucket cleanly.
  5. Why should keys be immutable? A key whose hash changes after insertion is filed in the wrong bucket and becomes unreachable.
  6. Can a HashMap have a null key? Yes, one. TreeMap can't (it must compare keys); Map.of and Hashtable allow none.
  7. HashMap vs Hashtable? Hashtable is old and synchronized and disallows nulls; use HashMap, or ConcurrentHashMap for threads.
  8. HashMap vs TreeMap? O(1) and no order vs O(log n) and sorted keys with navigation (floorKey, headMap).
  9. What causes ConcurrentModificationException? Structurally modifying a collection while iterating it with a for-each loop; use Iterator.remove() or removeIf.

Glossary

Term Meaning Example
Map A collection of key → value entries, one value per key Map<String, String>
Key The unique handle you look up by "asha@mail.in"
Value What is stored against a key "Asha Rao"
Entry One key with its value Map.Entry<K, V>
Parallel lists Two lists matched only by position emails + names
HashMap A map built on an array of buckets new HashMap<>()
Bucket One slot of the table, chosen from the hash 16 by default
Table / capacity The bucket array and its length 16, 32, 64...
Hash spreading Mixing high bits into low bits h ^ (h >>> 16)
Bucket index Which bucket a key goes to h & (n - 1)
Collision Two keys in the same bucket "Aa", "BB"
Chain The linked list of entries inside one bucket Aa → BB
Load factor How full the table may get before resizing 0.75
Resize / rehash Doubling the table and moving every entry 16 → 32
Treeify Turning a long chain into a red-black tree chain > 8
Unboxing Turning an Integer into an int int n = count.get(k)
getOrDefault get, with a fallback for missing keys getOrDefault(k, 0)
merge Insert, or combine with the old value merge(k, 1, Integer::sum)
Method reference A method passed as a value (episode 36) Integer::sum
Immutable key A key whose contents can't change String, records
ConcurrentModificationException Thrown when a collection changes during a for-each remove in a loop
Fail-fast iterator An iterator that stops as soon as it sees a change HashMap's iterators
LinkedHashMap A HashMap that remembers insertion order menu board
TreeMap A map with sorted keys (red-black tree) fee slabs
floorEntry / ceilingKey Nearest entry ≤ x / nearest key ≥ x slab for Rs 350
headMap / tailMap The part of the map below / from a key slabs below 499

Summary

  • Parallel lists drift apart and indexOf is O(n); a map keeps each key tied to its value.
  • put / get / remove / containsKey; put returns the old value; a missing key gives null.
  • Count with getOrDefault or merge, never by unboxing get's result.
  • Inside: 16 buckets, h ^ (h >>> 16), & (n - 1); collisions chain; load factor 0.75 resizes; long chains become trees.
  • Never change a key; remove inside loops with Iterator.remove().
  • LinkedHashMap keeps insertion order; TreeMap keeps keys sorted with floorEntry, ceilingKey, headMap.
  • Next: who gets served first? Queue, Deque, PriorityQueue, Stack (episode 33).