Besides the AbstractMap Class, Java’s TreeMap discreetly implements the Map interface and NavigableMap. Depending on which constructor is used, the map is sorted either by the natural ordering of its keys or by a Comparator specified at map creation time.
This is an effective method of sorting and storing key-value pairs. Regardless of the specified comparators, the treemap’s storage order must be consistent with equals, just like any other sorted map. The implementation of a treemap is presented as not synchronized because a map must be synchronized externally if it is used by multiple threads concurrently, and at least one of the threads modifies the map fundamentally.
Class declaration for TreeMap
Let’s look at the java.util.TreeMap class declaration.
public class TreeMap<Key,Value> extends AbstractMap<Key,Value> implements NavigableMap<Key,Value>, Cloneable, Serializable
Class parameters for TreeMap
Let’s look at the java.util.TreeMap class’s parameters.
- This map’s kind of keys is designated by the letter K.
- The type of mapped value is V.
TreeMap Characteristics
The following are some of the treemap’s key features:
- The Java Collections Framework includes this class.
- The class extends AbstractMap and implements Map interfaces such as NavigableMap and SortedMap.
- Because TreeMap (unlike Map) does not accept null keys, a NullPointerException is raised.
- On the other hand, multiple null values can be associated with separate keys.
- The entry pairs given by this class’s methods and views are snapshots of mappings taken when they were created.
- The Entry.setValue method is not supported.
Now it’s time to talk about Synchronized TreeMap. The TreeMap implementation is not synchronized. This means that if multiple threads visit a tree set simultaneously and at least one of the updates it, the set must be externally synchronized. The Collections.synchronizedSortedMap method is commonly used to accomplish this. This should be done at the creation time to avoid unintentional unsynchronized access to the set. This can be accomplished by:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
You’re probably wondering how the TreeMap works on the inside.
The methods in a TreeMap return an Iterator that is fail-safe for getting keyset and values. ConcurrentModificationException will be thrown for any concurrent modification. The data structure of a TreeMap is a red-black tree. Each node in the tree has the following properties:
3 variables (key=Key, value=Value, boolean color=Color) 3 references (Entry lft = Left, Entry rgt = Right, Entry parent = Parent)
TreeMap constructors
When creating a TreeMap, we must first create a TreeMap object. The TreeMap class contains several constructors that allow the TreeMap to be created. The constructors available in this class are as follows:
- TreeMap()
- TreeMap(Comparator comp)
- TreeMap(Map M)
- TreeMap(SortedMap sm)
Let’s go over each one individually before implementing each constructor:
The first constructor: TreeMap
This constructor creates an empty treemap that will be sorted according to its keys’ natural order. Example :
// Program for demonstrating the TreeMap using the Default Constructor
// Importing required classes
import java.util.*;
import java.util.concurrent.*;
// TreeMapImplementation is the Main class
public class Codeunderscored {
// Method one showing the TreeMap constructor
static void CodeFirstConstructor()
{
// Creation of an empty TreeMap
TreeMap<Integer, String> treeMap
= new TreeMap<Integer, String>();
// Mapping string values to int keys
// using put() method
treeMap.put(1, "Code");
treeMap.put(18, "Underscored");
treeMap.put(16, "Coding");
treeMap.put(34, "Java");
treeMap.put(12, "Extravaganza");
// how to print the TreeMap elements
System.out.println(" The TreeMap is as follows: " + treeMap);
}
// Method Two: The primary driver method
public static void main(String[] args)
{
System.out.println("TreeMap using the "+ "TreeMap() constructor:\n");
// Calling constructor
CodeFirstConstructor();
}
}
The second Constructor: TreeMap(Comparator comp)
This constructor is responsible for creating an empty TreeMap object with nodes that require an external sorting order specification.
// Program for demonstrating TreeMap using the Comparator Constructor
//First, import the needed classes
import java.util.*;
import java.util.concurrent.*;
// Class 1: This is the helper class for CodeStudent
class CodeStudent {
// CodeStudent's attributes
int c_rollno;
String c_name, c_address;
// Constructor
public CodeStudent(int c_rollno, String c_name, String c_address)
{
// This keyword refers to current object itself
this.c_rollno = c_rollno;
this.c_name = c_name;
this.c_address = c_address;
}
// class's method for printing CodeStudent details
public String toString()
{
return this.c_rollno + " " + this.c_name + " "
+ this.c_address;
}
}
// Class Two: This is the helper class for implementing a Comparator
class CodeSortByRoll implements Comparator<CodeStudent> {
// responsible for sorting the student's roll number in ascending order
public int compare(CodeStudent aVar, CodeStudent bVar)
{
return aVar.c_rollno - bVar.c_rollno;
}
}
// Class Three: This is the Main class
public class Code {
// here, we call the constructor inside main()
static void CodeSecondConstructor()
{
// Creation of an empty TreeMap
TreeMap<CodeStudent, Integer> treeMap
= new TreeMap<CodeStudent, Integer>(
new CodeSortByRoll());
// Mapping string values to int keys
treeMap.put(new CodeStudent(1, "Joy", "Manchester"), 2);
treeMap.put(new CodeStudent(2, "Green", "LA"), 3);
treeMap.put(new CodeStudent(3, "Tyson", "New York"), 1);
// Print the TreeMap elements
System.out.println(" The TreeMap is: " + treeMap);
}
// The driver;s main method
public static void main(String[] args)
{
System.out.println("The TreeMap using "
+ "TreeMap(Comparator)"
+ " constructor:\n");
CodeSecondConstructor();
}
}
The third Constructor: TreeMap (Map M)
This constructor is used to populate a TreeMap with entries from a specified map ‘M’, which will be sorted following the keys’ natural order.
Example
// Program for illustrating the TreeMap through the Default Constructor
//First, Import the required classes
import java.util.*;
import java.util.concurrent.*;
// This is the Main class
public class CodeTreeMapImplementation {
// Method 1: illustrates the constructor<Map>
static void CodeThirdConstructor()
{
// Creation of an empty HashMap
Map<Integer, String> hashMap
= new HashMap<Integer, String>();
// using the put() method to Map string values to respective int keys
hashMap.put(8, "Code");
hashMap.put(3, "Underscored");
hashMap.put(7, "Coding");
hashMap.put(11, "Challenge");
hashMap.put(5, "2022");
// Creation of the TreeMap by using the Map
TreeMap<Integer, String> treeMap
= new TreeMap<Integer, String>(hashMap);
// Printing the TreeMap elements
System.out.println("The TreeMap is: " + treeMap);
}
// Method 2: This is the driver's main method
public static void main(String[] args)
{
System.out.println(" The TreeMap using the "
+ "TreeMap(Map)"
+ " constructor:\n");
CodeThirdConstructor();
}
}
The fourth Constructor: TreeMap(SortedMap sm)
This constructor fills a TreeMap with the items from the specified sorted map, stored in the same order as the sorted map.
// Program for illustrating the TreeMap throughout the SortedMap Constructor
// First, Import the needed classes
import java.util.*;
import java.util.concurrent.*;
// TreeMapImplementation- Main class
public class Codeunderscored {
// Method for showing TreeMap(SortedMap) constructor
static void CodeFourthConstructor()
{
// Creating a SortedMap
SortedMap<Integer, String> sortedMap
= new ConcurrentSkipListMap<Integer, String>();
// using the put() method for mapping values of type string to int keys
sortedMap.put(8, "Code");
sortedMap.put(3, "Underscored");
sortedMap.put(7, "Coding");
sortedMap.put(11, "Challenge");
sortedMap.put(5, "2022");
// Creation of the TreeMap using the SortedMap
TreeMap<Integer, String> treeMap
= new TreeMap<Integer, String>(sortedMap);
// Printing of the elements of the TreeMap
System.out.println("The TreeMap is: " + treeMap);
}
// Method 2: The driver's Main method
public static void main(String[] args)
{
System.out.println("This is the TreeMap using the: "
+ "TreeMap(SortedMap)"
+ " constructor:\n");
CodeFourthConstructor();
}
}
The TreeMap Class’s methods
clear()
The method clears the map and removes all mappings from the TreeMap.
clone()
A shallow copy of this TreeMap is returned by this method.
containsKey(Object key)
If this map has a mapping for the supplied key, it returns true.
containsValue(Object value)
If this map is responsible for mapping one or more keys to the supplied value, it returns true.
entrySet()
This method is responsible for returning a set view of the mappings in this map.
firstKey()
Returns the current sorted map’s first (lowest) key.
get(Object key)
Returns the value to which this map maps the supplied key.
headMap(Object key_value)
The method returns a view of the map section that is strictly less than the key_value parameter.
keySet()
The method returns a Set representation of the treemap’s keys.
lastKey()
Returns the current sorted map’s last (highest) key.
put(Object key, Object value)
A mapping is inserted into a map using this way.
putAll(Map map)
All mappings from the specified map are copied to this map.
remove(Object key)
If this TreeMap has a mapping for this key, it is removed.
size()
The number of key-value mappings in this map is returned.
subMap((K startKey, K endKey)
The method returns the map portion with keys ranging from startKey to endKey, inclusive and exclusive.
values()
This method is tasked with returning a collection view of the values in this map.
The following programs will show you how to create, insert, and navigate through the TreeMap implementation.
Example: Program for Illustrating the Operations in TreeMap
// TreeMap operations include: Creation, insertion, searching, and traversal
//First, importing the necessary classes
import java.util.*;
import java.util.concurrent.*;
// This is the class's main implementation of the TreeMap
public class Codeunderscored {
// Declaration of a TreeMap
static TreeMap<Integer, String> treeMap;
// Method One: Creation of a TreeMap
static void CodeCreate()
{
// Creating an empty TreeMap
treeMap = new TreeMap<Integer, String>();
// Display message only
System.out.println("TreeMap has been created successfully");
}
// Method Two: Inserting values in the TreeMap
static void CodeInsert()
{
// using put() method to map values of string type to int keys
treeMap.put(8, "Code");
treeMap.put(3, "Underscored");
treeMap.put(7, "Coding");
treeMap.put(11, "Challenge");
treeMap.put(5, "2022");
// Display message only
System.out.println("\nPrinting the Elements successfully"
+ " after initial insert to the TreeMap");
}
// Method three: / searching for a key in the givenTreeMap
static void CodeSearch(int key)
{
// looking for the key
System.out.println("\nThis is the key \"" + key
+ "\" present? "
+ treeMap.containsKey(key));
}
// Method Four: searching for value in the provided TreeMap
static void CodeSearch(String value)
{
// Checking for the value
System.out.println("\nThis is the value \"" + value
+ "\" present? "
+ treeMap.containsValue(value));
}
// Method Five: displaying elements in the provided TreeMap
static void CodeDisplay()
{
// showing the TreeMap
System.out.println("\nShowing the TreeMap:");
System.out.println("The TreeMap is: " + trerMap);
}
// Method Six: traversing through the TreeMap
static void CodeTraverse()
{
// showing message explicitly
System.out.println("\nTreeMap Traversal:");
for (Map.Entry<Integer, String> eVar :
treeMap.entrySet())
System.out.println(eVar.getKey() + " "
+ eVar.getValue());
}
// Method 7: This is the driver's Main method
public static void main(String[] args)
{
// Calling the above-defined methods inside the main()
// Creation of a TreeMap
CodeCreate();
// Insertion of values in the TreeMap
CodeInsert();
// searching for key "2022" in the provided TreeMap
CodeSearch(2022);
// Searching for the value "Coding" in the TreeMap
CodeSearch("Coding");
// Displaying the TreeMap's elements
CodeDisplay();
// TreeMap Traversal
CodeTraverse();
}
}
Using TreeMap to Perform Various Operations
It is now possible to limit the kind of object that can be put in the TreeMap thanks to the advent of Generics in Java 1.5. Let’s look at using the TreeMap to accomplish a few common operations.
Operation One: Adding Elements
The put() method can add an element to the TreeMap. In the TreeMap, however, the insertion order is not preserved. Internally, the keys are compared and sorted in ascending order for each element. The common methods for adding elements include:
- put() -Puts the provided key/value mapping (entry) into the map.
- PutAll() -Puts all the entries from a specified map into this map.
- PutIfAbsent() – If the supplied key is not present in the map, putIfAbsent() adds the specified key/value mapping to the map.
// Program for demonstrating the addition of Elements in TreeMap through the put() Method
// First, import the necessary classes
import java.util.*;
// This is the Main class
class Codeunderscored {
// This is the driver's Main method
public static void main(String args[])
{
// Initialization of a given TreeMap by default
TreeMap treeMap = new TreeMap();
// using the put() method to Insert elements in TreeMap
treeMap.put(3, "Code");
treeMap.put(2, "Underscored");
treeMap.put(1, "Coding");
// Initializing a TreeMap through use of Generics
TreeMap<Integer, String> treeMapTwo
= new TreeMap<Integer, String>();
// using the method, "put()" to insert elements in the TreeMap given
treeMapTwo.put(new Integer(3), "Code");
treeMapTwo.put(new Integer(2), "Underscored");
treeMapTwo.put(new Integer(1), "Coding");
// Printing the elements of both TreeMaps
// Tree Map One
System.out.println(treeMap);
// Tree Map Two
System.out.println(treeMapTwo);
}
}
import java.util.TreeMap;
class CodeAdd {
public static void main(String[] args) {
//Making an even-numbered TreeMap
TreeMap<String, Integer> treeMap = new TreeMap<>();
// Making use of the put() method
treeMap.put("Eight", 8);
treeMap.put("Twelve", 12);
// making use of the putIfAbsent() ethod
treeMap.putIfAbsent("Six", 6);
System.out.println("TreeMap of even numbers: " + treeMap);
//Making a number TreeMap
TreeMap<String, Integer> numbers = new TreeMap<>();
treeMap.put("One", 1);
// Using the putAll() method
numbers.putAll(treeMap);
System.out.println("TreeMap of of the given numbers: " + treeMap);
}
}
Operation Two: TreeMap Element Access
Using values(), keySet(), and entrySet()
- entrySet() – returns a collection of all the key/value mappings (entry) for a treemap key.
- keySet()- returns a collection of all the keys in a treemap.
- values() – delivers a collection of a tree map’s maps.
import java.util.TreeMap;
class CodeElementAccess {
public static void main(String[] args) {
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Eleven", 11);
treeMap.put("Twelve", 12);
treeMap.put("Thirteen", 13);
System.out.println("The TreeMap is: " + treeMap);
// utilizing the entrySet() method
System.out.println("The Key/Value mappings include: " + treeMap.entrySet());
// utilizing the keySet() method
System.out.println("The Keys include: " + treeMap.keySet());
// utilizing the values() method
System.out.println("The Values Include: " + treeMap.values());
}
}
Using the functions get() and getOrDefault()
- get() – Returns the value that corresponds to the supplied key. If the key cannot be retrieved, null is returned.
- getOrDefault() – Gets the default value for the provided key. If the key cannot be discovered, the default value is returned.
For instance,
import java.util.TreeMap;
class CodeElementAccessTwo {
public static void main(String[] args) {
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Eleven", 11);
treeMap.put("Twelve", 12);
treeMap.put("Thirteen", 13);
System.out.println("The TreeMap is: " + treeMap);
// Using get()
int valOne = numbers.get("Twelve");
System.out.println("Using get(): " + valOne);
// Using getOrDefault()
int valTwo = numbers.getOrDefault("Ten", 10);
System.out.println("Using getOrDefault(): " + valTwo);
}
}
The getOrDefault() method fails to locate the key Ten in this case. As a result, the default number 10 is returned.
Operation Three: Changing Elements
If we want to update an element after it has been added, we can do it by using the put() method to add it again. Because the keys are used to index the items in the treemap, the value of the key can be altered by simply adding the updated value for the key we want to change.
// program for Illustrating how to Updat TreeMap elements using the put() Method
// First, import the needed classes
import java.util.*;
// This is the Main class
class CodeUnderscored {
// Main driver method
public static void main(String args[])
{
// use Generics in the initialization of a TreeMap
TreeMap<Integer, String> treeMap
= new TreeMap<Integer, String>();
// Inserting the elements in Map
// using put() method
treeMap.put(3, "Code");
treeMap.put(2, "Code");
treeMap.put(1, "Code");
// Printing of all the current elements in the map
System.out.println(treeMap);
// Insertion of the element at the specified place corresponding to the key given
treeMap.put(2, "Underscored");
// Now, print the Maps' updated elements
System.out.println(treeMap);
}
}
Operation Four: Element Removal
The remove() method can delete an element from the TreeMap. If the key value is present in the map, this method removes the mapping for the key from the treemap.
Example
// Program for Illustrating Elements' Removal in the TreeMap using the method remove()
// First, importing the necessary classes
import java.util.*;
// This is the Main class
class CodeUnderscored {
// This is the driver's Main method
public static void main(String args[])
{
// Employ Generics to initialize a TreeMap
TreeMap<Integer, String> treeMap
= new TreeMap<Integer, String>();
// Inserting the elements
// using put() method
treeMap.put(3, "Code");
treeMap.put(2, "Underscored");
treeMap.put(1, "Coding");
treeMap.put(4, "2022");
// All the Map elements require printing
System.out.println(treeMap);
// Removal of the element that corresponds to the provided key
treeMap.remove(2);
// The updated TreeMap can now be Printed
System.out.println(treeMap);
}
}
Operation Five: Iterating through the TreeMap
There are several methods for iterating through the Map. The most well-known method is to utilize a for-each loop to obtain the keys. The getValue() method is designated for determining the key’s value.
Example
// Program for Illustrating Iteration over the TreeMap
// First, import the necessary classes
import java.util.*;
// This is the Main class
class CodeUnderscored {
// This is the driver's Main method
public static void main(String args[])
{
// Employ Generics to initialize a TreeMap
TreeMap<Integer, String> treeMap
= new TreeMap<Integer, String>();
// use the method, put(), to insert the element's
treeMap.put(3, "Code");
treeMap.put(2, "Underscored");
treeMap.put(1, "Coding");
// Use the entrySet() Method in a for-each loop traversal of the Map
for (Map.Entry mapElement : treeMap.entrySet()) {
int keyVar = (int)mapElement.getKey();
// locating the value
String valueVar = (String)mapElement.getValue();
// Printing the keyVar and valueVar
System.out.println(keyVar + " : " + valueVar);
}
}
}
Comparator for TreeMaps
Treemap elements are arranged organically in all of the instances above (in ascending order). We can, however, change the sequence of the keys. We’ll need to make our comparator class depending on how a treemap’s keys are arranged. For instance,
import java.util.TreeMap;
import java.util.Comparator;
class CodeCompartor {
public static void main(String[] args) {
// Using a custom comparator to create a treemap
TreeMap<String, Integer> treeMap = new TreeMap<>(new CustomComparator());
treeMap.put("Eleventh", 11);
treeMap.put("Twelveth",12);
treeMap.put("Thirteenth", 13);
treeMap.put("Fourteenth", 14);
System.out.println("TreeMap: " + treeMap);
}
// Constructing a comparator class
public static class CodeComparator implements Comparator<String> {
@Override
public int compare(String numberOne, String numberTwo) {
int valVar = numberOne.compareTo(numberTwo);
// reversing the order of elements
if ( valVar > 0) {
return -1;
}
else if ( valVar < 0) {
return 1;
}
else {
return 0;
}
}
}
}
Example: Java TreeMap
import java.util.*;
class CodeTreeMap1{
public static void main(String args[]){
TreeMap<Integer,String> treeMap=new TreeMap<Integer,String>();
treeMap.put(02,"Green");
treeMap.put(05,"Joy");
treeMap.put(07,"Bright");
treeMap.put(09,"Lucy");
for(Map.Entry m:treeMap.entrySet()){
System.out.println(m.getKey()+" "+m.getValue());
}
}
}
Example: Java TreeMap remove()
import java.util.*;
public class CodeTreeMap {
public static void main(String args[]) {
TreeMap<Integer,String> treeMap=new TreeMap<Integer,String>();
treeMap.put(02,"Green");
treeMap.put(05,"Joy");
treeMap.put(07,"Bright");
treeMap.put(09,"Lucy");
System.out.println(" Results prior to invoking the remove() method");
for(Map.Entry m:treeMap.entrySet())
{
System.out.println(m.getKey()+" "+m.getValue());
}
map.remove(02);
System.out.println("Results proceeding the invoking of the remove() method");
for(Map.Entry m:treeMap.entrySet())
{
System.out.println(m.getKey()+" "+m.getValue());
}
}
}
Example: Java TreeMap NavigableMap
import java.util.*;
class CodeTreeMap{
public static void main(String args[]){
NavigableMap<Integer,String> treeMap=new TreeMap<Integer,String>();
treeMap.put(02,"Green");
treeMap.put(05,"Joy");
treeMap.put(07,"Bright");
treeMap.put(09,"Lucy");
//Keeps the descending order
System.out.println("descendingMap: "+treeMap.descendingMap());
//Key-value pairs having keys that are less than or equal to the specified key are returned.
System.out.println("headMap: "+treeMap.headMap(02,true));
//Returns key-value pairs with keys equal to or greater than the supplied key.
System.out.println("tailMap: "+treeMap.tailMap(02,true));
//responsible for returning the count of key-value pairs between the provided keys.
System.out.println("subMap: "+treeMap.subMap(09, false, 02, true));
}
}
Example: Java TreeMap SortedMap
import java.util.*;
class CodeTreeMap{
public static void main(String args[]){
SortedMap<Integer,String> treeMap=new TreeMap<Integer,String>();
treeMap.put(02,"Green");
treeMap.put(05,"Joy");
treeMap.put(07,"Bright");
treeMap.put(09,"Lucy");
//Key-value pairs with keys smaller than the specified key are returned.
System.out.println("The headMap is: "+map.headMap(02));
//Returns key-value pairs with keys equal to or greater than the supplied key.
System.out.println("The tailMap is: "+map.tailMap(02));
//responsible for returning the count of key-value pairs between the provided keys.
System.out.println("The subMap is: "+map.subMap(09, 02));
}
}
Example: Java TreeMap Laptop
import java.util.*;
class Laptop {
int id;
String name,author,publisher;
int quantity;
public Laptop(int id, String name, String model, String manufacturer, int quantity) {
this.id = id;
this.name = name;
this.model = model;
this.manufacturer = manufacturer;
this.quantity = quantity;
}
}
public class CodeMap {
public static void main(String[] args) {
//Creating map of Laptops
Map<Integer,Laptop> treeMap=new TreeMap<Integer,Laptop>();
//Creating Laptops
Laptop laptopOne=new Laptop(1,"Lenovo Yoga","LN90THY","Lenovo",20);
Laptop laptopTwo=new Laptop(2,"HP Probook","P8976T","HP",5);
Laptop laptopThree=new Laptop(3,"Toshiba Slim","T999T","Toshiba",2);
//Adding Laptops to map
treeMap.put(2,laptopTwo);
treeMap.put(1,laptopOne);
treeMap.put(3,laptopThree);
//Traversing map
for(Map.Entry<Integer, Laptop> entry:treeMap.entrySet()){
int key=entry.getKey();
Laptop bVar=entry.getValue();
System.out.println(key+" Details:");
System.out.println(bVar .id+" "+bVar.name+" "+bVar.model+" "+bVar.manufacturer+" "+b.quantity);
}
}
}
Conclusion
With the help of examples, we have learned about the Java TreeMap class and its actions in this article. The tree data structure is implemented by the Java collections framework’s TreeMap class. Further, the NavigableMap interface is implemented.
The TreeMap class uses a tree to implement the Map interface. A TreeMap is an effective way to store key/value pairs in sorted order and retrieve them quickly. It’s worth noting that, unlike a hash map, a treemap ensures that the items are ordered in ascending key order. In addition, the Java TreeMap class implements a red-black tree model. It facilitates the storage of key-value pairs in sorted order quickly.
