TreeMap in Java

Soumitra

What is TreeMap?

  • It is a Red-Black tree based NavigableMap implementation.
  • Like HashMap it contains only unique elements.
  • Unlike HashMap it cannot have null key but like HashMap it can have multiple null values.
  • The map is sorted according to the natural ordering (ascending order) of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

Performance

TreeMap provides guaranteed log(n) time cost for the containsKey(), get(), put() and remove() operations.

Accessing in multi-threaded environment

Like HashMap and LinkedHashMap, the TreeMap implementation is not synchronized.

So multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be “wrapped” using the Collections.synchronizedMap() method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

Map m = Collections.synchronizedMap(new TreeMap(...));

For multi-threaded environment you can use ConcurrentHashMap instead of Synchronized TreeMap if you do not need the natural ordering of the keys but if you have same number of reader and writer threads then ConcurrentHashMap and Synchronized TreeMap will give the same performance. Therefore ConcurrentHashMap will give you best performance when you have many reader threads and very few writer threads.

More information could be found at http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

Fail-fast in TreeMap

If the map is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove() method, the iterator will throw a ConcurrentModificationException. 

Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

The fail-fast behavior of an iterator cannot be guaranteed and iterators throw ConcurrentModificationException on a best-effort basis.

Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

Set keys = treeMap.keySet();
for (Object key : keys) {
    treeMap.put(someObject, someValue); //it will throw the ConcurrentModificationException here
}

or

Set keys = treeMap.keySet();
for (Object key : keys) {
    treeMap.remove(key); //it will throw the ConcurrentModificationException here
}

Example

package com.roytuts.collections;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, String> llMap = new TreeMap<>();
        llMap.put("RedHat", "Unix");
        llMap.put("Google", "Android");
        llMap.put("Apple", "iOS");
        llMap.put("Microsoft", "Windows");
        // iterate over HashMap
        llMap.forEach((k, v) -> System.out.println(k + " => " + v));
        System.out.println();
        // iterate using iterator
        Iterator<Entry<String, String>> iterator = llMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<java.lang.String, java.lang.String> entry = (Map.Entry<java.lang.String, java.lang.String>) iterator
                    .next();
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }
    }
}

Output

Apple => iOS
Google => Android
Microsoft => Windows
RedHat => Unix
Apple => iOS
Google => Android
Microsoft => Windows
RedHat => Unix

Thanks for reading.

Leave a Comment