TreeMap
interface SortedMap extends Map
interface NavigableMap extends SortedMap
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable
TreeMap class extends AbstractMap and implements NavigableMap interface.
TreeMap is best choice when you want to store key value pair according to some sorting order. Entries in TreeMap sorted according to key.
Entries in TreeMap are sorted according to natural sorting order (default sorting order) of key or Custom Sorting order.
For Custom Sorting order Comparator provided at time of creating of TreeMap.
How TreeMap is Implemented in Java
According to Java Doc TreeMap is a Red-Black tree based NavigableMap implementation. This implementation guaranteed log(n) time cost for the containsKey , get, put and remove operation.
Feature of TreeMap
- TreeMap is Red-Black tree based NavigableMap implementation
- TreeMap stores its entries(key,value) according to some sorting order, this sorting order based on key.
- If you want to store entries according to some custom sorting order then you need to provide Comparator.
- TreeMap does not allow null key as other Map like HashMap and LinkedHashMap support one and only one null key.
- TreeMap in java is not Synchronized, Hence it is not Thread Safe.
Java TreeMap Constructor
- TreeMap() - Construct new and empty TreeMap using the natural ordering its keys
- TreeMap(Comparator<? super K> comprator) - constructs new, empty TreeMap orerded according to Comparator.
- TreeMap(Map<? extends K, ? extends V> map ) - constructs new TreeMap based on provided Map , ordered according to natural ordering of keys.
- TreeMap(SortedMap<K,? extends V> sortedMap) - construct new TreeMap containing the same mapping and using the same ordering as specified sorted map.
TreeMap Example - Construction , Insertion and Iteration
Following example add pincode as key and Corresponding area as value. This example uses spring for dependency Injection.
package io.lambda.collection.map.treemap;
import java.util.Map;
import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;
public class Zip {
private Map<Integer,String>zipcode;
public Zip(Map<Integer,String>zipcode) {
this.zipcode=zipcode;
}
public void addMockZipCode() {
zipcode.put(226010, "Gomti Nagar");
zipcode.put(110001,"CP");
zipcode.put(110041,"WestDelhi");
zipcode.put(110070,"vasantkunj");
zipcode.put(110070,"Vasantkunj");
}
public void display() {
//lambda expression to print entries.
zipcode.forEach((k,v)->{System.out.println(k+":"+v);});
}
public static void main(String[] args) {
ApplicationContext context=new ClassPathXmlApplicationContext("zipcode.xml");
Zip zip=context.getBean("zipcode", io.lambda.collection.map.treemap.Zip.class);
zip.addMockZipCode();
zip.display();
}
}
//zipcode.xml
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://www.springframework.org/schema/beans
http://www.springframework.org/schema/beans/spring-beans.xsd
http://www.springframework.org/schema/util
http://www.springframework.org/schema/util/spring-util.xsd">
<bean id="zipcode" class="io.lambda.collection.map.treemap.Zip">
<constructor-arg ref="treeMap"/>
</bean>
<bean id="treeMap" class="java.util.TreeMap"></bean>
</beans>
Output :
110001:CP
110041:WestDelhi
110070:Vasantkunj
226010:Gomti Nagar
The output of the above program clearly show that key is sorted according to its natural sorting order.
It is also noted that Vasantkunj added twice but it store only once, it overwrite old value with new one.
[ as calculated hash code for keys are same].
TreeMap doesnot allow null key.
Though HashMap and LinkedHashMap allowed one and only one null as key , TreeMap in java does not allow null as a key. An attempt to add null as key throw NullPointerException.
package io.lambda.collection.map.treemap;
import java.util.Map;
import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;
public class Zip {
private Map<Integer,String>zipcode;
public Zip(Map<Integer,String>zipcode) {
this.zipcode=zipcode;
}
public void addMockZipCode() {
zipcode.put(226010, "Gomti Nagar");
zipcode.put(110001,"CP");
zipcode.put(110041,"WestDelhi");
zipcode.put(110070,"vasantkunj");
zipcode.put(110070, "Vasantkunj");
zipcode.put(null, "upcomingCity");
}
public void display() {
zipcode.forEach((k,v)->{System.out.println(k+":"+v);});
}
public static void main(String[] args) {
ApplicationContext context=new ClassPathXmlApplicationContext("zipcode.xml");
Zip zip=context.getBean("zipcode", io.lambda.collection.map.treemap.Zip.class);
zip.addMockZipCode();
zip.display();
}
Output :
Exception in thread "main" java.lang.NullPointerException
at java.base/java.util.TreeMap.put(TreeMap.java:561)
at io.lambda.collection.map.treemap.Zip.addMockZipCode(Zip.java:22)
at io.lambda.collection.map.treemap.Zip.main(Zip.java:31)
Custom Sorting order of key in TreeMap
Entries in TreeMap are sorted according to natural sorting order of keys, but if you want to sort TreeMap according to some custom sorting order e.g. Descending order of number , words etc. then you provide Comparator at Map creating time.
/**
* Student Class
**/
package io.lambda.collection.map.treemap;
public class Student implements Comparable<Student>{
Integer enrollmentId;
String name;
public Student(Integer enrollmentId,String name) {
this.enrollmentId=enrollmentId;
this.name=name;
}
public Integer getEnrollmentId() {
return enrollmentId;
}
public void setEnrollmentId(Integer enrollmentId) {
this.enrollmentId = enrollmentId;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public int compareTo(Student student) {
return this.enrollmentId.compareTo(student.enrollmentId);
}
@Override
public String toString() {
return "enrollment : "+this.enrollmentId +"name :"+this.name;
}
}
/**
*Course Class
*/
package io.lambda.collection.map.treemap;
public class Course {
String name;
public Course(String name) {
this.name=name;
}
@Override
public String toString() {
return this.name;
}
}
/**
* Client Class having main method
*/
package io.lambda.collection.map.treemap;
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;
public class StudentMap {
Map<Student,Course> classX;
static Map<Student,Course> classXI;
public StudentMap(Map<Student,Course> classX) {
this.classX=classX;
}
public void createSection() {
classX.put(new Student(1001,"Yogesh"), new Course("X"));
classX.put(new Student(1002,"Mohan"), new Course("X"));
classX.put(new Student(1000,"Rakesh"),new Course("X"));
}
public void display() {
classX.forEach((student,course)->{System.out.println(student+":"+course);});
}
public static void main(String[] args) {
StudentMap map=new StudentMap(new TreeMap<Student,Course>());
map.createSection();
map.display();
//anonymous implementation of Comparator interface
classXI=new TreeMap<Student,Course>(new Comparator<Student>() {
@Override
public int compare(Student s1,Student s2) {
return s1.name.compareTo(s2.name)==0?0:s1.name.compareTo(s2.name)>0?
5:-1;
}
});
classXI.putAll(map.classX);
classXI.entrySet().stream().forEach(System.out::println);
}
}
Output
enrollment : 1000name :Rakesh:X
enrollment : 1001name :Yogesh:X
enrollment : 1002name :Mohan:X
enrollment : 1002name :Mohan=X
enrollment : 1000name :Rakesh=X
enrollment : 1001name :Yogesh=X
Here custom Comparator built with logic to sort entries of TreeMap based on Student Class name attribute. First part of output highlighted with blue color show the output from TreeMap no-args constrcutor while other Green color show the output which implement Comparator interface.
It sorts entries based one Student Name.
TreeMap is not Synchronized
TreeMap in Java is not ThreadSafe. In case we need to synchronize it , it should synchronize with the help of Collections.synchronizedSortedMap(TreeMap<K,V>) method.
for example
SortedMap map=Collections.synchronizedSortedMap(classX); // where classX is from above example which is Type of TreeMap<Student,Course>
TreeMap iterator is Fail-Fast
Like other Collection class iterator TreeMap iterator is Fail-Fast. If the map is structurally modified after getting Iterator for Map, then Iterator will throw a ConcurrentModificationException.
TreeMap Iteration
1. Get only keys using Map.keySet() method
package io.lambda.collection.map.treemap;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
public class TreeMapIterator {
private Map<String,String>stateCapitalMap = new TreeMap<>(); //No-args constructor
/*
* add state and there capital
*/
public void addMockEntries() {
stateCapitalMap.put("Delhi", "New Delhi");
stateCapitalMap.put("Uttar Pradesh", "Lucknow");
stateCapitalMap.put("Uttara Khand", "Dehradun");
stateCapitalMap.put("J&K", "Shri Nagar");
stateCapitalMap.put("Bhiar", "Patna");
}
public void displayKeySetIterator() {
Iterator<String> itr=stateCapitalMap.keySet().iterator();
System.out.println("using Map interface Set<T>keySet().itrator()\tOutput\n");
while(itr.hasNext()) {
System.out.println(itr.next());
}
}
public void displayKeySetForEachLoop() {
System.out.println("\nUsing For - Each loop\t Output\n");
for(String state : stateCapitalMap.keySet()) {
System.out.println(state);
}
}
public void displayKeySetForEachLambda() {
System.out.println("\nusing Stream class stream() method\toutput\n");
stateCapitalMap.keySet().stream().forEach(System.out::println);
}
public static void main(String[] args) {
TreeMapIterator example=new TreeMapIterator();
example.addMockEntries();
example.displayKeySetIterator();
example.displayKeySetForEachLoop();
example.displayKeySetForEachLambda();
}
}
using Map interface Set<T>keySet().itrator() Output
Bhiar
Delhi
J&K
Uttar Pradesh
Uttara Khand
Using For - Each loop Output
Bhiar
Delhi
J&K
Uttar Pradesh
Uttara Khand
using Stream class stream() method output
Bhiar
Delhi
J&K
Uttar Pradesh
Uttara Khand
2. Get Value only using Collection<T> values() method
package io.lambda.collection.map.treemap;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
public class TreeMapIterator {
private Map<String,String>stateCapitalMap = new TreeMap<>(); //No-args constructor
/*
* add state and there capital
*/
public void addMockEntries() {
stateCapitalMap.put("Delhi", "New Delhi");
stateCapitalMap.put("Uttar Pradesh", "Lucknow");
stateCapitalMap.put("Uttara Khand", "Dehradun");
stateCapitalMap.put("J&K", "Shri Nagar");
stateCapitalMap.put("Bhiar", "Patna");
}
public void displayValuesIterator() {
Iterator<String>value=stateCapitalMap.values().iterator();
while(value.hasNext()) {
System.out.println(value.next());
}
}
public void displayValuesUsingForEachLoop() {
for(String s: stateCapitalMap.values()) {
System.out.println(s);
}
}
public void displayValuesUsingStreamMethod() {
stateCapitalMap.values().stream().forEach(System.out::println);
}
public static void main(String[] args) {
TreeMapIterator example=new TreeMapIterator();
example.addMockEntries();
System.out.println("Output : Using Iterator\n");
example.displayValuesIterator();
System.out.println("Output : Using For - Each loop \n");
example.displayValuesUsingForEachLoop();
System.out.println("Output : Using forEach() method \n");
example.displayValuesUsingStreamMethod();
}
}
Output : Using Iterator
Patna
New Delhi
Shri Nagar
Lucknow
Dehradun
Output : Using For - Each loop
Patna
New Delhi
Shri Nagar
Lucknow
Dehradun
Output : Using forEach() method
Patna
New Delhi
Shri Nagar
Lucknow
Dehradun
3. Iteration Key and Value
package io.lambda.collection.map.treemap;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
public class TreeMapIterator {
private Map<String,String>stateCapitalMap = new TreeMap<>(); //No-args constructor
/*
* add state and there capital
*/
public void addMockEntries() {
stateCapitalMap.put("Delhi", "New Delhi");
stateCapitalMap.put("Uttar Pradesh", "Lucknow");
stateCapitalMap.put("Uttara Khand", "Dehradun");
stateCapitalMap.put("J&K", "Shri Nagar");
stateCapitalMap.put("Bhiar", "Patna");
}
public void displayEntriesIterator() {
Iterator<Map.Entry<String, String>>itr=stateCapitalMap.entrySet().iterator();
while(itr.hasNext()) {
Map.Entry<String, String>mapEntry=itr.next();
System.out.println(mapEntry.getKey()+" : "+mapEntry.getValue());
}
}
public void displayEntriesUsingForEachLoop() {
for(Map.Entry<String, String> mapEntry:stateCapitalMap.entrySet()) {
System.out.println(mapEntry.getKey()+" : "+mapEntry.getValue());
}
}
public void displayEntriesUsingForEachMethodLambdaMethodReference() {
stateCapitalMap.entrySet().stream().forEach(System.out::println);
}
public void displayEntriesUsingForEachLambda() {
stateCapitalMap.forEach((k,v)->{System.out.println(k+" : "+v);});
}
public static void main(String[] args) {
TreeMapIterator example=new TreeMapIterator();
example.addMockEntries();
System.out.println("Output : Using Iterator\n");
example.displayEntriesIterator();
System.out.println("\nOutput : Using For - Each loop \n");
example.displayEntriesUsingForEachLoop();
System.out.println("\nOutput : Using forEach() method \t Method Reference \n");
example.displayEntriesUsingForEachMethodLambdaMethodReference();
System.out.println("\nOutput : Using forEach() method \t Lambda expression \n");
example.displayEntriesUsingForEachLambda();
}
}
Output : Using Iterator
Bhiar : Patna
Delhi : New Delhi
J&K : Shri Nagar
Uttar Pradesh : Lucknow
Uttara Khand : Dehradun
Output : Using For - Each loop
Bhiar : Patna
Delhi : New Delhi
J&K : Shri Nagar
Uttar Pradesh : Lucknow
Uttara Khand : Dehradun
Output : Using forEach() method Method Reference
Bhiar=Patna
Delhi=New Delhi
J&K=Shri Nagar
Uttar Pradesh=Lucknow
Uttara Khand=Dehradun
Output : Using forEach() method Lambda expression
Bhiar : Patna
Delhi : New Delhi
J&K : Shri Nagar
Uttar Pradesh : Lucknow
Uttara Khand : Dehradun
