集合源码学习(六):TreeMap

时间:2021-11-17 14:09:04

从这篇博客开始,慢慢一起学习Map集合

什么是Map?

Map和List不同,
在List中,我们记得主要是线性表,List中又可以细分为基于数组实现(ArrayList,Vector, ..),基于链表实现(LinkedList, …)。并且主要是List只有value,即只有一个值。
而在Map中 ,存储的是一个键值对 组合,即key-value。基本操作都是作用于这个组合。
看Map接口的实现:

public interface Map<K,V>

而对于构造Map的方式又有多种,本文主要介绍TreeMap,基于红黑树 的Map实现方式。

TreeMap的基本特征

先看定义:

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable

1):有序性
NavigableMap是一个扩展SortedMap的集合,因而TreeMap也是有序的,注意这里的有序性和ArrayList里面的顺序性不同
好比10个小朋友站队,
在ArrayList里面,依次进入,我不能保证在里面是按照高矮排序的,但是一定是顺序的,也就是如果张三在李四前面进,
王五在李四后面进,那么最终队列中,李四前后就一定是张三和王五(当然方位关系,也可为王五和张三)。
而在TreeMap里面,由于结构不同,所以就不是线性表这样一条线,但是通过iterator遍历的时候(通过身高确定的comparator),就能够保证最终按照身高高矮顺序输出。
所以二者不同。

2):元素值空值问题
由上特点分析,TreeMap是有序的,而在里面其实是通过Comparator来比较的,这样才会有序嘛,并且在创建一个TreeMap的时候,可以传入Comparator辅助排序,或者用默认的Comparator进行判定大小(强行用父类compareTo进行比较的)。这样的意图是什么呢,也就是你可以将键设为空值(null),前提是你要自己传一个Comparator,考虑到null的情况。当然值也是能为null的,正常存正常输出。
先看获取值的源码:

 final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
//默认情况下,不允许key为null
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;
}
//当用了自己的Comparator的时候
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;
}

3):不允许重复
当插入一个新值的时候,会沿着二叉树一直向下找,知道找到合适位置,如果找到key相等的话,就会产生替换操作,所以是不允许重复的,具体原理在下文将put操作会分析。

4):操作的时间复杂度
在jdk描述中,指出在get,put,remove等操作方法中,都具有log(n)的时间复杂度,即查找、插入和删除在平均和最坏情况下都是O(log n)。在下文具体分析中可知悉。

5):非线程安全
TreeMap非线程安全,使用时注意同步或者使用包装类进行同步。

synchronizedSortedMap Collections.synchronizedSortedMap

TreeMap的原理

TreeMap是基于二叉树实现的,这里不了解二叉树的可以看看网上的一些文章,而在二叉树里面又分为多种类型的树,有一种树叫做AVL,这里可以了解下:AVL 。而在AVL树的具体实现中,又有一种典型的实现方法,这就是红黑树了红黑树
而在Java中TreeMap,就是基于这种红黑树实现的。
或许说道这里,还是有很多读者会很蒙,不太理解TreeMap是啥,下面介绍下红黑树的基本特征,最后会给出简单易懂的TreeMap原理。

红黑树

二叉查找树
由于红黑树本质上就是一棵二叉查找树,所以在了解红黑树之前,咱们先来看下二叉查找树。
二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

-若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
-若任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
-任意结点的左、右子树也分别为二叉查找树。
-没有键值相等的结点(no duplicate nodes)。

因为,一棵由n个结点,随机构造的二叉查找树的高度为lgn,所以顺理成章,一般操作的执行时间为O(lgn)。

但二叉树若退化成了一棵具有n个结点的线性链后,则此些操作最坏情况运行时间为O(n),也就是编程斜着的一根。后面我们会看到一种基于二叉查找树-红黑树,它通过一些性质使得树相对平衡,使得最终查找、插入、删除的时间复杂度最坏情况下依然为O(lgn)。

红黑树
而红黑树,也是一棵二叉树。
但它是如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢?这就引出了红黑树的5条性质:

1)每个结点要么是红的,要么是黑的。  
2)根结点是黑的。
3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
4)如果一个结点是红的,那么它的俩个儿子都是黑的。
5)对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

也正是这5条性质保证了这棵红黑树高度为log(n),所以保证了查找、插入、删除的时间复杂度最坏为O(log n)。
什么时候会用到这5条新值呢?就是当你对树的结构进行了改变(插入,删除)时,就需要调整来保证这5条性质所以改变
后还是一棵红黑树。
先看一张图了解下:(就是平衡二叉树,加上红黑颜色节点限制)
集合源码学习(六):TreeMap

树的旋转知识
主要包括左旋和右旋,在平衡二叉树中,用于调整二叉树的最大高度差不超过1。
左旋:
集合源码学习(六):TreeMap

右旋:
集合源码学习(六):TreeMap

插入及调整
接下来就是红黑树的插入过程,
首先是要确定新加入的节点适合放到哪个位置,步骤就是从根节点向下遍历,左小右大。
当找到之后,就将值插入,但是插入过程后,树的结构和相关性质就会发生变化导致不再符合红黑树的特征,此时就需要调整
经过调整步骤后,树的结构就再一次符合了红黑树的特征了,并且值也插进去了。
这里就不再详细讲红黑树插入算法,本文主要集中篇幅将Java中TreeMap,当然理解了红黑树后,也就可以轻松理解TreeMap了,深入了解可访问
julycoding

删除及调整
和插入步骤一样,不细讲
先找到节点,再删除节点,调整。

总括
红黑树就是一棵平衡二叉树,它的红黑结构保证了它的树的平衡性,保证了插入、删除、查找的效率即log(n),所以每当插入节点之后,再进行调整,以保证树的红黑结构。

TreeMap源码剖析

这里把TreeMap的具体动作方法进行介绍。

传入一个有序集合进行构造

   public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
//从有序集合里面建立一个treemap
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
/**
* 从有序集合中获得数据并插入。
* 注意是有序的
*/

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);
}

/**
* 插入操作
*
* level :当前节点应该插入的层
* lo:子树的第一个节点
* hi:子树的最后一个节点
* @param 表明该层该节点必须为红色
*/

@SuppressWarnings("unchecked")
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 {
//判断是否有错误
if (hi < lo) return null;
int mid = (lo + hi) >>> 1;
Entry<K,V> left = null;
//一直往下递归找到左子节点
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
//找到了,设置值的过程。
K key;
V value;
if (it != null) {
if (defaultVal==null) {
Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
key = (K)entry.getKey();
value = (V)entry.getValue();
} else {
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
Entry<K,V> middle = new Entry<>(key, value, null);
// 设置完之后,就开始设置color以及将节点和待插入位置的父子节点连接起来。
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;
}

上面代码即通过传入一个有序的集合,来构造一个TreeMap,由于是有序集合,所以肯定是从二叉树的两头开始构造的。

getEntry方法

即通过一个key,获取key属于的那个节点。

    /**
* 从实体中寻找key,默认是没有有comparator的。
* 就使用默认的compareTo来进行比较。
*
* 由此可知,key不能为null。
*/

final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
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;
}

getEntry方法只涉及二叉树的查找,所以不涉及调整,即从根节点开始一直向下查找。这段相关代码在上面将键是否为null时列举出来过,就不多讲了。
在二叉树结构的TreeMap中,并不是每次都能找到值,所以在TreeMap中,还提供了很多get方法,例如:
final Entry

/**
* 天花板,所以在上面,所以比k大的最小
* 找到一个,比key大的,最小的节点,可以等于k,获取TreeMap中不小于key的最小的节点;
若不存在(即TreeMap中所有节点的键都比key大),就返回null
* @param key
* @return
*/

final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
// 情况一:若“p的key” > key。
// 若 p 存在左孩子,则设 p=“p的左孩子”;
// 否则,返回p
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
// 情况二:若“p的key” < key。
} else if (cmp > 0) {
// 若 p 存在右孩子,则设 p=“p的右孩子”
if (p.right != null) {
p = p.right;
} else {
// 若 p 不存在右孩子,则找出 p 的后继节点,并返回
// 注意:这里返回的 “p的后继节点”有2种可能性:第一,null;第二,TreeMap中大于key的最小的节点。
// 理解这一点的核心是,getCeilingEntry是从root开始遍历的。
// 若getCeilingEntry能走到这一步,那么,它之前“已经遍历过的节点的key”都 > key。
// 能理解上面所说的,那么就很容易明白,为什么“p的后继节点”又2种可能性了。
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
// 情况三:若“p的key” = key。
} else
return p;
}
return null;
}

put方法

put方法步骤,先向下找最适合本(key,value)对的地方,然后插入,最后调整

    /**
* 将一对键值对k,v插入到treemap中,如果k已经存在,则会发生替换,value将替换oldvalue
*/

public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
//检查是否为null
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 左右两条线,向下的查找
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
return t.setValue(value);
} while (t != null);
}
else {
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);
}
//找到了最佳的位置
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;
}

delete方法

相比较与put方法来说,delete方法并不用再进行寻找节点,因为已经给了你这个节点了,当然有些方法如果只提供key的话,就还需要找到这个节点。

/**
* 删除p,然后重新调整平衡
*/

private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// p有两个孩子节点
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
// 选取替代将要删除节点位置节点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
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;
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else {
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;
}
}
}

TreeMap里面的Iterator

首先,TreeMap里面的Iterator也是fail-fast的。这里要注意一点,在Map里面的集合中,遍历操作只能通过Iterator来实现,因为Map里面不是线性表,所以你自然不能用类似于ArrayList等for循环走一遍就遍历到所有操作。
TreeMap里面有多个不同实现的Iterator
static class TreeMapSpliterator<K,V>:在TreeMap的Iterator中作为下面两个Iterator的父类,实现公共的Spliterater方法。
static final class KeySpliterator<K,V>:key的分割迭代器。
static final class DescendingKeySpliterator<K,V>:倒序的key的分割迭代器。

本文图片以及红黑树学习引用于:
julycoding