TreeMap in Java – The Sorted Map

TreeMap in Java is one of the implementation of the Map interface. How it differs from the other implementation HashMap is that unlike HashMap which is unordered, TreeMap is Sorted.

TreeMap is sorted according to the natural ordering of its keys by default. If you want different sort ordering then you will have to provide a Comparator at the TreeMap construction time.

TreeMap is a Red-Black tree based implementation of Map. TreeMap class extends AbstractMap and implements NavigableMap, Cloneable and Serializable interfaces.

Features of TreeMap

Some of the features of the TreeMap in Java which are discussed in this post are as follows-

  1. In TreeMap elements are sorted by keys.
  2. In TreeMap values may be duplicate but a key has to be unique.
  3. TreeMap doesn’t permit null keys, null values are permitted though.
  4. TreeMap in Java is not thread safe.
  5. The iterators returned by all of TreeMap’s “collection view methods” are fail-fast. Which means, 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 throws a ConcurrentModificationException.

Java TreeMap constructors

  • TreeMap()– Constructs a new, empty tree map, using the natural ordering of its keys.
  • TreeMap(Comparator<? super K> comparator)– Constructs a new, empty tree map, ordered according to the given comparator.
  • TreeMap(Map<? extends K,? extends V> m)– Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys.
  • TreeMap(SortedMap<K,? extends V> m)– Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map.

Java example creating a TreeMap

Let’s see an example where a TreeMap is created and elements inserted in the TreeMap. We’ll display those values to see the sorted ordering.

Output

From the output you can see that the elements are sorted on keys. Since natural ordering for Integer is ascending that is why keys are sorted in ascending order.

Key 1345 is inserted twice, since key has to be unique that is why value is overwritten for the same key.

In TreeMap null keys are not allowed

We can check that TreeMap doesn’t allow null as key by trying to add null as key in the TreeMap. It should throw NullPointerExpcetion.

Output

Changing the sort order in TreeMap

If you want to change the sort order in TreeMap then you will have to provide a Comparator. In the previous example if you want keys to be sorted in descending order then you can do it as follows.

Output

Methods in TreeMap class

List of some of the methods in TreeMap class in Java.

  • ceilingEntry(K key)– Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
  • ceilingKey(K key)– Returns the least key greater than or equal to the given key, or null if there is no such key.
  • clear()– Removes all of the mappings from this map.
  • containsKey(Object key)– Returns true if this map contains a mapping for the specified key.
  • containsValue(Object value)– Returns true if this map maps one or more keys to the specified value.
  • floorEntry(K key)– Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
  • floorKey(K key)– Returns the greatest key less than or equal to the given key, or null if there is no such key.
  • get(Object key)– Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
  • keySet()– Returns a Set view of the keys contained in this map.
  • remove(Object key)– Removes the mapping for this key from this TreeMap if present.
  • size()– Returns the number of key-value mappings in this map.
  • subMap(K fromKey, K toKey)– Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
  • tailMap(K fromKey)– Returns a view of the portion of this map whose keys are greater than or equal to fromKey.

TreeMap implementation is not synchronized

TreeMap in Java is not thread safe as it is not synchronized. If multiple threads access a TreeMap concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. You can wrap your TreeMap using the Collections.synchronizedSortedMap method.

Java TreeMap iterator

You can’t directly use an iterator with Map. You will have to get the collection view of the Map and then iterate it. The iterators returned by TreeMap’s collection view methods are fail-fast. If the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator throws a ConcurrentModificationException.
Iterating TreeMap Java example

Output

That’s all for the topic TreeMap in Java – The Sorted Map. If something is missing or you have something to share about the topic please write a comment.


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.