Internal working of TreeMap

TreeMap is using a Red-Black tree implementation. A red–black tree is a data structure which is a type of self-balancing binary search tree. When the tree is modified,the new tree is subsequently rearranged to make it balanced.
TreeMap is used to sort the data.If you are using the default constructor , sorting is done on the basis of natural ordering (Comparable in case of String) and if you provide Comparator , the sorting will be on the basis of compareTo function.

Demo 1: 

package com.a;
import java.util.TreeMap;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
public class Demo1 {

public static void main(String[] args) {
TreeMap<String, String> map = new TreeMap<String, String>();
map.put("d", "first element");
map.put("h", "second element");
map.put("f", "third element");
map.put("a", "fourth element");
map.put("c", "fifth element");
System.out.println(map);

}

}

Output:

{a=fourth element, c=fifth element, d=first element, f=third element, h=second element}

As we have used TreeMap default constructor and having String as key , the sorting will be on the basis of characters (a , c , d , f and h).

Now we will try to understand , how to implement Comparable and Comparator in program.
We will use Person class having id field and we want the sorting to be done on the basis of id.

Demo2: Implementing Comparable

package com.a;
import java.util.TreeMap;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Person implements Comparable {
private int id;

public Person() {
super();
// TODO Auto-generated constructor stub
}
public Person(int id) {
super();
this.id = id;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
@Override
public String toString() {
return "Person [id=" + id + "]";
}
@Override
public int compareTo(Object o) {
Person p = (Person) o;
if (this.id == p.id)
return 0;
else if (this.id > p.id)
return 1;
else
return -1;
}
}

public class Demo2 {

public static void main(String[] args) {
TreeMap<Person, String> map = new TreeMap<Person, String>();
Person p1 = new Person(18);
Person p2 = new Person(6);
Person p3 = new Person(4);
Person p4 = new Person(12);
Person p5 = new Person(10);
map.put(p1, "first data");
map.put(p2, "second data");
map.put(p3, "third data");
map.put(p4, "fourth data");
map.put(p5, "fifth data");
System.out.println(map);
}

}

Output:

{Person [id=4]=third data, Person [id=6]=second data, Person [id=10]=fifth data, Person [id=12]=fourth data, Person [id=18]=first data}


Demo 3: Implementing Comparator

package com.a;
import java.util.Comparator;
import java.util.TreeMap;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Person implements Comparator {
private int id;

public Person() {
super();
// TODO Auto-generated constructor stub
}
public Person(int id) {
super();
this.id = id;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
@Override
public String toString() {
return "Person [id=" + id + "]";
}
@Override
public int compare(Object o1, Object o2) {
Person p1 = (Person) o1;
Person p2 = (Person) o2;
if (p1.id == p2.id)
return 0;
else if (p1.id > p2.id)
return 1;
else
return -1;
}
}

public class Demo2 {

public static void main(String[] args) {
TreeMap<Person, String> map = new TreeMap<Person, String>(new Person());
Person p1 = new Person(18);
Person p2 = new Person(6);
Person p3 = new Person(4);
Person p4 = new Person(12);
Person p5 = new Person(10);
map.put(p1, "first data");
map.put(p2, "second data");
map.put(p3, "third data");
map.put(p4, "fourth data");
map.put(p5, "fifth data");
System.out.println(map);
}

}

Output:

{Person [id=4]=third data, Person [id=6]=second data, Person [id=10]=fifth data, Person [id=12]=fourth data, Person [id=18]=first data}

The above result shows that the sorting is done on the basis of id.

Conclusion:
TreeMap is used to sort data on the basis of comparable or comparator.TreeMap uses Red-Black tree implementation which is self-balancing binary tree. Using TreeMap is expensive as it will try to shift nodes every time modification is done in order to balance the tree.