Java Treemap – java.util.TreeMap Example

1. Introduction

In this example we will see how and when to use the Java Treemap class java.util.TreeMap. A TreeMap is a Red-Black tree based NavigableMap implementation which has log(n) time cost for the basic operations: add, remove, and contains.

A TreeMap 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 a Comparator typically provided at the sorted map creation time. A TreeMap 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 with comparable/comparator to decide the attribute responsible for sorting.

As the diagram showing, TreeMap implements Map, MavigableMap, and SortedMap interfaces. I will demonstrate commonly used TreeMap 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

Add Junit library to the pom.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 a User class which implements Comparable. It has firstName, lastName, and salary data members. The compareTo method is based on the firstName and lastName.

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;
	}

	@Override
	public int compareTo(User o) {
		return Comparator.comparing(User::getFirstName).thenComparing(User::getLastName).compare(this, o);
	}

	@Override
	public 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;
	}

	@Override
	public 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;
	}

	@Override
	public String toString() {
		return firstName + " " + lastName + " " + salary;
	}

}

3.3 UserSalaryComparator

In this step, I will create a UserSalaryComparator which implements the Comparator interface. The compare 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> {

	@Override
	public 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 a Set 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 a Set view of the keys contained in this map.
• Collection<V> values() – returns a Collection view of the values contained in this map.

In this step, I will create a PrintService which prints out the TreeMap’s elements via entrySet, forEach, keySet, and values 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 the AbstractMap class. I will demonstrate the common used methods from Map in a Junit test class.

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

• add4Elements(Map) – It adds 4 elements to map with the put method, checks the map’s size with the size method, retrieves the value based on the key with the get method, and check the key with the containsKey method.
• removeElements – it removes and replaces an element.
• add4Users(Map) – it demonstrates the put 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 set
		integerMap.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 the NavigableMap interface. In this step, I will create a TreeMapTest to demonstrate the commonly used constructors and methods.

• setup – It creates four TreeMap instances. Some created with the default constructor, others created with a special Comparator.
• test_integer_key – it adds elements, find the first entry, last entry, returns a portion of map, etc.
• test_integer_key_reversOrder – it creates a TreeMap from a sorted map.
• test_KeyIsComparabale – it creates a TreeMap with the User class. The User class implements Comparable and is sorted on the basis of firstName and lastName.
• test_KeyIsComparator – It creates a TreeMap from a sorted map and maintains the same order – based on the user’s salary. .
• will_throw_NullPointerException – it demonstrates the put method will throw a NullPointerException if the key is null.

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();

	@Before
	public void setup() {
		intTreeMapWithDefaultOrder = new TreeMap<>();
		intTreeMapWithReverseOrder = new TreeMap<>(Collections.reverseOrder());

		userTreeMapWithDefaultOrder = new TreeMap<>();
		userTreeMapOrderBySalary = new TreeMap<>(new UserSalaryComparator());
	}

	@After
	public void test_isEmpty() {
		intTreeMapWithDefaultOrder.clear();
		intTreeMapWithReverseOrder.clear();
		userTreeMapWithDefaultOrder.clear();
		userTreeMapOrderBySalary.clear();
		
		assertTrue(intTreeMapWithDefaultOrder.isEmpty());
		assertTrue(intTreeMapWithReverseOrder.isEmpty());
		assertTrue(userTreeMapWithDefaultOrder.isEmpty());
		assertTrue(userTreeMapOrderBySalary.isEmpty());
	}

	@Test
	public 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 < 10
		SortedMap<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 > 3
		SortedMap<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");
	}

	@Test
	public 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);
	}

	@Test
	public 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);
	}

	@Test
	public 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=Name3
key=Bob Zheng 1, value=Name4
key=Eve Smith 12, value=Name1
key=Mary Zheng 15, value=Mary Zheng
***** createdFromSortedMap order from natual order *****
key=Adm Johnson 22, value=Name3
key=Bob Zheng 1, value=Name4
key=Eve Smith 12, value=Name1
key=Mary Zheng 15, value=Mary Zheng
 *** Ordered based on User's Salary() ***
key=Bob Zheng 1, value=Name4
key=Eve Smith 12, value=Name1
key=Mary Zheng 15, value=Mary Zheng
key=Adm Johnson 22, value=Name3
***** createdFromSortedMap order by Salary *****
key=Bob Zheng 1, value=Name4
key=Eve Smith 12, value=Name1
key=Mary Zheng 15, value=Mary Zheng
key=Adm Johnson 22, value=Name3
LastEntry = Adm Johnson 22=Name3
ceilingEntry = Adm Johnson 22=Name3
 *** integerTreeMapWithReverseOrder in ReverseOrder **
key=22,value=JCG
key=11,value=ABC
key=4,value=123
key=3,value=XYZ
 *** createdFromSortedMap in ReverseOrder **
key=22,value=JCG
key=11,value=ABC
key=4,value=123
key=3,value=XYZ
** Default ascending order based on the Key value **
key=3,value=XYZ
key=4,value=123
key=11,value=ABC
key=22,value=JCG
* firstEntry = 3=XYZ
 firstKey=3
* lastEntry.key= 22
** headMap key < 10 in default order ***
key=3,value=XYZ
key=4,value=123
** tailMap key > 10 in default order ***
key=11,value=ABC
key=22,value=JCG
 firstPulled= 3=XYZ
k=4, v=123
k=11, v=ABC
k=22, v=JCG
123
ABC
JCG
Tests run: 5, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.349 sec

Results :

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 the Collections.synchronizedSortedMap method to ensure thread-safe.

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

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;

	@Before
	public void setup() {
		executor = Executors.newFixedThreadPool(5);
	}

	@After
	public void finish() {
		try {
			executor.awaitTermination(10l, TimeUnit.SECONDS);
		} catch (Exception e) {
			// ignore
		}
		assertEquals(COUNT, mapObj.size());

	}

	@Test
	public 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.ThreadSafeTreeMapTest
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 10.124 sec

Results :

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 a TreeMap 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 a treeMap must be consistent with equals if this sorted map is to correctly implement the Map interface.

6. Download the Source Code

In this example we saw various ways of using a TreeMap.

Last updated on Aug 23, 2019

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

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

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 the Terms and Privacy Policy

Sign up

Thank you!

We will contact you soon.