¶Map
¶一.概述
在JAVA的常用数据结构中除了Collection族，还有Map—映射，在Map族中，顶层的Map接口规定了子类的基本行为，先看一下整体的类结构图：
- 仔细看的话，会发现 Map,HashMap,LinkedHashMap 之间的结构和 Set,HashSet,LinkedHashSet 比较类似，都是由一个类继承基本接口和实现骨架的抽象类，然后另一个Linked类直接继承Hash类实现顺序存储的功能
- HashMap 的 put(K,V) 方法有两个版本：一个是以默认的链表结构存储时调用的 putVal(K,V) 方法，会构造新的 Node 节点插入 ； 另一个是内部类 TreeNode 的 putTreeVal(K,V) ，会构造新的 TreeNode 节点插入红黑树结构中
- Map 存储的是键值对，也就是它的内部类:Entry,同时从Map 的 keySet() 方法返回 key 值的 Set 集合和其他基于 key 进行的操作来看，Map 是不允许键重复的，在 Map 中键是作为唯一索引一样存在的
¶二.Map<K,V> :
先从 Map<K,V> 了解一下它对 Map 实现的一些特性的要求:
方法:
size():int : 返回Map中的键值对数量，这一点和 Collection 一样，返回的是元素的数量而不是容器的长度
isEmpty():boolean : 检查Map容器是否为空
containsKey(Object key):boolean : 判断是否存在 key 值，并不关心key值是否关联对象
containsValue(Object value):boolean : 判断是否包含值value
get(Object key):V : 根据 key 返回泛型值V
put(K,V):V : 新增K-V ,如果已经存在K，就是修改V
remove(Object key):V : 根据key删除键值对，返回泛型值V
putAll(Map<? extends K,? extends V> map) : 将参数 map的键值对填充进来
clear() : 清除所有键值对
keySet():Set
: 返回 键 K 的Set集合 values():Collection
: 返回所有 值 V 的集合 entrySet():Set<Map.Entry<K,V>> : 返回所有键值对的Set集合
getOrDefault(Object key,V defaultValue) : 获取 key 对应的 value，如果key不存在或者不关联值，返回参数的 defaultValue
forEach(BiConsumer<? extends K,? super V> action) : 迭代方法
replaceAll(BiFunction<? super K,? super V,? extends V> function) : 替换所有对应 entry 的value 值
putIfAbsent(K key,V value) : 意图明显的方法名，如果key 对应的值为空，新增 K-V
remove(Object key,Object value) : 根据 key 和 value 移除键值对
replace(K key,V oldValue , V newValue) : 使用 newValue 替换 key 对应的 oldValue
replace(K key, V value) : 使用 value 替换 key 对应的值
小结:
- 可以看出所有的操作都是先从key值开始的，先匹配到key值再进行之后的增删改等操作，这意味着再 Map 中 key 是作为唯一标识一样的存在，也就是所谓的key值不重复了
- put 方法兼具了新增和修改键值对的能力，依据是key是否对应存在任意值—包括 null 值，存在就进行修改，不存在key就新增键值对k-v
- 可以只返回key和value的集合，Set
和 Collection ，这里也可以看出，Key 是不会重复的，不然Set集合和Collection 对应的时候就会导致key缺失了，不能够代表key集 - 还有一个 entrySet() 方法，返回的是键值对集合，Entry 才是 Map真正存储的东西，这也符合那句话：简单的数据结构组合起来构成复杂的数据结构。键值关联再加上键排重，形成了Map 这种映射的数据结构。
¶三.HashMap<K,V>: key 值不重复，存储结构可变，可扩容
在不需要考虑存储顺序，又需要使用键值对这样的存储结构时，HashMap 是最合适的
HashMap 是最常用到的key-value存储之一，也是并发数据结构ConcurrentHashMap 的非线程安全版本
在了解 HashMap 之前先说明几个概念:
Node : 可以通过具备前后节点引用构成链表结构，或者具备前后节点，父子节点引用构成树结构的自包含数据类型，物理上可以不连续。
链表:每个节点通过持有前后节点的引用达到构成一条链式结构
红黑树 : 节点具备颜色的平衡二叉树，除了满足平衡二叉树的特点，还具备以下特点
- 节点非黑即红
- 根节点为黑，叶子节点为黑，没有叶子节点时增加颜色为黑色空节点代替
- 红色节点的子节点为黑色
- 从任一节点到达它的空子节点所包含的黑色节点数量相等
bin : 一种数据结构 ， 每个bin都包含一条单链表的头节点，它代表了一个区域的元素，每个属于这个区域内的元素都会被链接到链表中？
JDK 1.8 版本 HashMap 数据结构:
每个buket元素超过一定数量（TREEIFY_THRESHOLD = 8）时，转红黑树存储
元素数量小于等于一定数量（UNTREEIFY_THRESHOLD = 6）时，转链表存储
¶基本属性：
先看一下 HashMap 的类结构图:
HashMap 包含的基本属性主要是容量定义，负载因子，链表转红黑树指标，红黑树转链表指标等
- **DEFAULT_INITIAL_CAPACITY = 1<<4 ** : 默认的初始化容量
- **MAXIMUM_CAPACITY = 1<<30 ** : 最大容量
- DEFAULT_LOAD_FACTOR = 0.75f : 负载因子，默认值0.75，即键值对达到容量的0.75比例，就会进行扩容
- TREEIFY_THRESHOLD = 8: 使用红黑树代替链表存储数据的阈值，即此时链表的节点个数
- UNTREEIFY_THRESHOLD = 6 ： 使用链表代替红黑树存储的阈值，即此时红黑树的节点个数
- MIN_TREEIFY_CAPACITY = 64: 用于红黑树化时要求数组的最小长度
- Node<K,V>[ ] table : 用于存储节点的数组，get时节点会根据key hash 到table的index
- Set<Map.Entry<K,V>> entrySet : 用于存HashMap 中所有的节点
- int size : 节点的总个数
- int modCount ：节点被修改的次数
- int threshold : 决定是否扩容的阈值，loadFactor * capacity(size)，也就是说，假设size=100,loadFactor =0.75,容量达到75时需要扩容
- final float loadFactor : 加载因子，用于计算阈值
¶基本方法：
public V put(K key,V value) : return putVal(hash(key),key,value,false,true);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54> final V putVal(int hash,K key,V val,boolean onlyIfAnsent,boolean evict){
> Node<K,V> tab;
> Node<K,V> p;
> int n,i;
> //如果没有创建过table，使用扩容方法初始化一个内部table
> if((tab = table)==null || (n = tab.length)==0){
> n = (tab = resize()).length;
> }
> //如果根据key 和 hash 到的值为空，创建节点插入链表末尾
> if((p = tab[i = (n-1) & hash]) == null){
> tab[i] = newNode(hash,key,value,null);
> }else{
> Node<K,V> e;K k;
> //判断是否已经存在将要添加的元素，即是否存在相同hash值
> if(p.hash == hash && ((key = p.key) ==key || (key != null && key.equals(l)))){
> //赋值
> e = p;
> }else if(p instanceof TreeNode){
> //如果p是一个树节点，转型并调用putTreeNode进行添加
> e = ((TreeNode<K,V> p).putTreeVal(this,tab,hash,key,value);
> }else{
> //否则遍历链表查找是否存在该元素
> for (int binCount = 0; ; ++binCount) {
> if ((e = p.next) == null) {
> //如果 p节点是尾节点且为空，构造新节点插入
> p.next = newNode(hash, key, value, null);
> //遍历的次数大于属性 TREEIFY_THRESHOLD（链表转红黑树存储元素的阈值）
> if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
> //将当前存储元素的链表转红黑树格式存储元素
> treeifyBin(tab, hash);
> break;
> }
> if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
> break;
> p = e;
> }
> }
> if (e != null) { // existing mapping for key
> V oldValue = e.value;
> if (!onlyIfAbsent || oldValue == null)
> e.value = value;
> //插入元素后要保证HashMap 内部的链表存储结构不被破坏，将元素移至末尾
> afterNodeAccess(e);
> return oldValue;
> }
> }
> ++modCount;
> if (++size > threshold)
> resize();
> //插入元素后，将key指向的空节点移除
> afterNodeInsertion(evict);
> return null;
> }
>- 一次元素插入，从尾节点开始判断，如果匹配到hash值指向尾部空节点，直接构造节点插入
- 否则进行遍历，匹配节点是否存在，存在则只进行赋值
- 否则判断是否是一个树节点，是的话调用 putTreeNode() 方法进行节点插入
- 在遍历链表的过程中，如果发现遍历的次数达到了存储结构转红黑树的要求，将所有元素转为红黑树存储
- 最后判断是否将元素排至队尾和删除空元素
putTreeVal(HashMap<K,V> map,Node<K,V>[] tab,int h,K k,V v):TreeNode<K,V>: 当插入节点是树节点的时候调用这个方法进行元素插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//先获取根节点，如果当前节点的父节点为空，说明它是根节点，否则查找根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//比较根节点hash和参数hash，判断节点位于根节点的左子树还是右子树
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
//这里的判断是为了后续的遍历，在未匹配到指定元素但后续左右节点不为空的情况，以左右子节点为起点查找指定hash和key的参数节点
if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null && (q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
//根节点
TreeNode<K,V> xp = p;
//如果匹配到空的叶子节点，根据前面的 dir 值判断参数元素位于树的左边还是右边
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
//如果匹配到hash但hash指向null,构造节点插入
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
//根据dir判断新节点插入到左边还是右边
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//添加对节点的引用，满足树的关系
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//判断当前的根节点在自己的bin结构中是第一个节点
//balanceInsertion(root, x);插入元素后判断红黑树的结构是否被破坏
//确保当前根节点也是bin结构中的第一个节点
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}插入一个树节点，先从确定根节点开始，然后判断要插入的元素应该位于根节点的左侧还是右侧
匹配到hash有两种情况：null 和 已存在的节点
匹配到null节点会构造新节点插入根节点的左子树或者右子树
匹配到已存在的节点，仅简单赋值一次
在成功插入节点之后，做了两件事：判断插入节点后的树特性是否被破坏，否则平衡树的结构； 确保当前的根节点在bin存储中也是第一个节点，这样从红黑树转链表时头节点不会出错
resize(): Node<K,V>[ ] : 扩容方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//未初始化过的HashMap 内部 table 为null
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果当前的table的容量大于最大容量 1<<30,
if (oldCap >= MAXIMUM_CAPACITY) {
//下一次扩容的size就是Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果 原容量*2小于最大允许容量且大于默认容量10
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//下一次扩容的size就是原本的 threshold*2
newThr = oldThr << 1; // double threshold
}
//使用原本的下次扩容size来初始化table容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//使用默认容量初始化table
newCap = DEFAULT_INITIAL_CAPACITY;
//计算新的扩容阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//计算一个临时阈值
float ft = (float)newCap * loadFactor;
//如果扩容后容量小于最大容量，且临时阈值小于最大容量，说明还可以进行扩容，直接赋值为新的扩容阈值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
({"rawtypes","unchecked"})
//定义新的Node数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//遍历旧table
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//如果当前节点不为空，将旧table的节点引用置空
oldTab[j] = null;
//如果当前节点是尾节点
if (e.next == null)
//插入数组末尾
newTab[e.hash & (newCap - 1)] = e;
//如果是一个树节点
else if (e instanceof TreeNode)
//将节点分割成高位和低位树结构或者当它的容量足够小时，转为链表？
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//TODO...没看懂？？？
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}- 首先需要计算出正确的扩容容量，几个判断依据：newCapa 是否大于最大容量，newCapa是否大于默认容量，oldThreshold是否小于最大容量
- 正常情况下是2倍扩容，然后对threshold也进行2倍增加，会维持一样比例的扩容阈值
- 之后就是构建新节点数组和遍历旧数组赋值，同样地如果节点是一个树节点，需要调用 splie(HashMap,Node[],index,bit) 方法去分割树，同时还需要判断是否有必要将bucket的元素进行链表化以节省空间和提升效
treeify(Node<K,V>[] tab):链表转红黑树
当一个bucket中元素的数量超过 TREEIFY_THRESHOLD = 8 时，将链表元素转红黑树存储
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49final void treeify(Node<K,V>[] tab) {
//定义根节点
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//第一次会将第一个节点设置为根节点，即parent=null,red=false
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
//到这里说明已经确定了根节点，接下来就是根据hash确定其他节点的插入位置
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
//hash小于根节点，说明应该位于左子树
dir = -1;
else if (ph < h)
//hash大于根节点，应该位于右子树
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//到这里只是完成了一次子节点元素插入，但是节点并没有着色，除了知道根节点和叶子节点是黑色，不知道其他节点的颜色
//同时还可能需要进行树旋转来平衡树使它继续满足一颗红黑树的特性
root = balanceInsertion(root, x);
break;
}
}
}
}
//之前说过，每个bin都包含一个链表的头节点，所以需要确保当前的根节点就是bin持有的第一个节点
moveRootToFront(tab, root);
}- 仅仅是插入元素的过程比较简单，先确定根节点，再通过hash去判断接下来的节点是插入到左子树还是右子树
- 每次插入子节点之后需要通过 balanceInsertion() 平衡树
balanceInsertion(TreeNode<K,V>) root , Node<K,V> x) :平衡树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
//先假设插入了一个红色节点x，那也就假设它的父节点xp是黑色节点，xpp是红色节点
x.red = true;
// xp:x的父节点 ； xpp:xp的父节点； xppl:xpp的左子节点；xppr:xpp的右子节点；
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
//x没有父节点，说明x是根节点
x.red = false;
return x;
}
//TODO ...这一段需要补充一些图来说明
//如果当前节点的父节点是黑色节点，且父节点的父节点为空，说明插入在根节点之后
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//到了这一步时: xp : red ; xpp应该是 !red ，但是x已经假设是red了
if (xp == (xppl = xpp.left)) {
//如果还存在一个红色的右子节点
if ((xppr = xpp.right) != null && xppr.red) {
//说明是在红色节点之后插入了一个红色节点，需要重新着色
xppr.red = false;//xpp左右节点为黑色
xp.red = false;
xpp.red = true;
x = xpp;//x赋值为xpp，本身节点是红色，具备两个空的黑色节点
}
else {
//说明xpp的右子节点为空,如果这时插入的节点在xp的右边
if (x == xp.right) {
//左旋
//此时插入的情况是: xpp.left=null;xpp.right=xp;xp.left=null;xp.right=x;
root = rotateLeft(root, x = xp);
//插入后: xpp.left=x; xpp.right=xp;
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//xp不为空时
if (xp != null) {
//将xp置为黑色节点
xp.red = false;
//如果xpp也不为空
if (xpp != null) {
//将xpp置为红色节点
xpp.red = true;
//右旋，使得x和xp成为红色节点xpp的两个黑色子节点
root = rotateRight(root, xpp);
}
}
}
}
else {
//到这里说明xp是xpp的右子节点，再假设 xpp存在红色的左子节点xppl
if (xppl != null && xppl.red) {
//重新着色
//左子节点黑色
xppl.red = false;
//右子节点黑色
xp.red = false;
//xpp红色
xpp.red = true;
//插入了一个具有两个空黑色子节点的红色节点
x = xpp;
}
else {
//xpp不存在左子节点的情况下，给xpp的右子节点xp插入了左节点x
if (x == xp.left) {
//右旋
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//xpp不存在左子节点的情况下，给xpp的右子节点xp插入了右节点x
if (xp != null) {
//重新着色，xp称为黑色节点
xp.red = false;
if (xpp != null) {
xpp.red = true;
//左旋
root = rotateLeft(root, xpp);
}
}
}
}
}
}- 先判断插入节点是否是根节点，或者插入节点是否在根节点之后
- 以上情况都不是的话说明树的高度至少为3
- 再假设插入节点是一个红色节点，因为叶子节点都是黑色节点
- 继续根据插入节点的位置和颜色和父节点的位置和颜色以及父节点的父节点的位置和颜色判断是进行节点重新着色还是旋转树，或者都需要
rotateLeft(TreeNode<K,V> root,Node<K,V> p):左旋
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
//r:右节点 ； rl:r的左子节点 ； pp : p 的父节点
TreeNode<K,V> r, pp, rl;
// r=p.right
if (p != null && (r = p.right) != null) {
//p.right==null
if ((rl = p.right = r.left) != null)
rl.parent = p;
//r.parent = p.parent
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
//如果 p 节点是左子节点
else if (pp.left == p)
// pp.left = r = p.right
pp.left = r;
else
//p是右子节点
//pp.right = r =p.right
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}- 没那么看懂左旋和右旋，说明之后再补充.
- //TODO…
rotateRight(TreeNode<K,V> root,TreeNode<K,V> p):右旋
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}- 待补充…TODO
**moveRootToFront(Node<K,V>[] tab,TreeNode<K,V> root) **：确认参数的root节点也是bin结构中的第一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
//根节点不为空，tab不为空，存在节点
if (root != null && tab != null && (n = tab.length) > 0) {
//获取第一个元素的下标
int index = (n - 1) & root.hash;
//取出 tab 数组中第一个树节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//判断头节点和首节点
if (root != first) {
Node<K,V> rn;
//将root节点置为tab数组的首节点
tab[index] = root;
//说明root节点在tab中存在prev节点
TreeNode<K,V> rp = root.prev;
//如果root节点还存在next节点
if ((rn = root.next) != null)
//将next节点和prev节点连接
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
//如果当前tab数组的首节点不为空
if (first != null)
//root节点作为first的prev节点链接进来
first.prev = root;
//链接root和first节点
root.next = first;
//头节点prev置空
root.prev = null;
}
assert checkInvariants(root);
}
}- 确保当前红黑树结构中的root节点也是tab数组链表结构的首节点
checInvariants(TreeNode<K,V>)：检查树结构是否被破坏
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
//这里是按照红黑树的特性去检验树结构是否被破坏的
//从前一个方法可以知道传入的参数是根节点
tb = t.prev, tn = (TreeNode<K,V>)t.next;
//因为moveRootToFront 方法已经把根节点置为链表结构的首节点了，所以prev节点肯定是null
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
//存在非空的left节点但是节点的hash大于根节点，说明插入位置错误
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
//同上
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
//根节点可以是红色节点或者黑色节点，但是红黑树中红色节点的子节点是黑色节点
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
//递归
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}- 主要是根据红黑树的特性从根结出发，检查节点之间的关系是否被破坏
blanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) : 和前面的
blanceInsertion(root,x)方法类似，作用是在删除节点之后平衡树。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
//判断是否删除了空节点或者删除了根节点
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
//判断被删除节点是否是父节点为空的黑色节点，其实就是根节点
x.red = false;
return x;
}
else if (x.red) {
//被删除的是一个红色节点，将节点置黑 TODO...为什么？
x.red = false;
return root;
}
else if ((xpl = xp.left) == x) {
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;
else {
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
}
else {
if (sr == null || !sr.red) {
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
}
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}- TODO…涉及红黑树旋转平衡的函数之后再补充，现在看不懂
¶小结
- HashMap 存储节点的方式有两种：链表和红黑树，它们之间会相互转换以维持比较好的存储和使用性能
- 每次在进行节点增删的时候，都会进行节点数组是否为空，增删节点是否是树节点，增删节点后调整存储结构和确定首节点等操作
- 对于增删节点的方法分别提供了基于链表和基于红黑树的实现