“本文将主要介绍HashMap的put操作以及相应的扩容。”
相关阅读:
JDK1.8HashMap源码学习-put操作以及扩容(一)
01
—
红黑树化
当我们继续向编号6的桶中增加值,直到数组长度达到64,接着继续增加值,使得6号桶中的节点数为7,这个时候的结构图如下:
这时我们加入518这个节点,就会触发转红黑树的操作。我们看下treeifyBin这个方法。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果数组为空或者数组长度没有达到64 则执行扩容
//通过扩容去实现桶中节点数减少的目的
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY){
resize();
//满足桶中节点数大于8 且 数组长度不小于64 执行转换红黑树
}else if ((e = tab[index = (n - 1) & hash]) != null) {
//将单链变成双链 hd是链的头 tl是移动节点
TreeNode<K,V> hd = null, tl = null;
do {
//将Node<K,V>节点转换为TreeNode<K,V>节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null){
hd = p;
}else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null){
//当前数组下标中保存的节点数据转红黑数
hd.treeify(tab);
}
}
}
具体逻辑就是如果数组为空或者数组长度没有达到64则执行扩容操作,通过数组扩容为原先的两倍达到减少桶中节点数的目的。如果数组长度不小于64且该桶节点数大于等于8(调用该方法时的条件)且该桶的根节点不为空,先执行单向链表转为双向链表,即遍历单向链表,转换完成后再红黑树化。
其中变为双向链表的过程中,把原先的Node<K,V>节点转换为TreeNode<K,V>节点。而在最开始介绍HashMap数据结构的时候我们介绍过,TreeNode<K,V>节间接继承自Node<K,V>节点,主要多了一些构造红黑的一些属性,父节点parent,左右孩子节点left,right,以及前节点prev(双向链表使用)和节点的颜色red(一个boolean类型)。此时完成了双向链表的构造结构图如下
接着我们将链表的头节点hd赋值给桶的根节点,且不为空则执行红黑树化,即treeify。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//TreeNode<K,V> x = this 调用该方法采用的是根节点调用 所以x就是根节点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//当前节点的下一节点 控制链表循环
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//第一次循环 赋值根节点 而且根节点肯定是黑色且没有父节点
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;;) {
/**
* dir 方向
* ph p节点的hash值
* pk p节点的key
*/
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h){//方向向左
dir = -1;
}else if (ph < h){//方向向右
dir = 1;
//hash值一致 继续比较key 计算出方向
}else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0){
dir = tieBreakOrder(k, pk);
}
//xp临时赋值 是x的父节点及以上节点
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;
}
}
}
}
//确保数组存储的一定是双向链表的头节点 也是树的根节点
//以及检查红黑树的合法性
moveRootToFront(tab, root);
}
从根节点遍历桶中的节点,TreeNode<K, V> x =this,从调用处我们知道this指的是根节点,然后通过比较hash值找到查找方向,直到找到挂载的位置,进行赋值,然后进行红黑树的平衡插入,最后保证数组存储的根节点数据即是双向链表的头节点也是红黑树的根节点。
我们看下每次插入一个节点是怎么保证插入平衡的
/**
* 平衡插入的节点
* @param root 根节点
* @param x 新插入的节点
*/
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;;) {
/**
* 1、赋值操作 xp = x.parent 即xp为x的父节点
* 2、判断是否为空 如果是空说明x 节点就是根节点 而根节点肯定是黑色
*/
if ((xp = x.parent) == null) {
x.red = false;
return x;
/**
* 判断x的父节点xp颜色是否为黑色 和x祖父节点xpp是否为空
* 如果 任一条件成立 则直接返回根节点
*/
}else if (!xp.red || (xpp = xp.parent) == null){
return root;
}
//xppl x的祖父节点的左孩子节点
//判断x的父节点是否是x的祖父节点左孩子节点
if (xp == (xppl = xpp.left)) {
//xppr x的祖父节点的右孩子节点
//赋值xppr 如果插入节点x的祖父节点的右孩子节点不为空且是红色
if ((xppr = xpp.right) != null && xppr.red) {
//赋值x的祖父节点的右孩子节点颜色为黑色
xppr.red = false;
//x父节点为黑色
xp.red = false;
//x的祖父节点为红色
xpp.red = true;
//x赋值为x的祖父节点 继续循环
x = xpp;
}else {
//插入节点是否x父节点是右孩子
if (x == xp.right) {
//如果是 赋值x为x的父节点 即x的父节点需要左旋
root = rotateLeft(root, x = xp);
//此时x已经变为x的父节点 xp和xpp同样向根的方向推进一层
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果插入节点插入的位置是右孩子
//此时xp已经是插入节点的祖父节点了
if (xp != null) {
//赋值插入节点的父节点为黑色
xp.red = false;
//如果插入节点的父节点不为空
if (xpp != null) {
//赋值为红色
xpp.red = true;
//x的祖父节点需要右旋
root = rotateRight(root, xpp);
}
}
}
}else {
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);
}
}
}
}
}
}
我们先看下什么是左旋和右旋
/**
* 左旋 就是将操作节点P的右孩子变为P的父节点
* 操作节点变为原右孩子的左节点
* 如果原操作节点得右孩子有左孩子
* 那么就把这个左孩子变为操作节点的右孩子
* @param root 红黑树的根节点
* @param p 操作节点
*/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
//操作节点不为空 且操作节点的右孩子不为空
if (p != null && (r = p.right) != null) {
/**
* 1、将操作节点的右孩子的左孩子赋值给操作节点的右孩子 即rl = p.right = r.left
* 2、如果rl不为空 则修改rl的父节点为操作节点
*/
if ((rl = p.right = r.left) != null){
rl.parent = p;
}
/**
* 1、将操作节点的父节点赋值给操作右孩子的父节点 即pp = r.parent = p.parent
* 2、pp 如果为空 即操作节点的父节点为空 说明原操作节点为根节点
* 这次左旋后 根节点为r 即操作节点的右孩子变为根节点
* 3、根节点的颜色只能是黑色
*/
if ((pp = r.parent = p.parent) == null){
(root = r).red = false;
//操作节点的父节点不为空 如果操作节点的父节点的左孩子就是操作节点
//赋值 将操作节点的父节点的左孩子赋值为操作节点的右孩子
}else if (pp.left == p){
pp.left = r;
//否则 将操作节点的父节点的右孩子赋值为操作节点的右孩子
}else{
pp.right = r;
}
//将操作节点变为操作右节点的左孩子
r.left = p;
//操作节点的父节点变为操作节点的右孩子
p.parent = r;
}
return root;
}
我们看下图,有个直观的感受
关于左旋我们总结如下
我们看下右旋图
关于右旋我们总结如下
了解完左旋和右旋 我们看下左旋和右旋的条件
左旋条件:
右旋条件:
通过左旋和右旋达到红黑树的条件。接下来我们看下moveRootToFront
/**
* 确保数组存储的一定是双向链表的头节点 也是树的根节点吧
* Ensures that the given root is the first node of its bin.
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null
&& (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
//获取数组中保存的根节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果不一致 执行调整 就是将root节点从双向链表中截取出来 然后前后节点连接 再把截取的root节点放到原数组保存节点数的前面 完成双链的调整
if (root != first) {
Node<K,V> rn;
//将根节点保存到数组
tab[index] = root;
//根节点的前节点
TreeNode<K,V> rp = root.prev;
//根节点的下一节点不为空 将根节点的下一节点的前节点赋值为根节点的前节点
if ((rn = root.next) != null){
((TreeNode<K,V>)rn).prev = rp;
}
//根节点的前节点不为空 将根节点的前节点的后节点赋值为根节点的后节点 这样根节点就从双向链表中脱离了
if (rp != null){
rp.next = rn;
}
//如果原数组节点不为空 则件原数组节点的前节点保存为根节点
if (first != null){
first.prev = root;
}
//根节点的后节点为原数组头节点
root.next = first;
//根节点没有前节点
root.prev = null;
}
//检测是否合法
assert checkInvariants(root);
}
}
moveRootToFront主要完成了保证红黑树的根节点是双向链表的头节点,如果桶的根节点和红黑树的根节点不一致,就将红黑树的根节点从双向链表中脱离出来放到链表的头部。最后是检测红黑树的合法性。
/**
* 递归检查节点的正确性 从传入节点开始 如果是根节点 那就是整棵树
* Recursive invariant check
*/
static <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;
//如果当前节点的前节点不为空 且 当前节点的前节点的后节点不是当前节点 返回false 双向链表的操作
if (tb != null && tb.next != t){
return false;
}
//如果当前节点的后节点不为空 且 当前节点的后节点的前节点不是当前节点 返回false 双向链表的操作
if (tn != null && tn.prev != t){
return false;
}
//当前节点的父节点不为空 且当前节点不是当前节点父节点的左右孩子 返回false 红黑树操作
if (tp != null && t != tp.left && t != tp.right){
return false;
}
//当前节点的左孩子不为空 且 该左孩子的父节点不是当前节点或者左孩子的hash值大于当前节点 返回false
if (tl != null && (tl.parent != t || tl.hash > t.hash)){
return false;
}
//当前节点的右孩子不为空 且该右孩子的父节点不是当前节点或者右孩子的hash值小于当前节点 返回false
if (tr != null && (tr.parent != t || tr.hash < t.hash)){
return false;
}
//当前节点是红色 而且左右孩子节点不为空的话都是红色 返回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;
}
此时我们的数据结构是这样的
放个动图
02
—
插入一个树节点
整体过程其实就是先通过hash比较查找到插入的位置,然后执行插入,最后平衡插入以及保证树的根节点也是双向链表的头节点。
/**
* 插入一个树节点
* Tree version of putVal.
*/
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;
//从root节点开始查找位置
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
/**
* dir 查找方向 >0 向右查找 <0 向左查找
* ph 根节点的hash值
* pk 根节点的key值
*/
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))){
//hash一致 且key值一致 即为找到节点 返回后交给替换出做处理
return p;
//hash一致 但是key值不相等 那就看key是否可比较
}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;
/**
* 1、根据dir是否大于0判断下一个接着查找的方向 大于0 就从右孩子接着查找 小于0就从左孩子接着查找
* 2、赋值p 指向左孩子还是右孩子 如果不为空 继续查找 直到找到空的左孩子或者右孩子
* 3、执行树结构的插入
* 4、执行双向链表的插入
* 5、平衡插入树的节点 确保根节点保存在数组中
*/
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);
//根据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;//设置当前节点下一节点的前置节点为新节点 这个保证了先插入的节点的前节点是后插入节点
}
//后插入节点插入到了父节点和先插入节点的中间 双链的操作
//平衡插入的节点
//确保根节点在数组下标中
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
我看看下动态过程
03
—
树的裁剪
我们看下针对根节点是红黑树是如何进行扩容裁剪的。
/**
* map 旧数组
* tab 新数组
* index 旧数组下标
* bit 旧数组长度
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
//根据调用 知道this指的应该是当前的根节点
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//将单条双向链表 拆解为双条双向链表
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
//lc低链表计数 hc高链表计数
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null){
loHead = e;
}else{
loTail.next = e;
}
loTail = e;
++lc;
} else {
if ((e.prev = hiTail) == null){
hiHead = e;
}else{
hiTail.next = e;
}
hiTail = e;
++hc;
}
}
if (loHead != null) {//低链表头节点不为空
if (lc <= UNTREEIFY_THRESHOLD){//计数小于阈值
tab[index] = loHead.untreeify(map);//退成单向链表
}else {
tab[index] = loHead;//根节点赋值
if (hiHead != null){ // (else is already treeified)
loHead.treeify(tab);//双向链表树化
}
}
}
if (hiHead != null) {//高链表头节点不为空
if (hc <= UNTREEIFY_THRESHOLD){//计数小于阈值
tab[index + bit] = hiHead.untreeify(map);//退成单向链表并赋值到新数组高位置
}else {
tab[index + bit] = hiHead;//根节点赋值
if (loHead != null){
hiHead.treeify(tab);//双向链表树化
}
}
}
}
整体过程是将原先的单条双向链表拆解为两条双向链表,如果新双向链表节点数小于阀值UNTREEIFY_THRESHOLD=6 则将该条双向链表退化成单向链表并赋值新数组根节点,否则执行双向链表树化。
红黑树部分我们单独进行讲解。
再看下双向链表是如何退化成单向链表的,比较简单。
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
//从调用出 知道 this是根节点
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
//第一次进入 赋值头节点
if (tl == null){
hd = p;
}else{//剩下均进入的单链的构造 直到链表结束
tl.next = p;
}
tl = p;
}
return hd;
}
遍历双向链表,将TreeNode替换尾Node,执行链接操作,返回链表头节点用于赋值桶中根节点。
这也是为什么我的数据结构图中会在红黑树的结构外额外增加了双向链表的根据。
最后说一个面试的知识点,我们都知道HashMap是非线程安全,那什么情况下是非线程安全的呢?一个是在初始化双put一个是在扩容的时候。
记得关注哦,关注木左不迷路,木左带你上高速!