Java TreeMap 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

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.

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Java TreeMap Examples

Related Links:

.Net

Java

Related Links