继上一篇文章图解HashMap
上一篇讲解的是在Api25及25以前的put和get实现,今天讲一讲26及之后的实现。
在25的时候,采用的是数组+链表的实现方式,那么在26后采用的是数组+链表
或者数组+红黑树
的方式来存储数据,因为代码量过多就不像前篇一样一句一句解析了,我会贴出源码被给出相应的注释
这里先简单讲解一下红黑树的概念和旋转的步骤,红黑树概念抄自百度 :)手动微笑
红黑树是什么:
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶节点(NIL节点,空节点)是黑色的。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
平衡树常用操作步骤
L : 父节点的左子节点变成父节点,父节点变成左子节点的右子节点
R : 父节点的右子节点变成父节点,父节点变成右子节点的左子节点
像LR,RL,RR,LL 就是组合一下这个旋转操作
put
首先还是put方法,看代码put的时候会调用putVal方法,那么我们从这个方法开始讲
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//这个方法在第一次put的时候会进来,因为第一次的时候table==null
if ((tab = table) == null || (n = tab.length) == 0)
//resize是重新调整大小的方法,返回值是Node<K,V>[] 这里不仅仅赋值了tab,同时也将table赋值了,不仅仅是将数组扩容,同时会对红黑树做操作,后面会说
n = (tab = resize()).length;
//如果当前下标下的元素是null,就会直接添加进来
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果当前下表的元素不为null并且hash、key一样的话会吧当前下标的元素给e,因为上面已经判空了 所以走到这里元素肯定是不为null的。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果p的类型是TreeNode的话,那么会执行putTreeVal方法,这里是我们要讲的重点,等会再说
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//这个循环就是循环链表内容,如果找到一样的就替换,没找到的话就新增
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//重点在这里,如果链表的长度 >= TREEIFY_THRESHOLD - 1(7) 的时候,这个结构就会由数组+链表转为红黑树
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;
}
}
//如果上面有重复的元素, 就是e不为null,就会执行这里的代码替换原有value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//这是给LinkedHashMap提供的方法
afterNodeAccess(e);
return oldValue;
}
}
//没有找到重复的元素,要新增元素,不管当前结构是红黑树还是数组+链表 都会执行
++modCount;
//如果容量大于阈值的时候,会重新调整数组大小,就是扩容
if (++size > threshold)
resize();
//这是给LinkedHashMap提供的方法
afterNodeInsertion(evict);
return null;
}
treeifyBin(tab, hash);
这个代码很重要很重要,因为他是将当前结构换成树的方法,可以说这里是26的HashMap核心代码之一
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//同样是判断大小看看是否需要重新调整大小
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//当元素不为null的时候才会执行转换,否则的话也是直接结束这个方法
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//replacementTreeNode方法实际上就是new TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
//第一个p就是头节点
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//这里执行的是一个do-while循环,一直取到没数据,这里还没有转为树结构,只是把原先的单向链表转成了双向链表
if ((tab[index] = hd) != null)
//这里这里,真真的转树代码在这里
hd.treeify(tab);
}
}
treeify
final 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;
//先将左节点和右节点置为null
x.left = x.right = null;
//首次进来或将当前的x置为父节点,同时节点色为黑色
if (root == null) {
x.parent = null;
x.red = false;
root = x;
} else {
//有父节点了 肯定要执行这里的代码了
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//这个循环是来用确定添加子节点的位置的
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
//dir=-1 表示要往左边添加
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
//dir=1 表示要往右边添加
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;
//如果p==null 表示左或者右节点没有数据,可以添加进来,否则的话会执行下一次循环,流程见图1.1
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;
}
}
}
}
//确认父节点
moveRootToFront(tab, root);
}
图1.1.png
balanceInsertion 这个方法是用来判断树是否平衡,看代码
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//如果xp没有父节点了,则证明他就是父节点
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果节点是黑色,或者没有父节点,则直接返回root,他就是父节点
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//我理一下思路, 首先在上面一个判断xpp = xp.parent,这里可以断定xpp是xp的父节点
//但是下面的判断是这样的,xppl = xpp.left ,表示xppl是xpp的左子节点
//但是现在并不知道xp是xpp的左节点还是右节点,所以这里的判断就是xp == xppl?
//xp是不是左节点?如果xp是左节点直接进判断,不是的话就是进else
if (xp == (xppl = xpp.left)) {
//xppr是否为空,如果xppr不为null,那么它是否是红色节点,如果是的话,将他变成黑色,并且将他的父节点xpp改为红色节点, 这里就是一个更换节点颜色的操作,至于x=xpp,感觉没有用,因为在方法结束后 x 会被重新赋值
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//这里的xp是x的父节点 所以x=xp的右子节点的话,那么会进行左旋操作。同时x=xp,
//xp=x.parent,相当于两个节点都成为了他们之前的父节点
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果xp!=null的话证明还有父节点,所以要再进行一次右旋操作,这就是平衡二叉树所要用到的LR、L、R
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
/*
* 这里进行的操作和上方的类似,只不过这里变成了RL、R、L
*/
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
图1.2.png
旋转的代码就不贴了,很简单,有兴趣的可以自己点进去看看
moveRootToFront
接下来看看这个方法,这是确定根节点的
/*
* 这里保证的是取出的第一个TreeNode节点,就是根节点, 因为每次插入数据或者删除数据之后,平衡二叉树都需要进行平衡,这就导致了可能平衡后根节点有变化
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
//这里还是一个判空处理, 根节点不为null并且tab元素数组不为null
if (root != null && tab != null && (n = tab.length) > 0) {
//这里根据hash值和数组大小取出index,操作和put进元素时候一样,获取要put的index值,但是这里是用来获取
int index = (n - 1) & root.hash;
//获取第一个TreeNode
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果获取的第一个元素不是根节点
if (root != first) {
//定义一个空元素用来表示根结点的下一个元素
Node<K,V> rn;
//把原数组下标对象更改为根节点对象
tab[index] = root;
//获取根节点对象的上一个元素
TreeNode<K,V> rp = root.prev;
//如果rn!=null,那么rn的上一个元素就是根元素的上一个元素,这里相当于是将root从这个链表里面移除了
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
//如果根元素的上面还有元素,那么他的下一个元素就是rn,而他就是根元素
if (rp != null)
rp.next = rn;
//如果该数组下的元素不为null, 那么上一个元素就是root,就相当于root就是根元素了
if (first != null)
first.prev = root;
//之前的根元素现在变成了root的下一个元素
root.next = first;
//根元素没有父节点
root.prev = null;
}
//这里相当于一个规范检查吧,检查当前的结构是否符合红黑树的特性。
assert checkInvariants(root);
}
}
那么到这里,整个红黑树转换的过程就结束了,我们回到最开始的putVal方法,如果当前已经是红黑树了,那么他执行的putTreeVal
方法如下
putTreeVal
final 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;
//确认添加的节点在左边还是右边
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;
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;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
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;
//同样是确定根节点的
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
get
get方法最终调用的是getTreeNode方法,就是对树进行一个左序或者右序遍历,找到的时候直接返回出来就好了,贴一下代码可以看看
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
remove
相信你知道了树如何插入节点的,那么删除节点也一定知道了。附移除流程图一份,这里我就不考虑红黑的节点颜色了
移除一个节点.png
过程如下:
LR旋转衡树.png
顺便骗个star
更新了可自定义刷新加载和HEAD/FOOT的RecyclerView 希望各位大大多多支持
CustomRecycler
网友评论