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.

Example

Let us consider this program. It uses some of the simplest methods from TreeMap: you will recognize these from other collections like HashMap.

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.

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.

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.

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.

Specialized trees, as for optimized string lookups, can be constructed. These outperform HashMap and TreeMap. But TreeMap, a generalized implementation, is not universally faster.