# TreeMap源码
<a name="GtYlJ"></a>
# 简介
听名字就知道，TreeMap 是由Tree 和 Map 集合有关的，没错，TreeMap 是由红黑树实现的有序的 key-value 集合。
```java
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
```
<br />TreeMap 首先继承了 AbstractMap 抽象类，表示它具有散列表的性质，也就是由 key-value 组成。<br /> 其次 TreeMap 实现了 NavigableMap 接口，该接口支持一系列获取指定集合的导航方法，比如获取小于指定key的集合。<br /> 最后分别实现 Serializable 接口以及 Cloneable 接口，分别表示支持对象序列化以及[对象克隆](https://www.cnblogs.com/ysocean/p/8482979.html)。
<a name="aoVC0"></a>
# 字段定义
```java
/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
*
* @serial
*/
private final Comparator<? super K> comparator;
```
可以看上面的英文注释，Comparator 是用来维护treemap集合中的顺序，如果为null，则按照key的自然顺序。<br /> Comparator 是一个接口，**排序时需要实现其 compare 方法，该方法返回正数，零，负数分别代表大于，等于，小于**。那么怎么使用呢？这里举个例子：<br /> 这里有一个Person类，里面有两个属性pname，page，我们将该person对象放入ArrayList集合时，需要对其按照年龄进行排序。
```java
package com.ys.test;
/**
* Create by YSOcean
*/
public class Person {
private String pname;
private Integer page;
public Person() {
}
public Person(String pname, Integer page) {
this.pname = pname;
this.page = page;
}
public String getPname() {
return pname;
}
public void setPname(String pname) {
this.pname = pname;
}
public Integer getPage() {
return page;
}
public void setPage(Integer page) {
this.page = page;
}
@Override
public String toString() {
return "Person{" +
"pname='" + pname + '\'' +
", page=" + page +
'}';
}
}
```
排序代码：
```java
List<Person> personList = new ArrayList<>();
personList.add(new Person("李四",20));
personList.add(new Person("张三",10));
personList.add(new Person("王五",30));
System.out.println("原始顺序为："+personList.toString());
Collections.sort(personList, new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
//升序
//return o1.getPage()-o2.getPage();
//降序
return o2.getPage()-o1.getPage();
//不变
//return 0
}
});
System.out.println("排序后顺序为："+personList.toString());
```
结果：
```java
原始顺序为：[Person{pname='李四', page=20}, Person{pname='张三', page=10}, Person{pname='王五', page=30}]
排序后顺序为：[Person{pname='王五', page=30}, Person{pname='李四', page=20}, Person{pname='张三', page=10}]
```
<a name="y0YuM"></a>
## Entry
```java
private transient Entry<K,V> root;
```
```java
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
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
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
*/
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;
}
}
```
<a name="op5MV"></a>
## 主要字段
```java
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
```
相信对[红黑树](https://www.cnblogs.com/ysocean/p/8004211.html)这种数据结构了解的人，一看这几个字段就明白了，这也印证了前面所说的TreeMap底层有红黑树这种数据结构。
```java
/**
* The number of entries in the tree
*/
private transient int size = 0;
```
用来表示entry的个数，也就是key-value的个数。
```java
/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;
```
基本上前面讲的在ArrayList,LinkedList,HashMap等线程不安全的集合都有此字段，用来实现Fail-Fast 机制，如果在迭代这些集合的过程中，有其他线程修改了这些集合，就会抛出ConcurrentModificationException异常。
```java
private static final boolean RED = false;
private static final boolean BLACK = true;
```
<a name="gQwFt"></a>
# 构造函数
**无参构造**
```java
public TreeMap() {
comparator = null;
}
```
将比较器 comparator 置为 null，表示按照key的自然顺序进行排序。<br />**带比较器的构造函数**
```java
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
```
需要自己实现Comparator。<br />**构造包含指定map集合的元素**
```java
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
```
使用该构造器创建的TreeMap,会默认插入m表示的集合元素，并且comparator表示按照自然顺序进行插入。<br />**带 SortedMap的构造函数**
```java
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) {
}
}
```
和上面带Map的构造函数不一样，map是无序的，而SortedMap 是有序的，使用 buildFromSorted() 方法将SortedMap集合中的元素插入到TreeMap 中。
<a name="j9l52"></a>
# 添加元素
```java
//添加元素
public V put(K key, V value) {
TreeMap.Entry<K,V> t = root;
//如果根节点为空，即TreeMap中一个元素都没有，那么设置新添加的元素为根节点
//并且设置集合大小size=1,以及modCount+1，这是用于快速失败
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new TreeMap.Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
TreeMap.Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//如果比较器不为空，即初始化TreeMap构造函数时，有传递comparator类
//那么插入新的元素时，按照comparator实现的类进行排序
if (cpr != null) {
//通过do-while循环不断遍历树，调用比较器对key值进行比较
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
//遇到key相等，直接将新值覆盖到原值上
return t.setValue(value);
} while (t != null);
}
//如果比较器为空，即初始化TreeMap构造函数时，没有传递comparator类
//那么插入新的元素时，按照key的自然顺序
else {
//如果key==null，直接抛出异常
//注意，上面构造TreeMap传入了Comparator，是可以允许key==null
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
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);
}
//找到父亲节点，根据父亲节点创建一个新节点
TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//修正红黑树（包括节点的左旋和右旋，具体可以看我Java数据结构和算法中对红黑树的介绍）
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
```
添加元素，如果初始化TreeMap构造函数时，没有传递comparator类，是不允许插入key==null的键值对的，相反，如果实现了Comparator，则可以传递key=null的键值对。<br /> 另外，当插入一个新的元素后（除了根节点），会对TreeMap数据结构进行修正，也就是对红黑树进行修正，使其满足红黑树的几个特点，具体修正方法包括改变节点颜色，左旋，右旋等操作，这里我不做详细介绍了。
<a name="Gh2sD"></a>
# 删除元素
<a name="mo9GS"></a>
## 根据key删除
```java
public V remove(Object key) {
//根据key找到该节点
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
//获得该节点的旧值
V oldValue = p.value;
//调用deleteEntry(p)删除该节点
deleteEntry(p);
return oldValue;
}
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的值设置为s
p.key = s.key;
p.value = s.value;
//p指向s
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
//得到p的子节点作为替代节点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//如果replacement != null
if (replacement != null) {
// Link replacement to parent
//将替代节点的parent设置为上文的s.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节点的连接
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
//TreeMap中只有待删除的节点，直接返回null
} 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;
}
}
}
```
删除节点分为四种情况：<br /> 1、根据key没有找到该节点：也就是集合中不存在这一个节点，直接返回null即可。<br /> 2、根据key找到节点，又分为三种情况：<br /> ①、待删除节点没有子节点，即为叶子节点：直接删除该节点即可。<br /> ②、待删除节点只有一个子节点：那么首先找到待删除节点的子节点，然后删除该节点，用其唯一子节点顶替该节点。<br /> ③、待删除节点有两个子节点：首先找到该节点的中序后继节点，然后把这个后继节点的内容复制给待删除节点，然后删除该中序后继节点，删除过程又转换成前面①、②两种情况了，这里主要是找到中序后继节点，相当于待删除节点的一个替身。
<a name="ACK0s"></a>
# 查找元素
<a name="nvOtF"></a>
## 根据key查找
```java
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
//如果初始化时定义了比较器，调用getEntryUsingComparator(key)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
//未定制比较器
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
//定制比较器的查找
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);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
```
<a name="cTcEX"></a>
# 遍历元素
通常有下面两种方法，第二种方法效率要快很多。
```java
TreeMap<String,Integer> map = new TreeMap<>();
map.put("A",1);
map.put("B",2);
map.put("C",3);
//第一种方法
//首先利用keySet()方法得到key的集合，然后利用map.get()方法根据key得到value
Iterator<String> iterator = map.keySet().iterator();
while(iterator.hasNext()){
String key = iterator.next();
System.out.println(key+":"+map.get(key));
}
//第二种方法
Iterator<Map.Entry<String,Integer>> iterator1 = map.entrySet().iterator();
while(iterator1.hasNext()){
Map.Entry<String,Integer> entry = iterator1.next();
System.out.println(entry.getKey()+":"+entry.getValue());
}
```
