TreeMap源码分析
treemap的数据结构基础是红黑树。
可以到如下复习一下红黑树：
http://blog.csdn.net/a910626/article/details/54378874
节点
static final class Entry<K,V> implements Map.Entry<K,V> {
// 键
K key;
// 值
V value;
// 左孩子
Entry<K,V> left;
// 右孩子
Entry<K,V> right;
// 父节点
Entry<K,V> parent;
// 红黑树的节点表示颜色的属性
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
// 根据给定的键、值、父节点构造一个节点，颜色是默认的黑色
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
// 获取节点的key
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
// 获取节点的value
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
// 修改并返回当前节点的value（返回的是旧的value）
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
// 判断节点相等的方法（两个节点为同一类型且key值和value值都相等时两个节点相等）
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
// 节点的哈希值计算方法
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
Entry类比较简单，实现了树节点的必要内容，提供了hashCode方法等。
TreeMap的父类和实现的接口
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.SerializableTreeMap继承自AbstractMap，AbstractMap实现了Map接口。
TreeMap实现了NavigableMap接口？
TreeMap实现了Cloneable接口
TreeMap实现了Serializable接口
构造函数
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}就不说了
属性
/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
*
* @serial
*/
// 用于保持顺序的比较器，如果为空的话使用自然顺序保持key的顺序
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;
/**
* The number of entries in the tree
*/
// 树中节点数量
private transient int size = 0;
/**
* The number of structural modifications to the tree.
*/
// ？？？
private transient int modCount = 0;
行为
下面从put/get方法开始，逐个分析TreeMap的方法。
put方法
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
// 如果根节点为null，将传入的键值对构造成根节点（根节点没有父节点，所以传入的父节点为null）
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 记录比较结果
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
// 分割比较器和可比较接口的处理
Comparator<? super K> cpr = comparator;
// 有比较器的处理
if (cpr != null) {
do {
// 记录新节点的父节点
parent = t;
// 使用比较器比较父节点和插入键值对的key值的大小
cmp = cpr.compare(key, t.key);
// 插入的key较大
if (cmp < 0)
t = t.left;
// 插入的key较小
else if (cmp > 0)
t = t.right;
// key值相等，替换并返回t节点的value（put方法结束）
else
return t.setValue(value);
} while (t != null);
}
// 没有比较器
else {
// key为null，抛出空指针异常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
// 与if里面的do while类似，只是比较的方式不同
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相同的节点才会有下面的操作
// 根据传入的键值对和找到的父节点创建新节点
Entry<K,V> e = new Entry<>(key, value, parent);
// 根据最后一次的判断结果确认新节点是父节点的左孩子还是右孩子
if (cmp < 0)
parent.left = e;
else
// 对加入新节点的树进行调整
parent.right = e;
fixAfterInsertion(e);
// 记录size和modcount
size++;
modCount++;
// 因为是插入新节点，所以返回的是null
return null;
}
首先一点通性是TreeMap的put方法和其他Map的put方法一样，向Map中加入键值对，若原先“键（key）”已经存在则替换“值（value）”，并返回原先的值。
在put(K key,V value)方法的末尾调用了fixAfterInsertion(Entry
get方法
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
get(Object key)通过key获取对应的value，它通过调用getEntry(Object key)获取节点，若节点为null则返回null，否则返回节点的value值。下面是getEntry(Object key)的内容，来看它是怎么寻找节点的。
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
// 如果有比较器，返回getEntryUsingComparator的结果
if (comparator != null)
return getEntryUsingComparator(key);
// 查找的key为null，抛出空指针
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
// 获取根节点
Entry<K,V> p = root;
// 对树进行遍历查找节点
while (p != null) {
// 把key和当前节点的key进行比较
int cmp = k.compareTo(p.key);
// key小于当前节点的key
if (cmp < 0)
// p移动到左节点上
p = p.left;
// key小于当前节点的key
else if (cmp > 0)
// p移动到右节点上
p = p.right;
// key值相等则当前节点就是要找的节点
else
return p;
}
return null;
}上面主要是处理实现了可比较接口的情况，而有比较器的情况在getEntryUsingComparator(Object key)中处理了，下面来看处理的代码。
final Entry<K,V> getEntryUsingComparator(Object key) {
K k = (K) key;
// 获取比较器
Comparator<? super K> cpr = comparator;
// 其实在调用此方法的get(Object key)中已经对比较器为null的情况进行判断，这里是防御性的判断
if (cpr != null) {
// 获取根节点
Entry<K,V> p = root;
// 遍历树
while (p != null) {
// 获取key和当前节点的key的比较结果
int cmp = cpr.compare(k, p.key);
// 查找的key值较小
if (cmp < 0)
// p“移动”到左孩子
p = p.left;
// 查找的key值较大
else if (cmp > 0)
// p“移动”到右节点
p = p.right;
// key值相等
else
// 返回找到的节点
return p;
}
}
// 没找到key值对应的节点，返回null
return null;
}更多方法就不再深入啦
应用场景
我们知道treemap的底层数据结构是红黑树，红黑树的优点是什么：插入、查找、删除效率综合来说都比二叉排序树、平衡二叉树要好一些。
与HashMap相比，TreeMap的key是有序的。
参考资料
http://www.importnew.com/16679.html
http://www.cnblogs.com/hzmark/archive/2013/01/02/TreeMap-Base.html
http://blog.csdn.net/hustyangju/article/details/27214251
https://www.nowcoder.com/questionTerminal/16ff3fe9d0e748ffb37212fdc280bef9