Java TreeMap Examples

These Java examples use the TreeMap collection. A TreeMap allows lookups and implements a red-black tree algorithm.
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.

Put: This method places keys (and their associated values) into the TreeMap. It is the same as the HashMap put().

Get: This returns a value from the TreeMap based on a key. Please consider the getOrDefault method for simpler code.

Java program that uses TreeMap put, get 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); } } Output 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.

EntrySet: This is one way to loop over the entire TreeMap. We import java.util.Map.Entry and use the Entry class.

Java program that uses getOrDefault, entrySet 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); } } } Output 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.
Java program that uses containsKey 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); } } } Output 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.

Ceiling, higher: A ceiling key is equal to or higher than the argument. A higher key is always higher.

Floor, lower: These are opposite ceiling. A floor key is equal to or lower than the argument.

First, last: These return the lowest and highest key according to how the TreeMap is internally sorted.

Java program that uses ceiling, floor, higher, lower methods 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()); } } Output 6=fish 10 10 100 2 First and last 0 100
Performance, HashMap versus TreeMap. Here we compare performance. We create two small collections: a HashMap and a TreeMap. We ensure the containsKey methods are compiled.

Description: We call the containsKey on the two collections many times, on keys that do and do not exist.

Result: The HashMap is faster. This is as expected: hashing collections are usually faster.

Note: This benchmark is limited: it tests small collections. And it does not involve navigation, which is not possible with HashMap.

Java program that times HashMap, TreeMap 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); } } Output 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.HashMap
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.

For simple uses: 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.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
HomeSearch
Home
Dot Net Perls