1. Introduction

In this example we will see how and when to use the JavaTreemap classjava.util.TreeMap. ATreeMap is a Red-Black tree basedNavigableMap implementation which has log(n) time cost for the basic operations: add, remove, and contains.

ATreeMap guarantees that the elements inserted remains sorted on the order of keys. The elements are ordered using the natural ordering of the keys, or by aComparator typically provided at the sorted map creation time. ATreeMap is typically used when, in a map, we want to keep the elements sorted all times by the keys. The keys could also be custom objects defined withcomparable/comparator to decide the attribute responsible for sorting.

As the diagram showing,TreeMap implementsMap,MavigableMap, andSortedMap interfaces. I will demonstrate commonly usedTreeMap constructors and methods.

2. Technologies Used

The example code in this article was built and run using:

• Java 11
• Maven 3.3.9
• Eclipse Oxygen
• Junit 4.12

3. Maven Project

In this step, I will create a Maven project.

3.1 Dependencies

AddJunit library to thepom.xml.

pom.xml

<project xmlns="http://maven.apache.org/POM/4.0.0"xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"><modelVersion>4.0.0</modelVersion><groupId>jcg.zheng.demo</groupId><artifactId>java-treemap-demo</artifactId><version>0.0.1-SNAPSHOT</version><build><sourceDirectory>src</sourceDirectory><plugins><plugin><artifactId>maven-compiler-plugin</artifactId><version>3.8.0</version><configuration><release>11</release></configuration></plugin></plugins></build><dependencies><dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.12</version></dependency></dependencies></project>

3.2 User

In this step, I will create aUser class which implementsComparable. It hasfirstName,lastName, andsalary data members. ThecompareTo method is based on thefirstName andlastName.

User.java

package jcg.zheng.demo.data;import java.util.Comparator;public class User implements Comparable<User> {private String firstName;private String lastName;private int salary;public User(String firstName, String lastName, int salary) {super();this.firstName = firstName;this.lastName = lastName;this.salary = salary;}@Overridepublic int compareTo(User o) {return Comparator.comparing(User::getFirstName).thenComparing(User::getLastName).compare(this, o);}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;User other = (User) obj;if (firstName == null) {if (other.firstName != null)return false;} else if (!firstName.equals(other.firstName))return false;if (lastName == null) {if (other.lastName != null)return false;} else if (!lastName.equals(other.lastName))return false;return true;}public String getFirstName() {return firstName;}public String getLastName() {return lastName;}public int getSalary() {return salary;}@Overridepublic int hashCode() {final int prime = 31;int result = 1;result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());return result;}public void setFirstName(String firstName) {this.firstName = firstName;}public void setLastName(String lastName) {this.lastName = lastName;}public void setSalary(int salary) {this.salary = salary;}@Overridepublic String toString() {return firstName + " " + lastName + " " + salary;}}

3.3 UserSalaryComparator

In this step, I will create aUserSalaryComparator which implements theComparator interface. Thecompare method is based on the user’s salary.

UserSalaryComparator.java

package jcg.zheng.demo.data;import java.util.Comparator;public class UserSalaryComparator implements Comparator<User> {@Overridepublic int compare(User o1, User o2) {return Comparator.comparing(User::getSalary).compare(o1, o2);}}

3.4 PrintService

TreeMap has the several methods to retrieve the elements:

• Set<Map.Entry<K,​V>> entrySet() – returns aSet view of the mappings contained in this map.
• default void forEach ​(BiConsumer<? super K,​? super V> action) – performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
• Set<K> keySet() – returns aSet view of the keys contained in this map.
• Collection<V> values() – returns aCollection view of the values contained in this map.

In this step, I will create aPrintService which prints out the TreeMap’s elements viaentrySet,forEach,keySet, andvalues methods.

PrintService.java

package jcg.zheng.demo.treemap;import java.util.Map;import java.util.Set;import java.util.Map.Entry;import java.util.function.BiConsumer;import jcg.zheng.demo.data.User;public class PrintService {public void print(Map<Integer, String> integerMap) {Set<Integer> keys = integerMap.keySet();keys.forEach(k -> {System.out.println("k=" + k + ", v=" + integerMap.get(k));});}public void printIntegerTreeMap_forEach(Map<Integer, String> integerMap) {BiConsumer<Integer, String> action = (k, v) -> System.out.println("key=" + k + ",value=" + v);integerMap.forEach(action);}public void printIntergerTreeMap_values(Map<Integer, String> integerMap) {integerMap.values().forEach(name -> {System.out.println(name);});}public void printUserTreeMap_entrySet(Map<User, String> userMap) {Set<Entry<User, String>> mapSet = userMap.entrySet();for (Entry<User, String> entry : mapSet) {System.out.print("key=" + entry.getKey());System.out.println(", value=" + entry.getValue());}}}

4. Junit Test Classes

4.1 MapTestUtil

TreeMap extends from theAbstractMap class. I will demonstrate the common used methods fromMap in a Junit test class.

In this step, I will create aMapTestUtil which has three methods:

• add4Elements(Map) – It adds 4 elements to map with theput method, checks the map’s size with thesize method, retrieves the value based on the key with theget method, and check the key with thecontainsKey method.
• removeElements – it removes and replaces an element.
• add4Users(Map) – it demonstrates theput method for a new element,get method to return an element,containsKey to check if the map has the given key or not.

MapTestUtil.java

package jcg.zheng.demo;import static org.junit.Assert.assertEquals;import static org.junit.Assert.assertNull;import static org.junit.Assert.assertTrue;import java.util.Iterator;import java.util.Map;import java.util.Set;import jcg.zheng.demo.data.User;public class MapTestUtil {private static final int NOT_EXIST_KEY = 5;private static final int KEY_11 = 11;private static final String ABC = "ABC";private static final String DEFAULT_VALUE = "defaultValue";private static final String MARY_ZHENG = "Mary Zheng";private static final String ZHENG = "Zheng";private static final String MARY = "Mary";public void add4Elements(final Map<Integer, String> integerMap) {// no duplicate in a setintegerMap.put(KEY_11, ABC);int mapSize = integerMap.size();integerMap.put(KEY_11, ABC);assertEquals(mapSize, integerMap.size());assertEquals(ABC, integerMap.get(KEY_11));assertTrue(integerMap.containsKey(KEY_11));assertTrue(integerMap.containsValue(ABC));assertNull(integerMap.get(NOT_EXIST_KEY));assertEquals(DEFAULT_VALUE, integerMap.getOrDefault(NOT_EXIST_KEY, DEFAULT_VALUE));integerMap.put(22, "JCG");integerMap.put(4, "123");integerMap.put(3, "XYZ");}public void removeElements(final Map<Integer, String> integerMap) {integerMap.remove(KEY_11);integerMap.replace(2, "JCG", MARY);}public void add4Users(final Map<User, String> userMap) {User user1 = new User(MARY, ZHENG, 15);userMap.put(user1, MARY_ZHENG);assertEquals(1, userMap.size());Set<User> keySet = userMap.keySet();Iterator<User> it = keySet.iterator();User key1 = it.next();assertTrue(user1.equals(key1));assertEquals(MARY_ZHENG, userMap.get(key1));assertEquals(MARY_ZHENG, userMap.get(user1));assertTrue(userMap.containsKey(user1));assertTrue(userMap.containsValue(MARY_ZHENG));assertEquals(MARY_ZHENG, userMap.get(user1));assertNull(userMap.get(new User("Tom", ZHENG, 25)));assertEquals(DEFAULT_VALUE, userMap.getOrDefault(new User("Tom", ZHENG, 25), DEFAULT_VALUE));userMap.put(new User("Eve", "Smith", 12), "Name1");userMap.put(new User("Adm", "Johnson", 22), "Name3");userMap.put(new User("Bob", "Zheng", 1), "Name4");}}

4.2 TreeMapTest

TreeMap implements theNavigableMap interface. In this step, I will create aTreeMapTest to demonstrate the commonly used constructors and methods.

• setup – It creates fourTreeMap instances. Some created with the default constructor, others created with a specialComparator.
• test_integer_key – it adds elements, find the first entry, last entry, returns a portion of map, etc.
• test_integer_key_reversOrder – it creates aTreeMap from a sorted map.
• test_KeyIsComparabale – it creates aTreeMap with theUser class. TheUser class implementsComparable and is sorted on the basis offirstName andlastName.
• test_KeyIsComparator – It creates aTreeMap from a sorted map and maintains the same order – based on the user’s salary. .
• will_throw_NullPointerException – it demonstrates theput method will throw aNullPointerException if the key isnull.

TreeMapTest.java

package jcg.zheng.demo;import static org.junit.Assert.assertEquals;import static org.junit.Assert.assertFalse;import static org.junit.Assert.assertTrue;import java.util.Collections;import java.util.Map.Entry;import java.util.SortedMap;import java.util.TreeMap;import org.junit.After;import org.junit.Before;import org.junit.Test;import jcg.zheng.demo.data.User;import jcg.zheng.demo.data.UserSalaryComparator;import jcg.zheng.demo.treemap.PrintService;public class TreeMapTest {private static final String DEFAULT_ASCENDING_ORDER_OF_KEY = "** Default ascending order based on the Key value **";private TreeMap<Integer, String> intTreeMapWithDefaultOrder;private TreeMap<Integer, String> intTreeMapWithReverseOrder;private TreeMap<User, String> userTreeMapWithDefaultOrder;private TreeMap<User, String> userTreeMapOrderBySalary;private MapTestUtil testUtil = new MapTestUtil();private PrintService mapService = new PrintService();@Beforepublic void setup() {intTreeMapWithDefaultOrder = new TreeMap<>();intTreeMapWithReverseOrder = new TreeMap<>(Collections.reverseOrder());userTreeMapWithDefaultOrder = new TreeMap<>();userTreeMapOrderBySalary = new TreeMap<>(new UserSalaryComparator());}@Afterpublic void test_isEmpty() {intTreeMapWithDefaultOrder.clear();intTreeMapWithReverseOrder.clear();userTreeMapWithDefaultOrder.clear();userTreeMapOrderBySalary.clear();assertTrue(intTreeMapWithDefaultOrder.isEmpty());assertTrue(intTreeMapWithReverseOrder.isEmpty());assertTrue(userTreeMapWithDefaultOrder.isEmpty());assertTrue(userTreeMapOrderBySalary.isEmpty());}@Testpublic void test_integer_key() {testUtil.add4Elements(intTreeMapWithDefaultOrder);System.out.println(DEFAULT_ASCENDING_ORDER_OF_KEY);mapService.printIntegerTreeMap_forEach(intTreeMapWithDefaultOrder);Entry<Integer, String> firstEntry = intTreeMapWithDefaultOrder.firstEntry();System.out.println("* firstEntry = " + firstEntry.toString());Integer firstKey = intTreeMapWithDefaultOrder.firstKey();System.out.println(" firstKey=" + firstKey.intValue());Entry<Integer, String> lastEntry = intTreeMapWithDefaultOrder.lastEntry();System.out.println("* lastEntry.key= " + lastEntry.getKey().intValue());// will only print out {3=XXX} as it the only element whose key value < 10SortedMap<Integer, String> headMap = intTreeMapWithDefaultOrder.headMap(10);System.out.println("** headMap key < 10 in default order ***");mapService.printIntegerTreeMap_forEach(headMap);// will only print out {11=ABC} as it the only element whose key value > 3SortedMap<Integer, String> tailMap = intTreeMapWithDefaultOrder.tailMap(10);System.out.println("** tailMap key > 10 in default order ***");mapService.printIntegerTreeMap_forEach(tailMap);Entry<Integer, String> firstPulled = intTreeMapWithDefaultOrder.pollFirstEntry();System.out.println(" firstPulled= " + firstPulled.toString());assertEquals(3, intTreeMapWithDefaultOrder.size());mapService.print(intTreeMapWithDefaultOrder);mapService.printIntergerTreeMap_values(intTreeMapWithDefaultOrder);testUtil.removeElements(intTreeMapWithDefaultOrder);}@Test(expected = NullPointerException.class)public void will_throw_NullPointerException() {intTreeMapWithDefaultOrder.put(null, "test");}@Testpublic void test_integer_key_ReversOrder() {assertTrue(intTreeMapWithReverseOrder.isEmpty());testUtil.add4Elements(intTreeMapWithReverseOrder);System.out.println(" *** integerTreeMapWithReverseOrder in ReverseOrder ** ");mapService.printIntegerTreeMap_forEach(intTreeMapWithReverseOrder);TreeMap<Integer, String> createdFromSortedMap = new TreeMap<>(intTreeMapWithReverseOrder);System.out.println(" *** createdFromSortedMap in ReverseOrder ** ");mapService.printIntegerTreeMap_forEach(createdFromSortedMap);}@Testpublic void test_Key_Comparable() {assertTrue(userTreeMapWithDefaultOrder.isEmpty());testUtil.add4Users(userTreeMapWithDefaultOrder);System.out.println(" *** Order based on User's compareTo() ***");mapService.printUserTreeMap_entrySet(userTreeMapWithDefaultOrder);TreeMap<User, String> createdFromSortedMap = new TreeMap<>(userTreeMapWithDefaultOrder);assertEquals(userTreeMapWithDefaultOrder.size(), createdFromSortedMap.size());System.out.println("***** createdFromSortedMap order from natual order *****");mapService.printUserTreeMap_entrySet(createdFromSortedMap);}@Testpublic void test_Key_Comparator() {assertTrue(userTreeMapOrderBySalary.isEmpty());testUtil.add4Users(userTreeMapOrderBySalary);System.out.println(" *** Ordered based on User's Salary() ***");mapService.printUserTreeMap_entrySet(userTreeMapOrderBySalary);TreeMap<User, String> createdFromSortedMap = new TreeMap<>(userTreeMapOrderBySalary);assertEquals(userTreeMapOrderBySalary.size(), createdFromSortedMap.size());System.out.println("***** createdFromSortedMap order by Salary *****");mapService.printUserTreeMap_entrySet(createdFromSortedMap);assertTrue(createdFromSortedMap.equals(userTreeMapOrderBySalary));createdFromSortedMap.put(new User("JCG", "mZheng", 11), "My Name5");assertFalse(createdFromSortedMap.equals(userTreeMapOrderBySalary));Entry<User, String> lastEntry = createdFromSortedMap.lastEntry();System.out.println("LastEntry = " + lastEntry.toString());Entry<User, String> ceilingEntry = createdFromSortedMap.ceilingEntry(lastEntry.getKey());System.out.println("ceilingEntry = " + ceilingEntry.toString());}}

Execute mvn test -Dtest=TreeMapTest and capture output.

OUTPUT

------------------------------------------------------- T E S T S-------------------------------------------------------Running jcg.zheng.demo.TreeMapTest *** Order based on User's compareTo() ***key=Adm Johnson 22, value=Name3key=Bob Zheng 1, value=Name4key=Eve Smith 12, value=Name1key=Mary Zheng 15, value=Mary Zheng***** createdFromSortedMap order from natual order *****key=Adm Johnson 22, value=Name3key=Bob Zheng 1, value=Name4key=Eve Smith 12, value=Name1key=Mary Zheng 15, value=Mary Zheng *** Ordered based on User's Salary() ***key=Bob Zheng 1, value=Name4key=Eve Smith 12, value=Name1key=Mary Zheng 15, value=Mary Zhengkey=Adm Johnson 22, value=Name3***** createdFromSortedMap order by Salary *****key=Bob Zheng 1, value=Name4key=Eve Smith 12, value=Name1key=Mary Zheng 15, value=Mary Zhengkey=Adm Johnson 22, value=Name3LastEntry = Adm Johnson 22=Name3ceilingEntry = Adm Johnson 22=Name3 *** integerTreeMapWithReverseOrder in ReverseOrder **key=22,value=JCGkey=11,value=ABCkey=4,value=123key=3,value=XYZ *** createdFromSortedMap in ReverseOrder **key=22,value=JCGkey=11,value=ABCkey=4,value=123key=3,value=XYZ** Default ascending order based on the Key value **key=3,value=XYZkey=4,value=123key=11,value=ABCkey=22,value=JCG* firstEntry = 3=XYZ firstKey=3* lastEntry.key= 22** headMap key < 10 in default order ***key=3,value=XYZkey=4,value=123** tailMap key > 10 in default order ***key=11,value=ABCkey=22,value=JCG firstPulled= 3=XYZk=4, v=123k=11, v=ABCk=22, v=JCG123ABCJCGTests run: 5, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.349 secResults :Tests run: 5, Failures: 0, Errors: 0, Skipped: 0[INFO] ------------------------------------------------------------------------[INFO] BUILD SUCCESS[INFO] ------------------------------------------------------------------------[INFO] Total time:  13.320 s[INFO] Finished at: 2019-08-22T20:42:42-05:00[INFO] ------------------------------------------------------------------------C:\MaryZheng\Workspaces\jdk12\java-treemap-demo>

4.3 Thread-Safe TreeMap

TreeMap is not thread-safe. Java Collection framework provides theCollections.synchronizedSortedMap method to ensure thread-safe.

In this step, I will create aThreadSafe_TreeMapTest which runs 1000 threads to put the element into aTreeMap object. We will get 1000 elements into the synchronized map for sure. However, it may or may not get 1000 elements into a normalTreeMap.

ThreadSafeTreeMapTest.java

package jcg.zheng.demo;import static org.junit.Assert.assertEquals;import java.util.Collections;import java.util.Random;import java.util.SortedMap;import java.util.TreeMap;import java.util.concurrent.ExecutorService;import java.util.concurrent.Executors;import java.util.concurrent.TimeUnit;import org.junit.After;import org.junit.Before;import org.junit.Test;public class ThreadSafeTreeMapTest extends MapTestUtil {private static final int COUNT = 100;SortedMap<Integer, String> mapObj;Random randon = new Random();private ExecutorService executor;@Beforepublic void setup() {executor = Executors.newFixedThreadPool(5);}@Afterpublic void finish() {try {executor.awaitTermination(10l, TimeUnit.SECONDS);} catch (Exception e) {// ignore}assertEquals(COUNT, mapObj.size());}@Testpublic void synchronizedSortedMap_test() {mapObj = Collections.synchronizedSortedMap(new TreeMap<Integer, String>());for (int i = 0; i < COUNT; i++) {executor.submit(this::addOne);}}public void addOne() {mapObj.put(randon.nextInt(), "Mary");}}

Now, execute the Junit test and capture the output here.

OUTPUT

------------------------------------------------------- T E S T S-------------------------------------------------------Running jcg.zheng.demo.ThreadSafeTreeMapTestTests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 10.124 secResults :Tests run: 1, Failures: 0, Errors: 0, Skipped: 0[INFO] ------------------------------------------------------------------------[INFO] BUILD SUCCESS[INFO] ------------------------------------------------------------------------[INFO] Total time:  20.067 s[INFO] Finished at: 2019-08-22T20:45:30-05:00[INFO] ------------------------------------------------------------------------C:\MaryZheng\Workspaces\jdk12\java-treemap-demo>

5. Summary

In this example, I demonstrated how to create aTreeMap and how to sort its elements. I also demonstrated how to find, add, retrieve, and iterate the map elements.

Important thing to note is that the ordering maintained by atreeMap must be consistent with equals if this sorted map is to correctly implement theMap interface.

6. Download the Source Code

In this example we saw various ways of using aTreeMap.

Last updated on Aug 23, 2019

Do you want to know how to develop your skillset to become aJava Rockstar?

Subscribe to our newsletter to start Rockingright now!

To get you started we give you our best selling eBooks forFREE!

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

and many more ....

I agree to theTerms andPrivacy Policy

Sign up

Thank you!

We will contact you soon.