Java TreeMap – TreeMap in Java

Filed Under: Java

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

Java TreeMap

Java TreeMap, TreeMap in Java, 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.


package com.journaldev.java;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class JavaTreeMapExample {

	public static void main(String[] args) {
		
		Map<Integer,String> map = new TreeMap<>();
		
		map.put(10, "10");
		map.put(1, "1");
		map.put(5, "5");
		
		System.out.println(map);
		
		map = new TreeMap<>(new Comparator<Integer>() {

			@Override
			public int compare(Integer x, Integer y) {
				return (x > y) ? -1 : ((x == y) ? 0 : 1);
			}
			
		});
		map.put(10, "10");
		map.put(1, "1");
		map.put(5, "5");
		System.out.println(map);

	}

}

It will produce below output.


{1=1, 5=5, 10=10}
{10=10, 5=5, 1=1}

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.


map = new TreeMap<>((x,y) -> {return (x > y) ? -1 : ((x == y) ? 0 : 1);});

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.


package com.journaldev.java;

import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class JavaTreeMapNavigationExamples {

	public static void main(String[] args) {
		
		//we have to define object as TreeMap to use NavigableMap functions
		TreeMap<Integer,String> map = new TreeMap<>();
		for(int i=0;i<10;i++) {
			map.put(i, i+"");
		}
		
		System.out.println(map);
		
		//find id closest to 5, lower and higher
		Entry<Integer,String> entry = map.lowerEntry(5);
		System.out.println("Closest Lower key than 5 is "+entry);
		entry = map.higherEntry(5);
		System.out.println("Closest Higher key than 5 is "+entry);
		
		System.out.println("Closest Lower key than 4 is "+map.lowerKey(4));
		
		entry = map.floorEntry(5);
		System.out.println("Closest floor entry than 5 is "+entry);
		
		entry = map.ceilingEntry(4);
		System.out.println("Closest ceiling key than 4 is "+entry);
		
		entry = map.firstEntry();
		System.out.println("First Entry is "+entry);

		entry = map.lastEntry();
		System.out.println("Last Entry is "+entry);
		
		Map<Integer, String> reversedMap = map.descendingMap();
		System.out.println("Reversed Map: "+reversedMap);
		
		//poll and remove first, last entries
		entry = map.pollFirstEntry();
		System.out.println("First Entry is "+entry);
		entry = map.pollLastEntry();
		System.out.println("Last Entry is "+entry);
		System.out.println("Updated Map: "+map);
		
		//submap example
		Map<Integer, String> subMap = map.subMap(2, true, 6, true);
		System.out.println("Submap: "+subMap);
		
		subMap = map.headMap(5, true);
		System.out.println("HeadMap: "+subMap);

		subMap = map.tailMap(5, true);
		System.out.println("TailMap: "+subMap);
	}

}

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


{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
Closest Lower key than 5 is 4=4
Closest Higher key than 5 is 6=6
Closest Lower key than 4 is 3
Closest floor entry than 5 is 5=5
Closest ceiling key than 4 is 4=4
First Entry is 0=0
Last Entry is 9=9
Reversed Map: {9=9, 8=8, 7=7, 6=6, 5=5, 4=4, 3=3, 2=2, 1=1, 0=0}
First Entry is 0=0
Last Entry is 9=9
Updated Map: {1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8}
Submap: {2=2, 3=3, 4=4, 5=5, 6=6}
HeadMap: {1=1, 2=2, 3=3, 4=4, 5=5}
TailMap: {5=5, 6=6, 7=7, 8=8}

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

Comments

  1. Ganesh Bhat says:

    Passing comparator to get entries in reverse order is discouraged, instead use Collections.reveseOrder().
    Good tutorial, I would have liked it more if you explained internals like Red-Black tree and and why not perfect Balanced tree

  2. Shravan Arora says:

    Hi
    If hashing isnt used in Treemaps, why do we need to override hashCode and equals methods, as mentioned in the point – “TreeMap entries are sorted in the natural ordering of it’s 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 provides implementation of equals and hashcode methods and Comparable interface for natural ordering.”

    1. Ganesh Bhat says:

      Good point, one need not implement equals and hashCode when adding entries to TreeMap, treeMap uses compare method to find out place for its insertion.

      Code can be seen here – http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/TreeMap.java

      1. Pankaj says:

        Yes, you are right. I have corrected the post.

  3. mohan says:

    I think Map interface doesn’t implement iterable. Can you re-check this and correct 5th point?.

    1. Pankaj says:

      Sorry for the confusion, I meant the methods returning iterator such as keySet(), values() etc. I have updated the post to make it more clear.

  4. Nishant says:

    Hi,

    Great article.
    Suggestion: it would have been better if you had explained, red and black tree along with it.

    Keep up the good work.

    Regards,
    Nishant

  5. طراحی نما says:

    I will always remember how you helped me to get this wonderful opportunity

  6. Anurag Singh says:

    nice tutorial about java treemap .
    great post
    thanks

Leave a Reply

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

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages