The TreeMap Class – Collections: Part II
By Jaime Williams / September 23, 2022 / No Comments / Composing Stream Pipelines, Oracle Certification Exam
The TreeMap<K,V> Class
The TreeMap<K, V> class is the analog of the TreeSet<E> class (p. 812), but in this case for maps. It provides an implementation that sorts its entries in a specific order (see also Figures 15.2 and 15.3, p. 786).
The TreeMap<K, V> class implements the NavigableMap<K, V> interface, and thereby the SortedMap<K, V> interface. By default, operations on sorted maps rely on the natural ordering of the keys. However, a total ordering can be specified by passing a customized comparator to the constructor.
A key in a TreeMap<K, V> cannot have the null value, but the value associated with a key in an entry can be null.
The TreeMap<K, V> implementation uses balanced trees, which deliver excellent performance for all operations. However, searching in a HashMap<K, V> can be faster than in a TreeMap<K, V>, as hashing algorithms usually offer better performance than the search algorithms for balanced trees.
The TreeMap<K, V> class provides four constructors, analogous to the ones in the TreeSet<E> class:
TreeMap()
A standard constructor used to create a new empty sorted map, according to the natural ordering of the keys.
TreeMap(Comparator<? super K> c)
A constructor that takes an explicit comparator for the keys, that is used to order the entries in the map.
TreeMap(Map<? extends K, ? extends V> map)
A constructor that can create a sorted map based on a map, according to the natural ordering of the keys of the specified map.
TreeMap(SortedMap<K, ? extends V> map)
A constructor that creates a new map containing the same entries as the specified sorted map, with the same ordering for the keys as the specified map.
Example 15.11 illustrates using navigable maps. It also prints a textual histogram like the one in Example 15.10, but using a TreeMap<K, V>, and in addition, it prints some statistics about the navigable map. See also the output from running the example. Some remarks about Example 15.11:
- An empty NavigableMap<Integer, Integer> is created at (1), where the key is the weight group and the value is the frequency. The loop at (2) reads the weights specified as program arguments, and creates a frequency map, as described in Example 15.10.
- The method printHistogram() at (15) prints a histogram of the frequencies in a navigable map:
public static <K> void printHistogram(NavigableMap<K, Integer> freqMap) {…}
It is a generic method with one type parameter, K, that specifies the type of the keys, and the type of the values (i.e., frequencies) is Integer. It prints the map and the number of entries in the map at (16) and (17), respectively. The forEach() method is invoked on the map at (18) to iterate over the entries in order to print the histogram, as explained in Example 15.10.
Printing the histogram at (3) shows the number of entries ordered in ascending key order and the size of the map:
Group frequency map: {10=1, 60=1, 75=3, 80=1, 90=1, 95=2, 185=1}
No. of weight groups: 7
…
- Calls to the methods firstEntry() and lastEntry() at (4) and (5):
out.println(“First entry: ” + groupFreqMap.firstEntry()); // (4)
out.println(“Last entry: ” + groupFreqMap.lastEntry()); // (5)
return the following entries, respectively:
First entry: 10=1
Last entry: 185=1
- Calls to the methods floorEntry() and higherKey() with the key value 77 at (6) and with the key value 90 at (7), respectively:
out.println(“Greatest entry <= 77: “
+ groupFreqMap.floorEntry(77)); // (6)
out.println(“Smallest key > 90: “
+ groupFreqMap.higherKey(90)); // (7)
give the following output, respectively:
Greatest entry <= 77: 75=3
Smallest key > 90: 95
- Calls to the methods tailMap(75, true) and headMap(75, false) at (8) and (9) with the argument 75:
…
printHistogram(groupFreqMap.tailMap(75, true)); // (8)
…
printHistogram(groupFreqMap.headMap(75, false)); // (9)
return the following map views, respectively:
Tail map (Groups >= 75): {75=3, 80=1, 90=1, 95=2, 185=1}
…
Head map (Groups < 75): {10=1, 60=1}
…
- The call to the subMap() method at (10)
printHistogram(groupFreqMap.subMap( // (10)
groupFreqMap.firstEntry().getKey(), false,
groupFreqMap.lastEntry().getKey(), false));
returns the map view with the first and the last entry excluded:
Frequency map (first and last entry excluded): {60=1, 75=3, 80=1, 90=1, 95=2}
…
- Polling of a navigable map is shown at (11). Polling is done directly on the navigable map, and the first entry in the map is always retrieved and removed by the pollFirstEntry() method at (12). A while loop is used to iterate over the entries in the map until the map is empty. For each entry, its key and its value is printed.
// Poll the navigable map: // (11)
int sumValues = 0;
while (!groupFreqMap.isEmpty()) {
Map.Entry<Integer, Integer> entry = groupFreqMap.pollFirstEntry(); // (12)
Integer frequency = entry.getValue();
sumValues += frequency;
out.printf(“%5s: %s%n”, entry.getKey(), frequency);
}
The number of weights—that is, the sum of the values in the map—is also calculated in the loop and printed at (13) and (14), respectively. After polling the map, the output shows that the map is empty.
Example 15.11 Using Navigable Maps
import java.util.Collections;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;
import static java.lang.System.out;
public class HistogramStats {
public static void main(String[] args) {
// Create a navigable map to store the frequency for each group.
NavigableMap<Integer, Integer> groupFreqMap = new TreeMap<>(); // (1)
// Determine the frequencies:
for (String argument : args) { // (2)
double weight = Double.parseDouble(argument);
int weightGroup = (int) Math.round(weight/5.0)*5;
groupFreqMap.merge(weightGroup, 1, Integer::sum);
}
// Print statistics about the frequency map:
out.print(“Group frequency map: “);
printHistogram(groupFreqMap); // (3)
out.println(“First entry: ” + groupFreqMap.firstEntry()); // (4)
out.println(“Last entry: ” + groupFreqMap.lastEntry()); // (5)
out.println(“Greatest entry <= 77: “
+ groupFreqMap.floorEntry(77)); // (6)
out.println(“Smallest key > 90: “
+ groupFreqMap.higherKey(90)); // (7)
out.print(“Tail map (Groups >= 75): “);
printHistogram(groupFreqMap.tailMap(75, true)); // (8)
out.print(“Head map (Groups < 75): “);
printHistogram(groupFreqMap.headMap(75, false)); // (9)
out.print(“Frequency map (first and last entry excluded): “);
printHistogram(groupFreqMap.subMap( // (10)
groupFreqMap.firstEntry().getKey(), false,
groupFreqMap.lastEntry().getKey(), false));
// Poll the navigable map: (11)
out.println(“Histogram (by polling):”);
int sumValues = 0;
while (!groupFreqMap.isEmpty()) {
Map.Entry<Integer, Integer> entry = groupFreqMap.pollFirstEntry(); // (12)
Integer frequency = entry.getValue();
sumValues += frequency;
out.printf(“%5s: %s%n”, entry.getKey(), frequency);
}
out.println(“Number of weights registered: ” + sumValues); // (13)
out.println(“Group frequency map after polling: ” + groupFreqMap); // (14)
}
// Prints a histogram for entries in a navigable map.
public static <K> void printHistogram(NavigableMap<K, Integer> freqMap) {// (15)
out.println(freqMap); // (16)
out.println(“No. of entries: ” + freqMap.size()); // (17)
freqMap.forEach((k, v) -> // (18)
out.printf(“%5s: %s%n”, k,
String.join(“”, Collections.nCopies(v, “*”))));
}
}
Running the program with the following arguments:
>
java HistogramStats 74 75 93 75 93 82 61 92 10 185
gives the following output:
Click here to view code image Group frequency map: {10=1, 60=1, 75=3, 80=1, 90=1, 95=2, 185=1}
No. of entries: 7
10: *
60: *
75: ***
80: *
90: *
95: **
185: *
First entry: 10=1
Last entry: 185=1
Greatest entry <= 77: 75=3
Smallest key > 90: 95
Tail map (Groups >= 75): {75=3, 80=1, 90=1, 95=2, 185=1}
No. of entries: 5
75: ***
80: *
90: *
95: **
185: *
Head map (Groups < 75): {10=1, 60=1}
No. of entries: 2
10: *
60: *
Frequency map (first and last entry excluded): {60=1, 75=3, 80=1, 90=1, 95=2}
No. of entries: 5
60: *
75: ***
80: *
90: *
95: **
Histogram (by polling):
10: 1
60: 1
75: 3
80: 1
90: 1
95: 2
185: 1
Number of weights registered: 10
Group frequency map after polling: {}