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
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
public Main() {
map = new TreeMap
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
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
public Main() {
map = new TreeMap
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 .