TreeMap在java中，是基于红黑树的原理实现的（红黑树的原理请参考红黑树（red black tree）-分分钟钟被安排地明明白白），其原理是一棵有条件的平衡二叉查询树。节点定义包含了左右儿子节点，父节点，颜色标识。源码如下：
/**
* 红黑树节点
*/
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;
}
......
}TreeMap属性主要属性包括，root根节点，comparator元素比较器，size集合元素大小。其源码如下：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
/**
* 元素比较器
*/
private final Comparator<? super K> comparator;
/**
* 根节点
*/
private transient Entry<K,V> root;
/**
* 集合元素大小
*/
private transient int size = 0;
/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;
......
}在添加元素时，步骤如下：
- 判断root根节点是否为空，如果为空则设置为root节点。
- 根据指定的比较器，或者key实现的comparator比较器，比较key的大小。如果存在key对应的原色，则修改value值。
- 添加元素，根据comparator比较器比较的结果，添加到对应的儿子节点位置。如果破坏了红黑树的特性，就需要调用方法fixAfterInsertion对元素进行节点旋转和颜色翻转（红黑树节点旋转和颜色翻转请参考红黑树（red black tree）-分分钟钟被安排地明明白白）。其源码如下：
/**
* 添加元素
*/
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
// root根节点为空，设置为root节点
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 如果比较器不为空，则根据指定的比较器比较元素的key，如果存在对应的key就修改value值
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 {
if (key == null)
throw new NullPointerException();
// 如果比较器为空，使用key实现的比较器比较元素的key，如果存在对应的key就修改 value值
@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);
}
// 添加新的元素
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 如果破坏了红黑树特性，则进行节点旋转和颜色转换操作
fixAfterInsertion(e);
size++;
modCount++;
return null;
}源码中，方法 private void fixAfterInsertion(Entry<K,V> x)，定义了红黑树的节点旋转和颜色转换操作（节点旋转和颜色转换可以参考红黑树（red black tree）-分分钟钟被安排地明明白白）。源码如下：
/** From CLR */
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)));
// y节点（为添加节点X的父级节点和右侧父级节点的兄弟节点）存在并且为红色
if (colorOf(y) == RED) {
// 节点X的父级节点和y节点都是红色，祖父节点为黑色，属于红黑树中转换颜色情形，直接颜色转换即可
// 祖父节点设置为红色，父级节点和父级节点的兄弟节点设置为黑色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
// while 循环继续判断祖父级节点
x = parentOf(parentOf(x));
} else {
// 添加节点x属于，左儿子-右子树情形，需要进行双旋转
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
// 左旋
rotateLeft(x);
}
// 添加节点x属于，左儿子-左子树情形，需要进行单旋转
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
// 右旋
rotateRight(parentOf(parentOf(x)));
}
}
// 添加元素属于右儿子-左子树或者右儿子-右子树两种情形
else {
// 添加节点X的父级节点和左侧父级节点的兄弟节点都是红色，祖父节点为黑色
// 属于红黑树中转换颜色情形，直接颜色转换即可
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 {
// 添加节点x属于，右儿子-左子树情形，需要进行双旋转
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
// 右旋
rotateRight(x);
}
// 添加节点x属于，右儿子-右子树情形，需要进行单旋转
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
// 左旋
rotateLeft(parentOf(parentOf(x)));
}
}
}
// 根节点为黑色
root.color = BLACK;
}rotateLeft方法定义了TreeMap中节点左旋的操作，其情形如下：
左儿子-右子树情形的双旋转，如图-2：
右儿子-右子树的单旋转，如图-3：
其源码如下：
/** From CLR */
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}retateRight定义了TreeMap中节点右旋的操作，其情形如下：
左儿子-左子树情形，如图-4：
右儿子-左子树情形，如图-5：
retateRight源码如下：
/** From CLR */
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/13637.html
