Grouping and counting
Lesson 072 covered the methods of one pair. The work starts when a map holds a collection for each key, or when the entries have to be printed in an order the map does not keep. Three patterns cover most of it: computeIfAbsent to build the value once, merge to accumulate a number, and a sorted copy of entrySet to print by value.
A map of lists
A word index maps a word to the lines it appears on, so the value is a list and the list has to exist before the first line number is added. computeIfAbsent does exactly that: it returns the existing list, or creates one with the function and stores it. The program below indexes three lines:
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class Index {
public static void main(String[] args) {
String[] lines = {
"the cat sat",
"the dog sat",
"a cat naps",
};
Map<String, List<Integer>> index = new LinkedHashMap<>();
for (int line = 0; line < lines.length; line++) {
for (String word : lines[line].split(" ")) {
index.computeIfAbsent(word, k -> new ArrayList<>()).add(line + 1);
}
}
for (Map.Entry<String, List<Integer>> entry : index.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
}
}
javac -Xlint:all Index.java
java Index
the [1, 2]
cat [1, 3]
sat [1, 2]
dog [2]
a [3]
naps [3]
The line numbers count from one because the loop counts from zero and the code adds one. The order is the order of first appearance, which is what LinkedHashMap keeps; a plain HashMap would print the same pairs in no order. computeIfAbsent runs its function only for a key that is not there, so the index never has to check for null.
Counting with merge
A counter is the same shape with a number for a value, and merge makes it one line: the value 1 for a new key and the sum for an old one. The counts are then copied into a list of entries, because a map has no order to sort and a list has:
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class Counts {
public static void main(String[] args) {
String text = "b a b c b a";
Map<String, Integer> counts = new LinkedHashMap<>();
for (String word : text.split(" ")) {
counts.merge(word, 1, Integer::sum);
}
System.out.println(counts);
List<Map.Entry<String, Integer>> entries = new ArrayList<>(counts.entrySet());
entries.sort(Comparator
.comparing(Map.Entry<String, Integer>::getValue).reversed()
.thenComparing(Map.Entry::getKey));
for (Map.Entry<String, Integer> entry : entries) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
}
}
javac -Xlint:all Counts.java
java Counts
{b=3, a=2, c=1}
b 3
a 2
c 1
The comparator reads the value of an entry, reverses it so the largest comes first, and breaks a tie by the key. Without the thenComparing the order of equal counts would be the order the list happened to have. Sorting a copy and leaving the map alone is the usual pattern: the map is the data, the list is the presentation.
Sorting a map by its values
There is no method on Map that sorts, because a hash map has no order to preserve. The three ways to present the entries in an order are a TreeMap for the key order, a sorted list of the entries as above, and a stream with sorted in the pipeline, which a later lesson shows for the same problem.
The key order is the cheap one: new TreeMap<>(map) copies the entries and keeps them sorted by key. The value order always needs the list, because the comparator must see the values and a tree of keys cannot compare them.
Grouping
Grouping is a map of lists where the key is the group. A TreeMap keeps the cities in alphabetical order, and the sizes are a second map built from the first:
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class Groups {
public static void main(String[] args) {
Map<String, List<String>> byCity = new TreeMap<>();
String[][] people = {{"Ada", "London"}, {"Grace", "New York"}, {"Alan", "London"}};
for (String[] person : people) {
byCity.computeIfAbsent(person[1], k -> new ArrayList<>()).add(person[0]);
}
for (Map.Entry<String, List<String>> entry : byCity.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
Map<String, Integer> sizes = new LinkedHashMap<>();
byCity.forEach((city, names) -> sizes.put(city, names.size()));
System.out.println(sizes);
System.out.println("largest " + largest(sizes));
}
static String largest(Map<String, Integer> sizes) {
String best = null;
for (Map.Entry<String, Integer> entry : sizes.entrySet()) {
if (best == null || entry.getValue() > sizes.get(best)) {
best = entry.getKey();
}
}
return best;
}
}
javac -Xlint:all Groups.java
java Groups
London: [Ada, Alan]
New York: [Grace]
{London=2, New York=1}
largest London
Inside a group the names keep the order they were added in, because the value is an ArrayList; the groups themselves are alphabetical because the key is a TreeMap. Those two orders are independent, which is the point of a map of lists: the key decides where the group goes and the list decides what is inside it.
The map forEach
Map.forEach takes a BiConsumer of the key and the value, which is why the lambda in the program has two parameters. It is shorter than an entrySet loop when the body only reads, and the entrySet loop is still the one to use when the entry itself is needed, as in the sort above.
A lambda may not change the map it walks: putting a key while the forEach runs throws ConcurrentModificationException, exactly as a removal inside a for-each over a list does in lesson 070. The copy in the example is not a style choice; it is what makes the update legal.
Exercises
- Add a fourth line to Index and print the index again.
- Count the words of a sentence and print the three most frequent, in order.
- Group the same people by the first letter of the name and print the groups.
- Sort the entries of Counts by key instead of by value and compare the output.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does
computeIfAbsentdo for a key that is not in the map?Answer
Creates the value with the function, stores it and returns it
The created value is put in the map and returned, so the caller can use it at once.
-
Why is a map copied into a list before it is sorted by value?
Answer
A map has no order, and a list is the structure that can be sorted
Sorting needs a sequence, and the entries of a map are not one.
-
What does
thenComparingadd to a comparator?Answer
A second key to decide the elements the first key leaves equal
It is the tie-break, applied only when the first comparison answers zero.
-
What does this program print?
import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.TreeMap; public class Q1 { public static void main(String[] args) { Map<String, List<String>> map = new TreeMap<>(); map.computeIfAbsent("b", k -> new ArrayList<>()).add("x"); map.computeIfAbsent("a", k -> new ArrayList<>()).add("y"); map.computeIfAbsent("b", k -> new ArrayList<>()).add("z"); System.out.println(map); } }Answer
{a=[y], b=[x, z]}
The sorted map orders the keys, and the second call for b appends to the same list.
-
What does this program print?
import java.util.LinkedHashMap; import java.util.Map; public class Q2 { public static void main(String[] args) { Map<String, Integer> counts = new LinkedHashMap<>(); for (String word : new String[] {"x", "y", "x"}) { counts.merge(word, 1, Integer::sum); } System.out.println(counts); } }Answer
{x=2, y=1}
The repeated word is summed to two and the linked map keeps the order of first appearance.
-
What does this program print?
import java.util.HashMap; import java.util.Map; public class Q3 { public static void main(String[] args) { Map<String, StringBuilder> map = new HashMap<>(); for (String word : new String[] {"a", "b", "a"}) { map.computeIfAbsent(word, k -> new StringBuilder()).append("!"); } System.out.println(map.get("a")); System.out.println(map.get("b")); } }Answer
!! / !
The builder for a is created once and appended to twice, and b once.
-
What does this program print?
import java.util.Map; import java.util.TreeMap; public class Q4 { public static void main(String[] args) { Map<String, Integer> map = new TreeMap<>(); map.put("b", 2); map.put("a", 1); map.put("c", 3); for (Map.Entry<String, Integer> e : map.entrySet()) { System.out.print(e.getKey() + e.getValue() + " "); } } }Answer
a1 b2 c3
The tree orders the keys, and each entry prints its key and value.
-
What does this program print?
import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.TreeMap; public class Q5 { public static void main(String[] args) { Map<String, List<Integer>> map = new TreeMap<>(); map.computeIfAbsent("x", k -> new ArrayList<>()).add(5); System.out.println(map.get("x").size()); System.out.println(map.get("y")); } }Answer
1 then null
Only x was created, and a key that was never asked for has no value.
-
Why may a lambda inside
forEachnot put a key into the map?Answer
The map is being iterated, so a change throws ConcurrentModificationException
The iteration notices the change on its next step, as a list iterator does.
-
What does
new TreeMap<>(map)give?Answer
A copy of the entries, ordered by key
The constructor copies the entries into a sorted map, which orders them by key.
The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.
Article author: Arthur Isaev