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.

Class Loaders in Java

Java Virtual Machine contains class loader subsystem which takes care of finding and loading types, both classes and interfaces. JVM contains separate namespaces for classes loaded using different class loaders. JVM keeps the track of classes loaded by individual Class Loaders. Java Class Loader works in three principles

1) Delegation principle:
The request for loading a particular class starts from Application Class Loader. Application Class Loader checks in the cache whether the class is already loaded ,if not then delegated the request to Extension Class Loader. Extension Class Loader also checks in the cache and if not found , delegates the request to Bootstrap Class Loader. Bootstrap Class Loader also checks in the cache  , if the class is not found , it checks whether the class is to loaded by it or not. If the class is not a part of API ie rt.jar , etc that means it is not to be loaded by Bootstrap , the request is delegated back to Extension Class Loader. Extension Class Loader will search in the extension (ext) folders of jdk or jre. If the class is not found it will delegate the request back to Application Class Loader. thus the request will start from Application class Loader , go up the hierarchy and come back to Application Class Loader , it has to load the class , eg. User defined class.

2) Visibility principle:
Classes loaded by Class Loaders up in hierarchy will be visible down the hierarchy. Class Loaded by Bootstrap Class Loader will be visible to Extension Class Loader and Application Class Loader and if a class is loaded by Extension Class Loader it will be visible to Application Class Loader and the class will not be visible to Bootstrap Class Loader. if a class is loaded by Application Class Loader ,it will not be visible to both Bootstrap and Extension Class Loaders.

3) Uniqueness Principle:
If a class is loaded by a Class Loader , it will not be loaded again by any Class Loader down the heirarchy.

Java Virtual Machine contains two types of class loaders
A) Primordial class loader and
B) ClassLoader objects

The primordial class loader is  virtual machine implementation whereas class loader object is running Java application component. If JVM is implemented using/in C programming language , then the primordial class loader will be also a part of C program whereas Class Loader objects are Java API classes written in Java which are compiled to class files and loaded and instantiated like any other java class object.

A) The Primordial Class Loader
The primordial Class loader (Bootstrap Class Loader) loads trusted classes, including the classes of the Java API.It loads the Java API classes ie rt.jar, core.jar, i18n.jar ,etc.It is not a subclass of java.lang.ClassLoader.

Demo1

package com.classloader;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
public class BootStrapDemo {

public static void main(String[] args) {
System.out.println(Integer.class.getClassLoader());

}

}

Output:
null

Note: As Bootstrap class loader is the implementation of JVM and not the child class of Class Loader , it displays null.

B) The Class Loader Objects 
Under this category we have Extension Class loader and Application(System) Class loader.These are subclass of java.lang.ClassLoader.

Inheritance hierarchy of Class Loader objects

i)The Extension Class loader
It loads the classes from the jars which are present in the extension directory of JRE ...\Java\jdk1.6.0\jre\lib\ext  or  ...\Java\jre6\lib\ext. It is used to introduce new functionality like mysql driver jar required to load driver for jdbc connection.

Demo 2

package com.classloader;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
public class ExtensionDemo {
public static void main(String[] args) {
try {
System.out.println(Class.forName("com.mysql.jdbc.Driver").getClassLoader().getClass());
} catch (ClassNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}

Output:
class sun.misc.Launcher$ExtClassLoader

ii)Application Class loader
It is also known as System class loader.It is the default class loader. it loads the classes of the classpath. If mysql jar is added to the classpath , it will be loaded by Application class loader.

Demo 3

package com.classloader;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
public class ApplicationDemo {
public static void main(String[] args) {
System.out.println(ApplicationDemo.class.getClassLoader().getClass());

}
}

Output:
class sun.misc.Launcher$AppClassLoader

Conclusion : 
JVM has two types of class loaders 1) Primordial (Bootstrap) Class Loader and 2) Class Loader Objects. Class Loader Objects are Application Class Loader and Extension Class loader. JVM follows three principles ,  while loading a class , delegation principle , visibility principle and uniqueness principle.