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 withInteger::sum.Integer::sumis 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
hashCode()turns the key into anint(it can be negative).- 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. - Index:
& (n - 1)keeps the low bits. Because the table sizenis always a power of two, this equalsh 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; usegetKey()andgetValue(). 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
Comparableor you pass aComparator(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
- Count each word in
"to be or not to be"withmerge. - Find the first non-repeating character in
"swiss". - Map roll numbers to marks and print them sorted by roll number.
- 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
- How does HashMap work internally? An array of buckets.
hashCode()is spread (h ^ (h >>> 16)) and masked withn - 1to pick a bucket; collisions are chained;equalsfinds the entry inside the bucket. - What is the default capacity and load factor? 16 and 0.75; the map resizes (doubles and rehashes) when size exceeds capacity × load factor.
- 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).
- Why must the capacity be a power of two? So
hash & (n - 1)equalshash % n, which is faster, and resizing splits each bucket cleanly. - Why should keys be immutable? A key whose hash changes after insertion is filed in the wrong bucket and becomes unreachable.
- Can a HashMap have a null key? Yes, one.
TreeMapcan't (it must compare keys);Map.ofandHashtableallow none. - HashMap vs Hashtable? Hashtable is old and synchronized and disallows nulls; use
HashMap, orConcurrentHashMapfor threads. - HashMap vs TreeMap? O(1) and no order vs O(log n) and sorted keys with navigation (
floorKey,headMap). - What causes ConcurrentModificationException? Structurally modifying a collection while iterating it with a for-each loop; use
Iterator.remove()orremoveIf.
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
indexOfis O(n); a map keeps each key tied to its value. put/get/remove/containsKey;putreturns the old value; a missing key givesnull.- Count with
getOrDefaultormerge, never by unboxingget'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).