简介
TreeMap是一个有序的key-value集合，它是通过红黑树实现的。它的每一个元素是一个key-value对，TreeMap类声明如下：
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
它继承于AbstractMap，实现了NavigableMap、Cloneable、 Serializable等接口。
TreeMap实现了NavigableMap接口，NavigableMap接口中定义了很多用于导航的方法，比如返回小于（大于）某个key的节点集合，返回具有最大（最小）key的节点等；实现了Cloneable接口，能被克隆；实现了Serializable接口，因此它支持序列化，能够通过序列化传输。
TreeMap是非线程安全的，只是用于单线程环境下。
TreeMap源码详解
TreeMap有如下几个成员变量：
// 自定义的比较器，用于给TreeMap的元素排序 private final Comparator<? super K> comparator; // 红黑树的根节点 private transient Entry<K,V> root; // 节点数目 private transient int size = 0; // TreeMap结构的修改次数，用于fail-fast机制 private transient int modCount = 0;
TreeMap中的节点都被封装成为了Entry类型数据：
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;
// 节点颜色，默认为BLACK
boolean color = BLACK;
// 构造方法
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
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;
}
}
TreeMap有如下四个构造方法：
// 无参构造方法，没有指定比较器，这时，节点顺序依赖于对key的自然排序
public TreeMap() {
comparator = null;
}
// 指定比较器的构造方法，这时，节点顺序依赖于该比较器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// 根据其他Map来创建TreeMap，没有指定比较器
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// 根据其他SortedMap来创建TreeMap，比较器设置为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方法、get方法和remove方法。
put(K key, V value)方法
public V put(K key, V value) {
Entry<K,V> t = root;
// 若红黑树为空，则设置根节点
if (t == null) {
// 类型检查
compare(key, key); // type (and possibly null) check
// 创建根节点
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;
cmp = cpr.compare(key, t.key);
// 如果key < 根节点，则在左子树查找插入位置
if (cmp < 0)
t = t.left;
// 如果key > 根节点，则在右子树查找插入位置
else if (cmp > 0)
t = t.right;
// 否则，重置根节点的值
else
return t.setValue(value);
} while (t != null);
}
// 如果没有指定比较器，则使用key进行自然排序
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 将key强制转换为Comparable<? super K>对象
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
// 如果key < 根节点，则在左子树查找插入位置
if (cmp < 0)
t = t.left;
// 如果key > 根节点，则在右子树查找插入位置
else if (cmp > 0)
t = t.right;
// 否则，重置根节点的值
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
// 如果key < 红黑树中最小节点parent，则新节点成为parent的左节点
if (cmp < 0)
parent.left = e;
// 如果key > 红黑树中最小节点parent，则新节点成为parent的右节点
else
parent.right = e;
// 节点插入完后，需要调整红黑树的高度和颜色
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
在插入键值对时，程序分为了两种情况：有比较器和没有比较器。若有比较器的话，则使用该比较器来进行排序，否则，通过key来进行自然排序。若是使用key来做自然排序的话，key要实现Comparable接口，才可以作为比较器，Java中的String、Integer等都实现了该接口，若我们使用自定义类来作为TreeMap的key，如果我们没有指定比较器，那自定义类要实现Comparable接口，才可以进行排序，否则，在插入元素时，会抛出ClassCastException异常。
Comparable接口很简单，它只有一个方法：
public interface Comparable<T> {
public int compareTo(T o);
}
这样，在通过自定义key进行排序时，就可以通过key的compareTo方法来进行比较排序。
同时，在添加元素时，key不可以为null，在put方法中调用了一个compare方法，该方法会对key进行类型检查，若key无法强制转换为Comparable类型，则会抛出ClassCastException异常，若key为null，则会抛出NullPointerException异常。
但是，value是可以为null的。添加，获取元素时，不会对value进行类型检查。
get(Object key)方法
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
get(Object key)方法调用了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);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 若没有比较器，则通过key来比较
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
// 若k < p，则在左子树寻找
if (cmp < 0)
p = p.left;
// 若k > p，则在右子树寻找
else if (cmp > 0)
p = p.right;
// 否则，返回p
else
return p;
}
// 返回null
return null;
}
若有比较器，则通过getEntryUsingComparator方法来处理：
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
// 若k < p，则在左子树寻找
if (cmp < 0)
p = p.left;
// 若k > p，则在右子树寻找
else if (cmp > 0)
p = p.right;
// 否则，返回p
else
return p;
}
}
return null;
}
可以看到，获取元素也是分为了两种情况：有比较器和没有比较器。在两种情况下，寻找元素的逻辑几乎一致。
get(Object key)方法调用了getEntry(Object key)方法之后，要判断getEntry(Object key)方法的返回值是否为null，若为null，则表明没有与key对应的节点，则get(Object key)方法返回null，否则，返回p.value。
remove(Object key)方法
public V remove(Object key) {
// 获取key对应的节点
Entry<K,V> p = getEntry(key);
// 节点不存在
if (p == null)
return null;
V oldValue = p.value;
// 删除节点
deleteEntry(p);
return oldValue;
}
该方法是先找到与key对应的节点，然后调用deleteEntry方法来删除节点：
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
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;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
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;
}
}
}
TreeMap其他相关方法
因为TreeMap允许value为null，所以要判断一个key在TreeMap中是否存在，是不可以用get(Object)方法来判断的，我们可以用containsKey(Object)方法来判断：
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
我们知道，getEntry(Object)方法会返回key对应的节点，若key不存在，则肯定返回的是null，若key存在，则无论value是否为null，key对应的节点都不为null。
我们下面来看一个TreeMap的导航方法：
lowerEntry(K key)方法
// 返回比指定key小的最大key的entry
public Map.Entry<K,V> lowerEntry(K key) {
return exportEntry(getLowerEntry(key));
}
该方法会先调用getLowerEntry(K)方法来获取节点。然后通过exportEntry方法来新建一个entry并返回。
// 返回比指定key小的最大key的entry节点
final Entry<K,V> getLowerEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
// 如果key > 根节点，则在右子树查询
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
}
// 否则，则在左子树查询
else {
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
// 若entry为null，则直接返回null，否则新建一个具有相同键值对的map并返回
return (e == null) ? null :
new AbstractMap.SimpleImmutableEntry<>(e);
}
clear()方法
// 清空map，并把根节点置为null
public void clear() {
modCount++;
size = 0;
root = null;
}
对HashSet和TreeSet的源码就不再进行解析了，它们分别是基于HashMap和TreeMap实现的，只是对应的节点中只有key，而没有value。