JDK1.8TreeMap
[toc]
概述
TreeMap也是Map接口的一种实现类，他最大的特点是迭代有序(默认按照Key值升序迭代)当然也可以设置为降序，TreeMap的内部用的是红黑树存储数组的，所以时间复杂度是O(logN)，此外TreeMap也是非线程安全的，并且TreeMap的key(value可以)值都不允许是空(key在某种情况下也可以为null，key为null的前提是传入比较器，而且这个比较器对于key是null的情况特殊处理了，那么key可以为null，但是不能通过get获取到这个值，只能通过遍历获取到对应value，这个可以通过源码看出put和get都体现了)。继承关系图如下：
image
二叉查找树&AVL树&红黑树
在了解TreeMap前先了解这三种树结构
二叉查找树
在介绍红黑树之前，先简单介绍一下排序二叉树。排序二叉树是一种特殊的二叉树，可以非常方便的对树中的节点进行排序和检索。
排序二叉树可以为孔数，如果不为空，则满足以下性质：
- 若左子树不为空，则左子树上所有的值均小于他的根节点的值
- 若右子树不为空，则右子树上所有的值均大于他的根节点的值
-
左、右子树也分别是排序二叉树。
下图即为一个排序二叉树：
image
对排序二叉树虽然可以快速搜索，但在最坏的情况下：如果插入的节点本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变为链表：所有节点只有左节点(插入节点是从大到小)；或者所有节点只有有节点(插入节点集本身是从小到大排列)。在这种情况下，排序二叉树就变成了普通的链表，其检索效率就会很差。 例如下图：
image
这种情况也是满足二叉查找树的条件，然而此时的二叉查找树已经退化为一条链表了，这样的二叉查找树的查找时间复杂度顿时变为O(n)，可想而知，我们必须不能让这种情况发生，为了解决这个问题，于是我们引申出了平衡二叉树。
平衡二叉树二叉查找树(AVL树)
平衡二叉树就是为了解决二叉叉查找树退化为链表而诞生的，平衡树具有如下特点：
- 具有二叉查找树的全部特性
- 每个节点的左子树和右子树的高度差之多等于1。例如，图一就是一颗平衡树，而图二则不是(节点右边标的是高度)。
image
对于图二，因为节点9的左孩子高度为2，右孩子的高度为0，他们之间差值超过1了。
平衡树基于这种特点就可以保证不会出现大量的节点偏向一方的情况了。于是，通过平衡树，解决了二叉查找树的缺陷，对于有n个节点的平衡树，最坏的查询时间复杂度也为O(logn)。
缺点：由于维护这种高度平衡，每一次插入、删除都要通过左旋和右旋来调整结构，非常耗时，只有对查找要求较高，插入删除不频繁才会优先考虑AVL，否则都会选择局部平衡的红黑树
红黑树
虽然平衡树解决了二叉查找树的退化链表的问题，能够把时间复杂度控制在O(logn)，不过却不是最佳的，因为平衡树要求每一个节点的左子树和右子树的高度至多等于1。这个要求是在是太严了，导致每次进行插入/删除节点时候，几乎都会破坏平衡二叉树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再一次称为平衡二叉树。
显然，如果在那种插入、删除频繁的场景中，平衡树需要频繁调整，这会是平衡树的性能大打折扣，为了解决这个问题有了红黑树，红黑树具有如下特点：
- 具有二叉查找树的特点
- 根节点为黑色的
- 每个叶子节点都是黑叔的空节点(NIL)，也就是说叶子节点不放数据。
- 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的
-
每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数组的黑色节点(即每条路径的都包含相同的黑节点)。例如下面图片(注意，图片中黑色的、空的叶子节点没有画出)
image
正是由于红黑树的这种特点，使得他能够在最坏情况下，也能在O(logn)的时间复杂度查找到某个节点。
不过如果单单在查找方面的效率，平衡树比红黑树快
所以，也可以说，红黑树是一种不大严格的平衡树。也可以说是折中方案。
红黑树确保没有一条路径会比其他路径长出两倍，因此红黑树是一种弱平衡二叉树，由于是弱平衡，在相同情况下AVL树(具有平衡条件的二叉查找树)高度低于红黑树，相对于严格的AVL树来说，他的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树
总结这三种树结构
平衡树是为了解决退化二叉查找树退化链表的情况，而红黑树为了解决平衡树在插入、删除等操作需要频繁调整的情况。
TreeMap
TreeMap：形式为tree的map，确切的说这里的tree是红黑树(red black tree)。
TreeMap实现了SortMap接口，因此是一个有序的map，表内每个元素在存储时都是按照规则排序的。
我们在使用TreeMap时，无论使用哪个方法，在内部基本都会用到TreeMap的基本元素Entry类，Entry本身的哈安逸指键值对(key-value)，这里是一个TreeMap自己定义和实现的类。从结构上看TreeMap对象就是由一个个的Entry对象所组成的，因此TreeMap的使用方法get()、put()、remove()...时，实际上都是在操作自己的一个个元素Entry。这里以TreeMap的get()方法为例：
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
这个方法就是在调用getEntry()方法，根据key值获取一个基本存储元素：Entry。
TreeMap的各个方法都在使用内部类Entry，TreeMap本身也就是由一个个Entry对象组成的，因此我们先看看这个类的内部是什么样子。
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;
boolean color = BLACK; //黑是true，红是false
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
//getKey、getValue、setValue、equals、hashCode、toString 等方法
}
TreeMap内部自定义了Entry类，这个类实现了Map.Entry接口，也就是说他是一个键值对(key-value)。
Entry 类的一共有六个成员变量：
- key 键
- value 值
- left 左节点
- right 右节点
- parent 父节点
- color 颜色
Entry类除了key和value这两个所有map都必须的变量之外。还有四个成员变量，分别是左、右、父节点，以及布尔值变量：颜色(黑是true，红是false)。 由此可以看出Entry定义的是红黑树
红黑树
红黑树的意义就在于，他是一种弱的平衡树二叉树，但他不需要那么平衡，差不多就行，这样查询也快，插入也快。
红黑树的为二叉树指定的五条规则(和上面一样)：
- 每个节点有颜色，不是红色就是黑色
- 根节点是黑色的
- 叶子节点也是黑色的null节点(叶子节点不存放数据)
- 中间节点可以是红色的，但是红色节点不能连在一起(红色节点只能跟黑色节点相连)
- (平衡的核心)从任意节点出发，到每个叶子节点，应途径数量一样的黑色节点。如图：
image
边看图边思考上面的规则，主要是第四、五两条规则，会发现他的平衡之处就在于，收到这些规则约束的二叉树，深度就是差的再多，在最坏的情况下，也只会差一倍(从根到叶子的最长的可能路径不多于最短的可能路径的两倍长)，这种二叉树大致上是平衡的。
红黑树插入节点同样要通过旋转来调整，但是调整次数比AVL树小很多，他虽然比AVL树查的慢，但是增删节点快，是一种不错的折中选择。
put方法
从整体看，TreeMap的put方法分三部分：
- 1、如果是首次添加，初始化容器，并直接返回
- 2、按照顺序直接插入新的节点
- 3、调整结构，以符合红黑树规则
public V put(K key, V value) {
Entry<K,V> t = root;
//如果根节点没有被初始化，进行初始化根节点
if (t == null) {
//如果key为null，如果比较器不允许为空，会报空指针异常
//使用比较器比较key，如果比较器为空，会使用K的比较器
compare(key, key); // type (and possibly null) check
//创建根节点
root = new Entry<>(key, value, null);
//size变为1
size = 1;
//modCount操作计数加1
modCount++;
return null;
}
//记录比较结果
int cmp;
//记录父节点
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//如果有特定的比较器
if (cpr != null) {
//有特定的比较器没有对key进行判空
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
//cmp<0说明在跟节点的左边
t = t.left;
else if (cmp > 0)
//说明在根节点的右边
t = t.right;
else
//如果比较结果相等将value放到对应entry中，返回旧的值
return t.setValue(value);
} while (t != null);
}
else {
//如果比较器是null并且key为null抛出空指针异常
//如果没有特定比较器，那么对key进行判空了
if (key == null)
throw new NullPointerException();
//获取key的默认比较器
@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
//找到相等的key放到对应位置，返回旧的值
return t.setValue(value);
} while (t != null);
}
//如果上面没有找对相等的key，那么说明是一个新的节点，那么就创建一个节点，放到最后面
Entry<K,V> e = new Entry<>(key, value, parent);
//通过cmp判断当前key与他的父节点的大小关系，用来决定放到左边还是右边
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//插入新的节点进行修复
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
注：TreeMap是通过比较器来确定元素是否相等的，如果两个key通过比较器进行比较确定是相等元素，那么就认为key是同一个，会修改对应的value值(即使是不同的key，只要比较器判定相等那么一样会修改value值的，不会因为key不同而插入新的值，而是因为key的通过比较器比较之后没有相同的key才会插入新的值)
注：如果没有传入比较器，默认使用key的自己实现的比较器，那么key不能为null，但是如果传入了比较器，并且这个比较器对于key是null的时候进行了特别处理那么key是允许为null的(这一点可以通过源码看出put和get都体现了)，但是直觉通过get(null)获取不到元素，只能通过遍历才能获取
注：value可以为null，通过源码可以看出没有限制value
按照代码顺序简单阅读以下这段put代码
初始化
put()方法首先获取TreeMap对象的根节点，这个根节点的类型就是我们最开始说的Entry类，是一个存储着键值对信息的红黑树节点。
如果发现没有根节点，说明这个TreeMap对象从来没有执行过put()方法，没有存储任意一个键值对，那么在这种情况下，把本次的put()方法呆了的键值对作为根节点，直接保存起来，直接返回，不执行后续操作
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
//如果是使用key本身的比较器需要保证key不为null，如果是传入比较器，并对key为null进行特别处理时运行key为null的
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
...后续代码
}
插入节点
在拿到根节点之后，put()方法就准备插入节点了，插入节点部分，并不关心红黑树约束条件，也就是说如果插入之后不满足红黑树的条件也没关系，调整树的结构符合红黑树这逻辑在put()方法最后面。
因此，插入节点时关注的，不在于插入前后是否符合红黑树，而在于找到插入点的位置，对于TreeMap而言，一切节点都是按照顺序存储的，找插入点的位置就是找新节点排在什么位置，他应该插入到左边节点比他小，而右边节点比他大的位置处，前提有一套计算顺序规则，代码如下：
//...前面的代码
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);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
//如果找到相等情况，将新的value更新，直接返回
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;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
//如果找到相等情况，将新的value更新，直接返回
return t.setValue(value);
} while (t != null);
}
//创建新的节点
Entry<K,V> e = new Entry<>(key, value, parent);
//插入到指定位置
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//...后序代码
如果有比较器，就是用特定的比较器进行比较，如果没有就使用key的默认比较器(使用key默认比较器，key不能为null)
调整结构
这部分TreeMap抽出一个单独方法，用以调整新节点之后的树，调整成红黑树
// ...已插入新节点
fixAfterInsertion(e);//调整树结构
size++;
modCount++;
return null;
插入新的节点默认是红色的，然后根据父节点和uncle(叔叔节点)来判断左旋右旋。代码有点难看懂
private void fixAfterInsertion(Entry<K,V> x) {
//节点默认是红色的
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
get()方法
get方法其实就在在红黑树中进行搜索，分为两种情况：
- 有指定比较器，那么就是用指定比较器(此时指定比较器如果对key为null进行特别处理，那么key是可以为null)
- 没有特定比较器，那么使用key默认比较器，key不允许为null
查询时间复杂度是O(logn)
用cmp记录比较结构，cmp=0说明该节点就是要查找的结果，返回，cmp<0就在左子树查找，cmp>0在右子树查找
代码如下：
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)
//存在特定比较器使用特定比较器进行比较
return getEntryUsingComparator(key);
if (key == null)
//如果不存在特定比较器，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;
}
remove()方法
删除方法是先查找到对应节点，然后进行删除，deleteEntry()方法就是为了删除节点，比较复杂看不太懂
public V remove(Object key) {
//先调用get方法获取该节点
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
//删除节点
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.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;
}
}
}
