HashMap hash碰撞扩容全解

3.7 更新 hasmap 链表变成红黑树 treeifyBin 方法

此时启动debug模式，点force step into 进入方法内部

此时算出key的hash值

代码语言：javascript复制

此时( tab = table ) != null 进入下一句 if
此时出现hash冲突 p = tab [i = (n-1) & hash] , p != null
跳过当前的if

代码语言：javascript复制

1.判断p的hash值是否与传入的hash值相等，并且判断key是否相等，如果相等则 e = p
2.判断 p 判断为 红黑树的实例
3.出现hash碰撞，判断 p.next 也就是 p的下一个节点是否为空， 为空就新建节点，如果p的下一个节点不为空
判断hash是否相等和key是否相等，当出现p.next 不为空 并且，下一个节点也不等于hash 和 key时， 将 p 节点 向下
移动到e的位置，继续for循环

代码语言：javascript复制

当e！=null 说明 出现hash 碰撞 出现 重复的 值 和 单纯的重复值，则返回旧值

代码语言：javascript复制

我们插入的元素为第13个元素，触发resize（）重新分配元素

代码语言：javascript复制

我们的旧值为:
oldCap = 16 //最大容量
oldthr = 12 //触发扩容阈值
通过上述方法扩容之后：
newCap = 32
newThr = 24

代码语言：javascript复制

此时重新分配数组上面的链表节点元素 ，把旧节点数组的不为空的头节点全部置空， 当其没有next节点时，为其在
新数组上分配位置，如果有next节点，则继续操作

代码语言：javascript复制

此时涉及更换节点位置算法

代码语言：javascript复制

Node<K,V> loHead = null, loTail = null; //为下标不到的节点头和节点尾部

代码语言：javascript复制

Node<K,V> hiHead = null, hiTail = null; //下标发生改变的节点头和节点尾部

代码语言：javascript复制

先拼接节点组成链表

代码语言：javascript复制

原来旧节点数组的链表节点被全部更换，下标改变的节点在偏移量=旧数组长度 原来的位置

-----------------------------------------------------------------------------------3.7更新------------------------------------------------------------------------------

当链表的的binCount >= 7时（从0计数），传入当前数组下标位置的hash值和数组，

代码语言：javascript复制

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

代码语言：javascript复制

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 转换为红黑树

全文结束

hashmap

0 人点赞

HashMap hash碰撞 扩容 全解

HashMap hash碰撞扩容全解