3.7 更新 hasmap 链表 变成 红黑树 treeifyBin 方法
此时启动debug模式,点force step into 进入方法内部
此时算出key的hash值
此时( tab = table ) != null 进入下一句 if
此时出现hash冲突 p = tab [i = (n-1) & hash] , p != null
跳过当前的if
1.判断p的hash值是否与传入的hash值相等,并且判断key是否相等,如果相等则 e = p
2.判断 p 判断为 红黑树的实例
3.出现hash碰撞,判断 p.next 也就是 p的下一个节点是否为空, 为空就新建节点,如果p的下一个节点不为空
判断hash是否相等和key是否相等,当出现p.next 不为空 并且,下一个节点也不等于hash 和 key时, 将 p 节点 向下
移动到e的位置,继续for循环
当e!=null 说明 出现hash 碰撞 出现 重复的 值 和 单纯的重复值,则返回旧值
我们插入的元素为第13个元素,触发resize()重新分配元素
我们的旧值为:
oldCap = 16 //最大容量
oldthr = 12 //触发扩容阈值
通过上述方法扩容之后:
newCap = 32
newThr = 24
此时重新分配数组上面的链表节点元素 ,把旧节点数组的不为空的头节点全部置空, 当其没有next节点时,为其在
新数组上分配位置,如果有next节点,则继续操作
此时涉及更换节点位置算法
Node<K,V> loHead = null, loTail = null; //为下标不到的节点头和节点尾部
Node<K,V> hiHead = null, hiTail = null; //下标发生改变的节点头和节点尾部
先拼接节点组成链表
原来旧节点数组的链表节点被全部更换,下标改变的节点在偏移量=旧数组长度+原来的位置
-----------------------------------------------------------------------------------3.7更新------------------------------------------------------------------------------
当链表的的binCount >= 7时 (从0计数),传入当前数组下标位置的hash值 和 数组,
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
}
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();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
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);
}
}
使用尾插法 将 所有链表上的元素转化为 双链表 再调用 treeify 转换为 红黑树
全文结束
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。