TreeMap in Java

Posted by Bijoy on in Map

TreeMap is a class that implements the Map interface.In every Map implementation data is storing as key-value pairs.A HashMap is unordered and unsorted map implementation .But TreeMap is the ordered Map implementation. In TreeMap , the items are storing in a specified order(ascending ,descending etc) of keys.For making an object as key in a TreeMap , either

a)The class should  implement Comparable interface , or

b)A Comparator instance should pass as constructor argument  at the time initialization of TreeMap.

In case a , the CompareTo() method implementation determines the order of map.In case b the  compare() method  determines the order.

case1)Objects of  Inbuilt classes like String  as keys in TreeMap.

Classes like String , Integer, Double are implementing Comparable interface by default.The compareTo() method does the logic to sort the objects in ascending order.So , if we are using objects String or Integer or Double as keys in our TreeMap, then the items will be in ascending order.

Let us verify this with an example.We are storing Employee objects as values against String keys .

See the Employee.java shown below.

public class Employee {
private int id;
private String name;
public Employee(int empId, String name) {
this.id = empId;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String toString() {
return "Id = " + getId() + " ; Name = " + getName();
}
}

Now let us see the Main.java

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class Main {
private Map map = null;
public Main() {
map = new TreeMap();
}
public void addItems() {
Employee emp1 = new Employee(1, "BIJOY");
map.put("1", emp1);
Employee emp2 = new Employee(2, "Karthik");
map.put("3", emp2);
Employee emp3 = new Employee(3, "Dexter");
map.put("0", emp3);
Employee emp4 = new Employee(4, "JayaKrishnan");
map.put("2", emp4);
}
public void displayItems() {
Set set = map.entrySet();
System.out.println("Size = " + set.size());
Iterator i = set.iterator();
while (i.hasNext()) {
Map.Entry entry = (Map.Entry) i.next();
System.out.print(entry.getKey() + ": ");
System.out.println(entry.getValue());
}
}
public static void main(String[] args) {
Main main = new Main();
main.addItems();
main.displayItems();
}
}

In addItems() method , we are creating four Employee objects , and putting these objects as values against String keys in TreeMap object  in a randon order .As of our discussion , it is clear that  the compareTo() method in java.lang.String class sorts objects in ascending order.Hence  data is storing in the ascending order of keys.Let us verify the output.

Output

Size = 4

0: Id = 3 ; Name = Dexter

1: Id = 1 ; Name = BIJOY

2: Id = 4 ; Name = JayaKrishnan

3: Id = 2 ; Name = Karthik.

So it is very much clear now.Now what we need to do ,  to get data to be stored in a different order? We know , the classes like String , Integer , Double are having Comparable implementation in it.The compareTo() method is responsible for  sorting the objects in ascending order. To get a different  sorting order here , we should use a Comparator instance as argument  while initializing a TreeMap.So our modified Main.java is shown below.Employee.java is the same one we already used.

import java.util.*;
public class Main {
private Map map = null;
public Main() {
map = new TreeMap(new Comparator() {
public int compare(String s, String s1) {
return s1.compareTo(s);
}
});
}
public void addItems() {
Employee emp1 = new Employee(1, "BIJOY");
map.put("1", emp1);
Employee emp2 = new Employee(2, "Karthik");
map.put("3", emp2);
Employee emp3 = new Employee(3, "Dexter");
map.put("0", emp3);
Employee emp4 = new Employee(4, "JayaKrishnan");
map.put("2", emp4);

}
public void displayItems() {
Set set = map.entrySet();
System.out.println("Size = " + set.size());
Iterator i = set.iterator();
while (i.hasNext()) {
Map.Entry entry = (Map.Entry) i.next();
System.out.print(entry.getKey() + ": ");
System.out.println(entry.getValue());
}
}
public static void main(String[] args) {
Main main = new Main();
main.addItems();
main.displayItems();
}
}

In this case the Comparator determining the sorting order.Let us verify the output here.

Output

Size = 4

3: Id = 2 ; Name = Karthik

2: Id = 4 ; Name = JayaKrishnan

1: Id = 1 ; Name = BIJOY

0: Id = 3 ; Name = Dexter

Summary

If we are using objects of  inbuilt classes like String , Integer ,  Double etc as keys in our TreeMap ,then the map , by default is in ascending order of keys.To change the order ,  a Comparator instance must pass as argument while initializing the TreeMap.

Case2:Objects of our own classes as keys in TreeMap

For an object to be used as key in a TreeMap either the class needs to implement the Comparable interface or a Comparator instance needs to pass as an argument at the time of initialization of TreeMap. The compareTo()  and compare() methods are responsible for the order of sorting.

1)  Let us see an example with implementing Comparable interface.In this case We are  putting String data against Employee objects.Let us see the Employee.java.

public class Employee implements Comparable {
private int id;
private String name;
public Employee(int empId, String name) {
this.id = empId;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String toString() {
return "Id = " + getId() + " ; Name = " + getName();
}
public int compareTo(Object o) {
Employee emp = (Employee)o;
return getId()-emp.getId();
}
}

Now let us see the Main.java

import java.util.*;
public class Main {
private Map map = null;
public Main() {
map = new TreeMap();
}
public void addItems() {
Employee emp1 = new Employee(1, "BIJOY");
map.put(emp1 ,"one");
Employee emp2 = new Employee(2, "Karthik");
map.put(emp2,"two");
Employee emp3 = new Employee(3, "Dexter");
map.put(emp3,"zero");
Employee emp4 = new Employee(4, "JayaKrishnan");
map.put(emp4,"four");
}
public void displayItems() {
Set set = map.entrySet();
System.out.println("Size = " + set.size());
Iterator i = set.iterator();
while (i.hasNext()) {
Map.Entry entry = (Map.Entry) i.next();
System.out.print(entry.getKey() + ": ");
System.out.println(entry.getValue());
}
}
public static void main(String[] args) {
Main main = new Main();
main.addItems();
main.displayItems();
}
}

Now let us see the output.

Output

Size = 4

Id = 1 ; Name = BIJOY: one

Id = 2 ; Name = Karthik: two

Id = 3 ; Name = Dexter: zero

Id = 4 ; Name = JayaKrishnan: four

So the output is in the ascending order of id. To change the sorting order ,just change the return statement in compareTo() of Employee.java to:

return emp.getId() – getId()

then we can see the order is reversing.

2)    Now let us examine how a Comparator instance is using to determine the order.Let us see the Employee.java first.Remember , here we are not implementing the Comparable interface.

public class Employee {
private int id;
private String name;
public Employee(int empId, String name) {
this.id = empId;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String toString() {
return "Id = " + getId() + " ; Name = " + getName();
}
}

Now , we are going to examine the Main.java.here a Comparator instance is passing as argument  while initializing TreeMap object.

import java.util.*;
public class Main {
private Map map = null;
public Main() {
map = new TreeMap(new Comparator() {
public int compare(Employee employee, Employee employee1) {
return employee.getId() - employee1.getId();
}
});
}
public void addItems() {
Employee emp1 = new Employee(1, "BIJOY");
map.put(emp1, "one");
Employee emp2 = new Employee(2, "Karthik");
map.put(emp2, "two");
Employee emp3 = new Employee(3, "Dexter");
map.put(emp3, "zero");
Employee emp4 = new Employee(4, "JayaKrishnan");
map.put(emp4, "four");
}
public void displayItems() {
Set set = map.entrySet();
System.out.println("Size = " + set.size());
Iterator i = set.iterator();
while (i.hasNext()) {
Map.Entry entry = (Map.Entry) i.next();
System.out.print(entry.getKey() + ": ");
System.out.println(entry.getValue());
}
}
public static void main(String[] args) {
Main main = new Main();
main.addItems();
main.displayItems();
}
}

Output

Size = 4

Id = 1 ; Name = BIJOY: one

Id = 2 ; Name = Karthik: two

Id = 3 ; Name = Dexter: zero

Id = 4 ; Name = JayaKrishnan: four

So the items got arranged in ascending order of id. Now change the return statement of compare() method to:

return employee1.getId() – employee.getId()

then we can the order is changing.You can verify it.

For objects of our own classes to be used as keys in TreeMap , we need not  to override the hashCode() and equals() methods of Object class.Because in TreeMap is not based on hash code value of objects.But it depends on Comparator or Comparable implementations. (Please read the post for more info about hashCode()) .But for other Map implementations(HasmMap,LinkedHashMap and hashtable overriding of hashCode() and equals() is mandatory , because these structures depends on hash code values)

Summary

If we need objects of our own classes as  keys in TreeMap then either the class should implement the Comparable interface or a Comparator instance needs to pass as  constructor argument of TreeMap. Also the class whose objects needs to be used as keys in TreeMap need not   override the hashCode() and equals() methods .

2 thoughts on “TreeMap in Java”

  1. Pingback: Collections in Java | CoderPanda

Leave a Reply

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