源码分析:
通过查看源码可以知道其实现以及继承。
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{}
在开头其定义了一些成员变量,在底层因为TreeMap是呈现红黑树结构,所以每个节点都具有树的特征。
//比较器,通过它来决定存储顺序
private final Comparator<? super K> comparator;
//根节点,
private transient Entry<K,V> root;
/**
* 树中的节点个数
*/
private transient int size = 0;
/**
* 修改次数,防止并发修改
*/
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;
//颜色,初始化为黑色,但是后序会将其改为起始红色,因为红黑树规定,开始时每个节点是红色
boolean color = BLACK;
...
}
查看其构造其如下:
//空参构造,此时不设置比较器
public TreeMap() {
comparator = null;
}
//有参构造一,此时需要传入比较器设置比较器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//可以传入已有的map,但是不设置比较器依旧置null
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
//它允许用户快速地将一个已排序的映射转换为TreeMap,而不需要手动将每个元素插入到新的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 | ClassNotFoundException cannotHappen) {
}
}
插入过程:
一般我们调用的是如下put方法,在底层会去调用一个三参构造方法
public V put(K key, V value) {
return put(key, value, true);
}
该重载方法有三个,1:键,2:值,3是否覆盖:true是覆盖,false则是保留,这和hashmap刚好反过来,hashMap中定义的是onlyIfAbsent,表示是否保留和此处相反。
这里有个细节,就是TreeMap如果不初始化比较器,会将其置为null,那他的默认比较从何而来?那么此时会使用key进行比较,首先会假定其已经实现了Comparable接口,然后尝试调用其compareTo方法,但是你会发现TreeMap里面从头都没有重写compareTo方法,其实这个时候如果这个键是String,他会String类型中已经重写的compareTo方法,实现比较。
当然也存在使用一个没有实现Comparable接口的key进行比较,如果尝试执行treeMap.put(key, "Value for key");
这一行,将会抛出ClassCastException
,因为没有实现Comparable
接口,TreeMap
无法对MyObject
的实例进行排序。此时只能传入一个自定义比较器。
private V put(K key, V value, boolean replaceOld) {
//获取根节点
Entry<K,V> t = root;
//如果没有根节点,则此时插入的元素会变成根节点
if (t == null) {
addEntryToEmptyMap(key, value);
return null;
}
//定义一个整型,因为比较器传回来的类型就是int,可以接收比较器的结果
int cmp;
//父节点
Entry<K,V> parent;
//获取比较器
Comparator<? super K> cpr = comparator;
//如果我们在使用构造方法传入了自定义比较器,此时会走这里的if
if (cpr != null) {
do {
parent = t;
//使用自定义比较器
cmp = cpr.compare(key, t.key);
//根据返回值判断谁大谁小(顺序还是倒叙都靠比较器内部返回参数(o1-o2)顺序)
//依照红黑树规则,小的在左边,大的在右边,相等则判断是否覆盖
//当t不等于null就会一直循环
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
}
//使用默认比较器,按 键(key) 进行比较
else {
Objects.requireNonNull(key);
@SuppressWarnings("unchecked")
//对我们的键进行强转类型,这样就可以使用其中的compareTo方法,此操作是假定key已经实现了Comparable方法
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//遍历的每个节点都赋值parent方便比较
parent = t;
//让我们的key与当前节点进行比较
cmp = k.compareTo(t.key);
//规则和上面提到的一致
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
}
//调用方法插入我们的节点
addEntry(key, value, parent, cmp < 0);
return null;
}
没有节点时,会调用以下方法,
private void addEntryToEmptyMap(K key, V value) {
//首先自己和自己比较(没有实际意义,追求一致性)
compare(key, key);
//让当前节点成为根节点,赋值给成员变量
root = new Entry<>(key, value, null);
//设置大小
size = 1;
//修改次数加一
modCount++;
}
在put方法中,如果要插入元素时只是找到要插入元素的父节点parent,真正的插入操作在addEntry进行。
private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
//包装我们的插入节点
Entry<K,V> e = new Entry<>(key, value, parent);
//依据addToLeft进行判断,如果是左边则插左边。如果是右边则插入右边
if (addToLeft)
parent.left = e;
else
parent.right = e;
//判断红黑树是否需要调整
fixAfterInsertion(e);
//容量加一
size++;
//修改次数加一
modCount++;
}
红黑树调整规则:
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)))) {
//进入if则表明当前节点它爹在左,则右节点就是它树,y就是叔叔节点
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 {
//进入if则表明当前节点它爹在右,则左节点就是它树,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 = 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;
}
具体规则可以参考如下: