java.util.TreeMap源码解析
2018-02-27 本文已影响4人
sunpy
所属包
package java.util;
继承与实现关系
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 = null;
/**
* 红黑树中节点的个数
*/
private transient int size = 0;
/**
* 对树结构修改的次数
*/
private transient int modCount = 0;
//定义规则红色就是false
private static final boolean RED = false;
//定义规则黑色就是true
private static final boolean BLACK = true;
红黑树数据结构
/**
* 定义了红黑树中节点的数据结构
*
*/
static final class Entry<K,V> implements Map.Entry<K,V> {
//键,也是红黑树排序的依据
K key;
//值
V value;
//红黑树中节点的左孩子节点
Entry<K,V> left = null;
//红黑树中节点的右孩子节点
Entry<K,V> right = null;
//红黑树中节点的父节点
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;
}
}
构造方法
/**
* 使用键的自然顺序构造一个新的、空的红黑树映射
*/
public TreeMap() {
comparator = null;
}
/**
* 构造一个新的、空的树映射，该映射根据给定比较器进行排序。
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 使用键的自然顺序构造一个新的、空的红黑树映射
* 将Map集合m中的数据都放到红黑树对应的节点中
*
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
/**
* 构造一个包含相同映射并使用与指定排序映射相同顺序的新树映射。 该方法运行时
* 间是线性时间。
*/
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) {
}
}
putAll方法
/**
* 将指定映射中的所有映射关系复制到此映射中。
* 这些映射关系将替换此映射所有当前为指定映射的所有键所包含的映射关系。
*/
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
//当前TreeMap的大小为0，并且传入参数map大小不为0,并且map是已排序
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
//获取map本身的比较器
Comparator c = ((SortedMap)map).comparator();
//如果传入参数map本身的比较器和TreeMap的比较器相同，那么就将map中的元素拷贝到TreeMap中
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// 调用AbstractMap中的putAll();
// AbstractMap中的putAll()又会调用到TreeMap的put()
super.putAll(map);
}
buildFromSorted方法
/**
* 重载方法，将输入参数map的大小作为TreeMap的大小
*/
private void buildFromSorted(int size, Iterator it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
this.size = size;
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
it, str, defaultVal);
}
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
/*
* 根是最中间的元素。
* 要得到它，我们必须首先递归地构造整个左子树，以便获取其所有元素。
* 然后，我们可以继续使用正确的子树。
* lo和hi参数是拉出当前子树的迭代器或流的最小和最大索引。
* 它们实际上没有索引，我们只是按顺序执行，确保按相应的顺序提取项目。
*/
//如果最小索引小于最大索引，返回null
if (hi < lo) return null;
//求出中间位置，最小索引加上最大索引右移一位（除以2）
int mid = (lo + hi) >>> 1;
Entry<K,V> left = null;
if (lo < mid)
//递归构造左子树
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
// extract key and/or value from iterator or stream
K key;
V value;
if (it != null) {
if (defaultVal==null) {
//如果默认值为空，使用Map的后继索引获取entry节点
Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
//获取entry节点的键
key = entry.getKey();
//获取entry节点的值
value = entry.getValue();
} else {
//如果默认值不为空，那么迭代器获取键
key = (K)it.next();
//将默认值作为值
value = defaultVal;
}
} else {
//使用对象流，读取流中的对象，作为键
key = (K) str.readObject();
//如果默认值不为空，那么值就为默认值，否则就使用对象流中读取的对象值作为值
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
//构造一个中间节点
Entry<K,V> middle = new Entry<>(key, value, null);
if (level == redLevel)
middle.color = RED;
if (left != null) {//如果左子树不为空
//更新中间节点的左子树
middle.left = left;
//更新左子树的父节点
left.parent = middle;
}
if (mid < hi) {
//递归构造右子树
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
//更新每次取中间节点的右子树
middle.right = right;
//更新每次右子树的父节点
right.parent = middle;
}
return middle;
}
方法
containsKey方法
/**
* 该方法如果包含了指定的键，就返回true
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
getEntry方法
//通过输入的键key获取红黑树中和其相同的key，如果没有就返回null
final Entry<K,V> getEntry(Object key) {
// 如果比较器不为空，那么使用比较器的比较规则获取节点Entry
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
//此时不存在比较器，那么就使用自然规则，创建比较器k
Comparable<? super K> k = (Comparable<? super K>) key;
//由于root是全局变量，是共享的，所以定义临时变量来存储
Entry<K,V> p = root;
//从根节点p开始，因为本身红黑树就是二叉排序树的局部平衡化而来的，所以采用二叉排序树的遍历方式
while (p != null) {
//使用自然规则进行比较遍历到的节点值和传入的键key是否相等
int cmp = k.compareTo(p.key);
//如果比较结果小于0，说明key小于根节点的key，那么就开始遍历左子树
if (cmp < 0)
p = p.left;
else if (cmp > 0)
//如果比较结果大于0，说明key大于根节点的key，那么就开始遍历右子树
p = p.right;
else
//如果等于0.说明key等于根节点的key，说明找到可以直接返回了
return p;
}
return null;
}
getEntryUsingComparator方法
/**
* 带自定义比较规则的比较器获取节点Entry
*/
final Entry<K,V> getEntryUsingComparator(Object key) {
K k = (K) key;
//使用泛型的上界构造临时变量cpr，并赋值
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
//从根节点开始遍历
while (p != null) {
//使用比较器的比较规则来判断遍历到的节点值和传入的键key是否相等
int cmp = cpr.compare(k, p.key);
//如果比较结果小于0，说明key小于根节点的key，那么就开始遍历左子树
if (cmp < 0)
p = p.left;
else if (cmp > 0)
//如果比较结果大于0，说明key大于根节点的key，那么就开始遍历右子树
p = p.right;
else
//如果等于0.说明key等于根节点的key，说明找到可以直接返回了
return p;
}
}
return null;
}
get方法
/**
* 返回指定键所映射的值，如果对于该键而言，此映射不包含任何映射关系，则返回
* null。
*/
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
comparator方法
//获取比较器
public Comparator<? super K> comparator() {
return comparator;
}
put方法
/**
* 将指定值与此映射中的指定键进行关联。
*/
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);
//红黑树大小为1
size = 1;
//修改了一次红黑树，所以修改次数加1
modCount++;
return null;
}
//变量作为比较结果
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//如果比较器不为空，那么就按照指定的比较规则的比较器进行比较
if (cpr != null) {
do {
//遍历找到传入参数键key的父节点
parent = t;
//比较传入参数键key和红黑树遍历节点的key
cmp = cpr.compare(key, t.key);
//如果比较结果小于0，说明key小于根节点的key，那么就开始遍历左子树
if (cmp < 0)
t = t.left;
//如果比较结果大于0，说明key大于根节点的key，那么就开始遍历右子树
else if (cmp > 0)
t = t.right;
else
//如果比较结果等于0,那么就将原来的值进行更新呗
return t.setValue(value);
} while (t != null);//遍历的条件就是直到遍历到叶子节点(此处的叶子节点指的是null的点)为止
}
else {//如果比较器为空，那么就按照自然规则的比较器进行比较
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//遍历找到传入参数键key的父节点
parent = t;
//比较传入参数键key和红黑树遍历节点的key
cmp = k.compareTo(t.key);
//如果比较结果小于0，说明key小于根节点的key，那么就开始遍历左子树
if (cmp < 0)
t = t.left;
//如果比较结果大于0，说明key大于根节点的key，那么就开始遍历右子树
else if (cmp > 0)
t = t.right;
else
//如果比较结果等于0,那么就将原来的值进行更新呗
return t.setValue(value);
} while (t != null);//遍历的条件就是直到遍历到叶子节点(此处的叶子节点指的是null的点)为止
}
//将输入的键值对封装成红黑树节点Entry，设置父节点为parent
Entry<K,V> e = new Entry<>(key, value, parent);
//如果比较结果小于0，说明key小于根节点的key，那么就开始遍历左子树
if (cmp < 0)
parent.left = e;
else
//如果比较结果大于0，说明key大于根节点的key，那么就开始遍历右子树
parent.right = e;
//前面使用二叉排序树的方式插入，为了满足红黑树性质，需要进行旋转和变色操作
fixAfterInsertion(e);
//插入值后长度加1
size++;
//插入值相当于修改树一次，所以次数加1
modCount++;
return null;
}
fixAfterInsertion方法：调整插入节点之后，红黑树结构调整
//调整红黑树的结构和颜色
private void fixAfterInsertion(Entry<K,V> x) {
//默认插入节点的颜色为红色
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
//判断x的父节点p是p的父节点pp的左孩子
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//获取x的父节点的父节点也就是祖父节点pp的右孩子y，就是父节点p的右兄弟节点，也是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变为祖父节点，可以看出从下往上遍历的
x = parentOf(parentOf(x));
} else {//否则叔叔的节点为黑色，黑叔情况
//x是父节点的右孩子
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
//左旋转父节点
rotateLeft(x);
}
//设置父节点的颜色为黑色
setColor(parentOf(x), BLACK);
//设置祖父节点的颜色为红色
setColor(parentOf(parentOf(x)), RED);
//右旋转祖父节点
rotateRight(parentOf(parentOf(x)));
}
} else {//判断x的父节点p是p的父节点pp的右孩子
//获取x的祖父节点的左孩子，就是y的左叔
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变为祖父节点，可以看出从下往上遍历的
x = parentOf(parentOf(x));
} else {//否则叔叔节点为黑色，黑叔情况
//x是父节点的左孩子
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;
}
remove方法
/**
* 如果此 TreeMap 中存在该键的映射关系，则将其删除
*/
public V remove(Object key) {
//先查询传入参数键key是否在红黑树的节点Entry中
Entry<K,V> p = getEntry(key);
//如果不存在则返回null
if (p == null)
return null;
//获取节点p的旧值
V oldValue = p.value;
//删除节点p
deleteEntry(p);
//返回旧值
return oldValue;
}
deleteEntry方法
/**
* 删除节点p，然后将红黑树进行局部平衡化
*/
private void deleteEntry(Entry<K,V> p) {
//删除节点了，就修改树结构一次，所以次数减1
modCount++;
//红黑树的大小减1
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
//当节点p的左右孩子节点都不为null时情况
if (p.left != null && p.right != null) {
//获取要删除的节点p的替换者s
Entry<K,V> s = successor(p);
//将s的键赋值给p的键
p.key = s.key;
//将s的值赋值给p的值
p.value = s.value;
//将s赋值给p
p = s;
}
//当节点p只有一个孩子时，获取对应的单个孩子
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//如果单个孩子不为空
if (replacement != null) {
//设置单个孩子的父节点
replacement.parent = p.parent;
//如果删除节点的父节点为null，那么p为根节点
if (p.parent == null)
//直接将单个孩子作为根节点
root = replacement;
//如果p为父节点的左孩子节点
else if (p == p.parent.left)
//直接将单个孩子作为p的父节点的左孩子
p.parent.left = replacement;
//如果p为父节点的右孩子节点
else
//直接将单个孩子作为p的父节点的右孩子
p.parent.right = replacement;
//将p的左孩子，右孩子，父节点都设置为null
p.left = p.right = p.parent = null;
//只有当删除节点为黑色时才需要进行颜色的调整
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
//由于p的父节点为null，说明p为根节点，而本身子节点都为null，那么根节点就为null
root = null;
} else { //如果单个孩子节点为空，说明没有孩子节点了。p的父节点不为空，说明p节点是叶子节点
//如果删除的节点p是黑色需要进行颜色调整
if (p.color == BLACK)
fixAfterDeletion(p);
//如果p的父节点不为空
if (p.parent != null) {
//判断p为父节点的左孩子节点
if (p == p.parent.left)
//p本身是其父节点的左孩子节点，而且本身是叶子节点，直接将p的父节点的左孩子节点设置为null即可
p.parent.left = null;
//判断p为父节点的右孩子节点
else if (p == p.parent.right)
//p本身是其父节点的右孩子节点，而且本身是叶子节点，直接将p的父节点的右孩子节点设置为null即可
p.parent.right = null;
//将p的父节点设置为null
p.parent = null;
}
}
}
successor方法：获取删除的节点替换者
/**
* 获取删除节点的替换者
*/
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
//如果t为空，那么后继节点返回null
if (t == null)
return null;
//如果t的右孩子不为null
else if (t.right != null) {
//获取t的右孩子节点p
Entry<K,V> p = t.right;
//遍历t的右子树中最小的节点p
while (p.left != null)
p = p.left;
return p;
} else {
//获取t的父节点
Entry<K,V> p = t.parent;
//获取节点t
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
fixAfterDeletion方法：删除节点后，红黑树为了满足性质需要调整结构
//删除节点后颜色的调整
private void fixAfterDeletion(Entry<K,V> x) {
//x不为根节点并且x的颜色为黑色
while (x != root && colorOf(x) == BLACK) {
//节点x为父节点的左孩子节点
if (x == leftOf(parentOf(x))) {
//获取x的右兄弟节点sib
Entry<K,V> sib = rightOf(parentOf(x));
//如果兄弟节点为红色
if (colorOf(sib) == RED) {
//兄弟节点调整为黑色
setColor(sib, BLACK);
//父节点调整为红色
setColor(parentOf(x), RED);
//左旋转父节点
rotateLeft(parentOf(x));
//兄弟节点为父节点的右孩子
sib = rightOf(parentOf(x));
}
//判断兄弟节点的左孩子颜色为黑色并且兄弟节点的右孩子颜色为黑色
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
//设置兄弟节点的颜色为红色
setColor(sib, RED);
x = parentOf(x);
} else {
//如果兄弟节点的右孩子颜色为黑色
if (colorOf(rightOf(sib)) == BLACK) {
//调整兄弟节点的左孩子为黑色
setColor(leftOf(sib), BLACK);
//调整兄弟节点的颜色为红色
setColor(sib, RED);
//右旋转兄弟节点
rotateRight(sib);
//兄弟节点为父节点的右孩子
sib = rightOf(parentOf(x));
}
//设置兄弟节点的颜色为父节点的颜色
setColor(sib, colorOf(parentOf(x)));
//设置父节点的颜色为黑色
setColor(parentOf(x), BLACK);
//设置兄弟节点的右孩子为黑色
setColor(rightOf(sib), BLACK);
//左旋转父节点
rotateLeft(parentOf(x));
x = root;
}
} else {
//获取x的左兄弟节点sib
Entry<K,V> sib = leftOf(parentOf(x));
//判断左兄弟节点的颜色为红色
if (colorOf(sib) == RED) {
//调整左兄弟节点为黑色
setColor(sib, BLACK);
//调整父节点颜色为红色
setColor(parentOf(x), RED);
//右旋转父节点
rotateRight(parentOf(x));
//左兄弟节点为父节点的左孩子
sib = leftOf(parentOf(x));
}
//判断兄弟节点的右孩子为黑色并且兄弟节点的左孩子为黑色
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
//设置兄弟节点颜色为红色
setColor(sib, RED);
x = parentOf(x);
} else {
//判断兄弟节点的左孩子节点颜色为黑色
if (colorOf(leftOf(sib)) == BLACK) {
//设置兄弟节点的右孩子颜色为黑色
setColor(rightOf(sib), BLACK);
//设置兄弟节点的颜色为红色
setColor(sib, RED);
//左旋转兄弟节点
rotateLeft(sib);
//左兄弟为父节点的左孩子节点
sib = leftOf(parentOf(x));
}
//设置左兄弟节点颜色为父节点的颜色
setColor(sib, colorOf(parentOf(x)));
//设置父节点颜色为黑色
setColor(parentOf(x), BLACK);
//设置兄弟节点的左孩子为黑色
setColor(leftOf(sib), BLACK);
//右旋转父节点
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
阅读总结
（1）TreeMap采用红黑树数据结构设计的。
（2）如果不传入比较器Comparator，那么就按照自然顺序进行值的比较。
（3）如果传入自定义的比较器Comparator，那么就按照自定义的规则进行值的比较。
（4）至于增加方法、删除方法，都是红黑树本身数据结构特点的操作，变色，旋转
（5）至于查询值，遍历红黑树，采用非递归方式遍历二叉排序树。
-----------------------------该源码为jdk1.7版本的
