TreeMap. This is a NavigableMap collection: it acts like a lookup dictionary, but allows navigation of its keys. In it, we store keys that point to values.
In navigation, we can access near keys. We can get ceiling, floor, higher and lower keys than any possible key. Even the lowest and highest keys are easily accessed.
An example. Let us consider this program. It uses some of the simplest methods from TreeMap: you will recognize these from other collections like HashMap.
Info Put() places keys (and their associated values) into the TreeMap. It is the same as the HashMap put().
And Get() returns a value from the TreeMap based on a key. Please consider the getOrDefault method for simpler code.
import java.util.TreeMap;
public class Program {
public static void main(String[] args) {
// Create TreeMap and add three entries to it.
TreeMap<String, Integer> tree = new TreeMap<>();
tree.put("cat", 6);
tree.put("dog", 4);
tree.put("bird", 10);
// Look up a value from a key in the TreeMap.
int value = tree.get("dog");
System.out.println(value);
}
}4
GetOrDefault, entrySet. Here are some more abilities of the TreeMap. The putIfAbsent calls add new keys only if no matching ones yet exist.
And GetOrDefault simplifies how we access values from TreeMap. It returns the second argument if no key exists.
Tip EntrySet() is one way to loop over the entire TreeMap. We import java.util.Map.Entry and use the Entry class.
import java.util.Map.Entry;
import java.util.TreeMap;
public class Program {
public static void main(String[] args) {
TreeMap<Integer, Integer> tree = new TreeMap<>();
// These calls place values in the TreeMap.
tree.putIfAbsent(10, 100);
tree.putIfAbsent(20, 200);
// These have no effect because keys already exist.
tree.putIfAbsent(10, -10);
tree.putIfAbsent(20, -10);
// Get keys (or default values) in the tree.
int result1 = tree.getOrDefault(10, 0);
int result2 = tree.getOrDefault(100, 0);
System.out.println(result1);
System.out.println(result2);
for (Entry<Integer, Integer> entry : tree.entrySet()) {
System.out.println(entry);
}
}
}100
0
10=100
20=200
ContainsKey, containsValue. These methods are also useful. They are the same on TreeMap as on other collections like HashMap. We see that TreeMap can be used in standard ways.
import java.util.TreeMap;
public class Program {
public static void main(String[] args) {
TreeMap<String, String> tree = new TreeMap<>();
tree.put("red", "apple");
// Test the containsKey and containsValue methods.
if (tree.containsKey("red")) {
System.out.println(true);
}
if (tree.containsValue("apple")) {
System.out.println(true);
}
}
}true
true
Ceiling, floor, higher, lower. Here are some specialized NavigableMap methods. With methods like ceilingKey, we pass a key, and the tree returns an existing, higher or equal key.
So The call to ceilingKey(9) returns 10: this is the "ceiling" key to 9. FloorKey acts in reverse.
Info A ceiling key is equal to or higher than the argument. A higher key is always higher.
import java.util.Map.Entry;
import java.util.TreeMap;
public class Program {
public static void main(String[] args) {
TreeMap<Integer, String> tree = new TreeMap<>();
tree.put(1, "apple");
tree.put(2, "bird");
tree.put(0, "carrot");
tree.put(100, "spider");
tree.put(6, "fish");
tree.put(10, "bread");
// Get ceiling keys relative to possible keys.
Entry<Integer, String> entry = tree.ceilingEntry(5);
int key = tree.ceilingKey(9);
System.out.println(entry);
System.out.println(key);
key = tree.floorKey(99); // Get a floor key.
System.out.println(key);
key = tree.higherKey(20); // Get a higher key.
System.out.println(key);
key = tree.lowerKey(5); // Get a lower key.
System.out.println(key);
System.out.println("First and last");
System.out.println(tree.firstKey());
System.out.println(tree.lastKey());
}
}6=fish
10
10
100
2
First and last
0
100
Benchmark, TreeMap. Here we compare performance. We create 2 small collections: a HashMap and a TreeMap. We ensure the containsKey methods are compiled.
Version 1 In this version of the code, we perform many lookups (in a tight loop) on the HashMap instance.
Version 2 In this code, we perform the same lookups as done in version 1, but use a TreeMap collection instead.
Result The HashMap is faster. This is as expected: hashing collections are usually faster.
Warning This benchmark is limited: it tests small collections. And it does not involve navigation, which is not possible with HashMap.
import java.util.HashMap;
import java.util.TreeMap;
public class Program {
public static void main(String[] args) throws Exception {
HashMap<Integer, Integer> hash = new HashMap<>();
TreeMap<Integer, Integer> tree = new TreeMap<>();
// Add values to our collections.
for (int v = 0; v < 1000; v += 100) {
hash.put(v, v);
tree.put(v, v);
}
// Ensure methods are compiled.
if (hash.containsKey(999) || tree.containsKey(999)) {
throw new Exception();
}
long t1 = System.currentTimeMillis();
// Version 1: do lookups in HashMap.
for (int i = 0; i < 10000000; i++) {
if (!hash.containsKey(500) || !hash.containsKey(900)
|| hash.containsKey(999)) {
throw new Exception();
}
}
long t2 = System.currentTimeMillis();
// Version 2: do lookups in TreeMap.
for (int i = 0; i < 10000000; i++) {
if (!tree.containsKey(500) || !tree.containsKey(900)
|| tree.containsKey(999)) {
throw new Exception();
}
}
long t3 = System.currentTimeMillis();
// ... Benchmark times.
System.out.println(t2 - t1);
System.out.println(t3 - t2);
}
}187 ms, HashMap containsKey
214 ms, TreeMap containsKey
In terms of raw performance, HashMap will usually have an advantage over TreeMap. But TreeMap has advantages, like key navigation. These are less often needed.
In my analysis, a TreeMap is only a clear win when key-based navigation (as with higherKey()) is used. In my experience, hashing collections have a performance edge over binary trees.
However If the features available in NavigableMap are used, a TreeMap could certainly be superior in performance.
Tip HashMap is a better choice. TreeMap for simple lookups will likely just perform slower.
Specialized trees, as for optimized string lookups, can be constructed. These outperform HashMap and TreeMap. But TreeMap, a generalized implementation, is not universally faster.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Mar 21, 2023 (simplify).