TreeMap本质上是红黑树（红黑树参考：链接，该文就是用TreeMap举例来说明红黑树操作的），并没有继承HashMap，和HashMap存在着本质区别。TreeMap的排序是基于对key的排序实现的，它的每一个Entry代表红黑树的一个节点。
Entry的数据结构如下：
static final class Entry<K,V> implements Map.Entry<K,V> {
// 键
K key;
// 值
V value;
// 左孩子
Entry<K,V> left = null;
// 右孩子
Entry<K,V> right = null;
// 父节点
Entry<K,V> parent;
// 当前节点颜色
boolean color = BLACK;
// 构造函数
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
再来看下TreeMap的构造方法。TreeMap一共有4个构造方法。
1、无参构造方法
public TreeMap() {
comparator = null;
}
采用无参构造方法，不指定比较器，这时候，排序的实现要依赖key.compareTo()方法，因此key必须实现Comparable接口，并覆写其中的compareTo方法。
2、带有比较器的构造方法
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
采用带比较器的构造方法，这时候，排序依赖该比较器，key可以不用实现Comparable接口。
3、带Map的构造方法
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
该构造方法同样不指定比较器，调用putAll方法将Map中的所有元素加入到TreeMap中。putAll的源码如下：
// 将map中的全部节点添加到TreeMap中
public void putAll(Map<? extends K, ? extends V> map) {
// 获取map的大小
int mapSize = map.size();
// 如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value对”
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator c = ((SortedMap)map).comparator();
// 如果TreeMap和map的比较器相等；
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
//二分法快速加入，其余情况逐个加入
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// 调用AbstractMap中的putAll();
// AbstractMap中的putAll()又会调用到TreeMap的put()
super.putAll(map);
}
4、带有SortedMap的构造方法
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
//直接二分法加入
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
TreeMap的put方法则对应红黑树的插入：
public V put(K key, V value) {
Entry<K,V> t = root;
// 若红黑树为空，则插入根节点
if (t == null) {
// TBD:
// 5045147: (coll) Adding null to an empty TreeSet should
// throw NullPointerException
//
// compare(key, key); // type check
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
// 找出(key, value)在二叉排序树中的插入位置。
// 红黑树是以key来进行排序的，所以这里以key来进行查找。
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 为（key-value）新建节点
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 插入新的节点后，调用fixAfterInsertion调整红黑树。
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
这里的fixAfterInsertion便是节点插入后对树进行调整的方法。关于红黑树，这里不做赘述。
删除操作则对应TreeMap的deleteEntry方法：
// 删除“红黑树的节点p”
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) {
Entry<K,V> s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null;
} else {
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
后面的fixAfterDeletion方法便是节点删除后对树进行调整的方法。关于红黑树，这里不做赘述。其它还有一些细节，都可在介绍红黑树的文章里研究。
关于TreeMap的源码，给出几点总结：
1、TreeMap是根据key进行排序的，它的排序和定位需要依赖比较器或覆写Comparable接口。也可能因此不需要key覆写hashCode方法和equals方法，就可以排除掉重复的key，而HashMap的key则需要通过覆写hashCode方法和equals方法来确保没有重复的key。
2、TreeMap的查询、插入、删除效率均没有HashMap高，一般只有要对key排序时才使用TreeMap。
3、TreeMap的key一般认为不能为null（比较器设置正确），而HashMap的key可以为null。
4、TreeMap必须正确设置比较器（或采用默认设置），否则结果不可预测。
参考地址：http://blog.csdn.net/ns_code/article/details/36421085