Skip to content

Intermediate · The collections framework · topic 33 of 60 · 30 min

Maps: HashMap, LinkedHashMap and TreeMap

Explanation

A Map stores key → value pairs with unique keys: a PIN code to a city, a SKU to stock. HashMap is the everyday choice (fast, no order), LinkedHashMap keeps insertion order and TreeMap keeps keys sorted. getOrDefault, merge and computeIfAbsent make counting and grouping short. HashMap uses hashCode to choose a bucket and equals to find the key inside it.

Why maps?

Looking things up by a key is everywhere: the stock of a SKU, the city for a PIN code, the cart of a user id. Searching a list each time is slow. A Map stores pairs and finds the value for a key almost instantly.

java
Map<String, Integer> stock = new HashMap<>();
stock.put("RICE-5KG", 40);
stock.put("DAL-1KG", 25);
stock.put("RICE-5KG", 38);                       // same key: value replaced
System.out.println(stock.get("RICE-5KG"));       // 38
System.out.println(stock.get("GHEE"));           // null (no such key)
System.out.println(stock.getOrDefault("GHEE", 0));   // 0
System.out.println(stock.containsKey("DAL-1KG"));    // true
stock.remove("DAL-1KG");

for (Map.Entry<String, Integer> e : stock.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

Counting and grouping, the modern way

java
String[] words = {"chai", "samosa", "chai", "jalebi", "chai"};
Map<String, Integer> count = new HashMap<>();
for (String w : words) count.merge(w, 1, Integer::sum);       // {chai=3, samosa=1, jalebi=1}

Map<String, List<String>> byCity = new HashMap<>();
byCity.computeIfAbsent("Pune", k -> new ArrayList<>()).add("Asha");
byCity.computeIfAbsent("Pune", k -> new ArrayList<>()).add("Ravi");
System.out.println(byCity);                                   // {Pune=[Asha, Ravi]}

Which Map?

MapKey orderSpeedNotes
HashMapNo guaranteed orderO(1) averageAllows one null key; the default choice
LinkedHashMapInsertion order (or access order)O(1) averageGood for predictable output; can build an LRU cache
TreeMapSorted keysO(log n)firstKey, floorKey, headMap, tailMap
Map.of(...)Unspecified-Small unmodifiable maps (Java 9+)

How HashMap works (interview favourite)

  1. Inside is an array of buckets.
  2. put(key, value) calls key.hashCode(), mixes the bits, and picks a bucket index from it.
  3. If the bucket is empty, the entry goes there. If other keys are already there (a collision), Java compares with equals: an equal key gets its value replaced; otherwise the new entry is added to that bucket.
  4. When the map gets too full (by default more than 75% of the buckets, the load factor 0.75), it doubles its array and redistributes the entries (rehashing).
  5. Since Java 8, a bucket with many colliding entries is turned into a small balanced tree, so the worst case stays fast.

get(key) repeats the same steps to find the bucket and uses equals to find the exact key. That is why keys must have correct, consistent equals and hashCode, and why mutable objects make poor keys.

Careful: Using a key whose fields you change after inserting it (for example a mutable Customer object) breaks the map: its hashCode changes, so get looks in the wrong bucket and the entry seems lost. Use immutable keys: String, Integer, records, enums.
Think of it like this: A HashMap is like a big post office with numbered sorting boxes. The PIN code (hashCode) decides which box a letter goes into; inside the box, the clerk reads the full address (equals) to find the right letter. If too many letters arrive, the post office builds a bigger rack (rehashing).
Tip: Iterate with entrySet() when you need both keys and values; calling get for each key in keySet() does twice the work.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

Maps: HashMap, LinkedHashMap and TreeMap · 1/6

Maps

In this lesson you will look things up by key with Maps.

Prefer a video by a teacher? Find free videos on “java hashmap internal working buckets hashcode equals tutorial” on YouTube ↗

In real life: Sales per city

An analytics job at a retail chain reads thousands of sales records and totals the amount per city with merge. A TreeMap is used for the final report so cities print alphabetically.

java
record Sale(String city, int amount) {}
List<Sale> sales = List.of(new Sale("Pune", 500), new Sale("Agra", 300), new Sale("Pune", 200));
Map<String, Integer> totals = new TreeMap<>();
for (Sale s : sales) totals.merge(s.city(), s.amount(), Integer::sum);
System.out.println(totals);   // {Agra=300, Pune=700}

Practice (0/3 done)

Task 1 · Question

What does this print? Map<String, Integer> m = new HashMap<>(); m.put("a", 1); m.put("a", 2); m.merge("a", 10, Integer::sum); System.out.println(m.get("a") + " " + m.size());

Task 2 · Code · Javascript

The same counting idea in JavaScript, which runs here: write wordCount(text) that returns a Map from each lower-case word to its count, like Java's map.merge(word, 1, Integer::sum).

Task 3 · Practice

Write a program that groups students by city: from a list of records Student(name, city), build a Map<String, List<String>> with computeIfAbsent, then print the cities in alphabetical order with a TreeMap, each followed by its students.

Quick quiz

Question 1

1.What does map.get(key) return for a missing key in a HashMap?

Question 2

2.Which map keeps keys sorted?

Question 3

3.What is the default load factor of HashMap?

Question 4

4.Which two methods must a HashMap key class implement correctly?

Read more (free)

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

What does map.get(key) return for a missing key in a HashMap?

Answer: null

Use getOrDefault to avoid null.

Which map keeps keys sorted?

Answer: TreeMap

TreeMap is sorted by key.

What is the default load factor of HashMap?

Answer: 0.75

At 75% full the table is resized.

Which two methods must a HashMap key class implement correctly?

Answer: equals and hashCode

hashCode chooses the bucket; equals finds the key.

Which key type cannot be used in a std HashMap?Related

Answer: f64

f64 does not implement Hash and Eq, because NaN is not equal to itself.

From HashMap and HashSet

Default Object.equals behaves like…Related

Answer: ==, same object only

Without overriding, equals checks identity.

From toString, equals, hashCode and records

What is the time to find a key in std::map with n keys?Related

Answer: O(log n)

std::map is a balanced tree, so its height is about log n.

From std::map and std::unordered_map

Why must a HashMap key override both equals and hashCode?Related

Answer: So equal keys land in the same bucket and are found

The contract keeps lookups correct.

From Java interview questions

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Sorting with Comparable and Comparator →

Next steps

  1. 2 more topics in “The collections framework” before its exam: Sorting with Comparable and Comparator, Queues, stacks and priority queues.
  2. Module 7 exam: The collections framework · 12 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Lambdas, streams and files. 60 topics left in the course before the final exam.

← Previous: Sets: HashSet, LinkedHashSet and TreeSet