Java TreeMap is one of the Map implementation and it’s part of Java Collections framework.

Java TreeMap

java-treemap-example

Some of the important points to remember about TreeMap in java are;

  1. Apart from implementing Map interface, Java TreeMap also implements NavigableMap and indirectly implements SortedMap interface. TreeMap also extends AbstractMap class.
  2. TreeMap entries are sorted in the natural ordering of its keys. It also provides a constructor to provide Comparator to be used for ordering. So if you are using any class as key, make sure it’s implementing Comparable interface for natural ordering. Check out java collections interview questions to understand the importance of these methods.
  3. Java TreeMap implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
  4. TreeMap is not synchronized and hence not thread-safe. For multithreaded environments, you can get a wrapped synchronized using Collections.synchronizedSortedMap method.
  5. TreeMap methods to get keyset and values return Iterator that are fail-fast in nature, so any concurrent modification will throw ConcurrentModificationException.
  6. TreeMap in java doesn’t allow null keys, however you can have multiple null values associated with different keys.

Java TreeMap Example

Let’s look at java TreeMap example program to see it’s natural sorting in action.

It will produce below output.

Notice that when we are not providing Comparator while creating TreeMap, it’s using Integer compareTo method for ordering of keys. That’s why keys are in increasing order even though we insert it in any order.

Next time, we are providing Comparator implementation to reverse the order and it’s being used by TreeMap. So the keys are stored in descending order.

For simplicity, I am providing an anonymous class implementation of Comparator above, we can use lambda expressions to do the same in a single line.

TreeMap vs HashMap

TreeMap and HashMap both implements Map interface and part of collection framework. Let’s look at some of the differences between TreeMap vs HashMap.

  1. TreeMap entries are sorted in natural ordering of keys whereas HashMap doesn’t store entries in any order.
  2. TreeMap doesn’t allow null key whereas we can have one null key in HashMap.
  3. Since TreeMap stores entries in sorted way, it’s a bit slower that HashMap in storing and retrieving objects.
  4. TreeMap uses Red-Black tree based NavigableMap implementation whereas HashMap uses hashing algorithm implementation.
  5. TreeMap implements NavigableMap, so you get some extra features that are not present in HashMap. For example – submap, first key, last key, head map, tail map etc.

When to use TreeMap in Java

Most of the time HashMap will be enough to use as Map implementation in your program. But if you have some special requirements related to sorting, finding next lower and higher key, work on a submap then you can go for TreeMap.

Let’s look at a simple TreeMap example program showing usage of NavigableMap methods.

When we execute above TreeMap example program, it produces following output.

All the above operations are self understood, please look into official documentation or comment here if you are confused about any of these.

That’s all for a quick roundup for TreeMap in java, I hope you enjoyed reading it.

References: Official API Documentation

By admin

Leave a Reply