hashmap何时扩容,扩容的算法(hashmap扩容时每个entry需要再计算一次hash吗?)

一、resize()源码及详细分析二、问题分析与核心代码详解

final Node[] resize() {
    //oldTab : 引用扩容之前的哈希表
    Node[] oldTab = table;
    //oldCap : 引用扩容之前的table数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //oldThr : 引用扩容之前的扩容阈值
    int oldThr = threshold;
    //newCap : 新的数组长度
    //newThr : 新的扩容阈值
    int newCap, newThr = 0;
    //oldCap大于0 代表了：hashMap中的哈希表已经初始化过了，是一次正常扩容
    if (oldCap > 0) {
        //如果当前数组的长度已经大于最大table长度
        //设置扩容阈值为int的最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //如果当前数组长度小于table最大长度
        //设置新的table大小为原来长度的2倍
        //如果扩容后的newCap小于数组的最大值限制，并且原数组大小大于等于16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //设置新的扩容阈值为原来的2倍
            newThr = oldThr << 1; // double threshold
    }
    //oldCap=0的情况(说明hashMap中的散列表为null)
    //这三种构造方法时oldCap==0 并且 oldThr扩容阈值已经有大小了
    // 1.new HashMap(initCap,loadFactor)
    // 2.new HashMap(intiCap)
    // 3.new HashMap(map) 并且Map有数据
    else if (oldThr > 0) // initial capacity was placed in threshold
        //把新的table大小设置为扩容前的扩容阈值
        newCap = oldThr;
    //oldCap==0 && oldThr==0 
    //那就意味着这个else里是为默认构造方法用的 new HashMap()
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果newThr==0，就通过公式
    //threshold = capacity * loadFactor计算一个新的扩容阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //把新的扩容阈值赋值给threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    	//创建一个大小为newCap的新数组
        Node[] newTab = (Node[])new Node[newCap];
    //更新table的引用
    table = newTab;
    //如果oldTab不为null，说明hashMap扩容之前，table不为null，也就是有数据
    //把原来数据导入新哈希表中的操作:
    if (oldTab != null) {
        //迭代原数组
        for (int j = 0; j < oldCap; ++j) {
            //当前node节点
            Node e;
            //如果当前迭代的桶节点不为null
            //把原来数据存到临时节点e中
            if ((e = oldTab[j]) != null) {
                //把原来的数据置空，等待GC回收
                oldTab[j] = null;
                //此处判断是单个元素
                if (e.next == null)
                    //就直接计算下标，找到新table中的下标位置，并把e直接存进去
                    newTab[e.hash & (newCap - 1)] = e;
                //此处判断是树化
                else if (e instanceof TreeNode)
                    //扔树里
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                //此处判断是链表
                else { // preserve order
                    //设置低位首节点和低位尾节点
                    Node loHead = null, loTail = null;
                    //设置高位首节点和高位尾节点
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        //如果与运算等于0
                        if ((e.hash & oldCap) == 0) {  //e.hash & oldCap下文会举************
                            //低位尾节点是null的话 就把e赋给低位首节点
                            if (loTail == null)
                                loHead = e;
                            //低位尾节点不是null的话 证明已经遍历了
                            else
                                //把低位尾节点的next设置为e
                                loTail.next = e;
                            //所以本次的e就成为了低位尾节点
                            loTail = e;
                        }
                        //如果按位与运算不等于0
                        else {
                            //判断高位尾节点是否为null 为null就把e赋给高位首节点
                            if (hiTail == null)
                                hiHead = e;
                            //高位尾节点不是null时，证明已经遍历了
                            else
                                //e接在高位尾节点后边
                                hiTail.next = e;
                            //此时应把e声明成为高位尾节点
                            hiTail = e;
                        }
                        //循环到没有下一个节点为止
                    } while ((e = next) != null);
                    //如果低位尾节点不为null
                    if (loTail != null) {
                        //这个低位尾节点也没有后继节点了
                        loTail.next = null;
                        //就把首节点赋值给新数组下标为j的桶，和旧数组位置一样
                        //也可想象为以首节点为引导把整个一条链表全都放到新table了
                        newTab[j] = loHead;
                    }
                    //如果高位尾节点不为null
                    if (hiTail != null) {
                        //这个高位尾节点也没有后继节点了
                        hiTail.next = null;
                        //就把首节点赋值给新数组下标为[j+oldCap]的桶，也就是原下标+原table.Length
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

问题1：为什么需要扩容？

当元素越来越多的时候，hashmap查找速度就从O(1) => 0(N)，也就是链化严重了为了解决哈希冲突带来的查询效率下降，所以进行扩容。

问题2：什么时候需要扩容？

延迟初始化用到了resize() ：第一次调用putVal时会初始化hashmap。size大小超过threshold扩容阈值时，会进行扩容操作。我在上一篇中有所提及：put方法详解.

处代码详解：
核心:e.hash & oldCap 为什么能把原来的链表一分为二变成高低两个链表？

首先 计算下标位置的运算为 hash & (length-1)

eg: oldTab=16

(1)

1111 1010 0000 1111 0000 1111 1100 1111 ---->1号e.hash的二进制 

0000 0000 0000 0000 0000 0000 0000 1111 -----(16-1)的二进制 

=>

0000 0000 0000 0000 0000 0000 0000 1111 => 15

所以下标位置是15 

(2)

1111 1010 0000 1111 0000 1111 1101 1111 ---->2号e.hash的二进制 

0000 0000 0000 0000 0000 0000 0000 1111 -----(16-1)的二进制 

=>

0000 0000 0000 0000 0000 0000 0000 1111 => 15

虽然(1)和(2)的**hash值**不同，但是算出的**下标i是相同的**

这也就意味着hash & (length-1)只与(length-1)的**最高位到最低位的位数有关** 当前位数就是4

==所以这也解释了两个hash值不同的元素一样可以放到同一个桶中。==

接下来 扩容会把链表拆分到新table中，那么是怎么拆分的呢？

e.hash & oldCap 为什么能把原来的链表一分为二变成高低两个链表？

带着两个疑问接着往下看：

源码中
e.hash & oldCap==0则 接 低 位 链 表
e.hash & oldCap!=0 则 接 高 位 链 表

还用(1) (2)的hash举例子

(1)

1111 1010 0000 1111 0000 1111 1100 1111 ---->1号e.hash的二进制 

0000 0000 0000 0000 0000 0000 0001 0000 -----16的二进制 

=>

0000 0000 0000 0000 0000 0000 0000 0000 => 0

由计算结果可知接低位 看下方源码

//低位尾节点是null的话 就把e赋给低位首节点
						  if (loTail == null)
                                loHead = e;
                            //低位尾节点不是null的话 证明已经遍历了
                            else
                                //把低位尾节点的next设置为e
                                loTail.next = e;
                            //所以本次的e就成为了低位尾节点
                            loTail = e;
-----------------------------------------------------------------------------------------------
						//如果低位尾节点不为null
    					if (loTail != null) {
                            //这个低位尾节点也没有后继节点了
                            loTail.next = null;
                            //就把首节点赋值给新数组下标为j的桶，和旧数组位置一样
                            //也可想象为以首节点为引导把整个一条链表全都放到新table了
                            //[X]重点！！
                            newTab[j] = loHead;
                   		  }

重点：代码[x]处

把此节点放到了新数组newTab[j]位置 也就是在oldTab和newTab的下标是一样的。

为什么会保持原位呢？

table扩容16 -> 32

扩容后hash值没变，只是数组长度变了，所以我们再算一次在新数组中的下标

1111 1010 0000 1111 0000 1111 1100 1111 ---->e.hash & oldCap==0中参与计算的e.hash值的二进制 

0000 0000 0000 0000 0000 0000 0001 1111 -----(32-1)的二进制 

=>

0000 0000 0000 0000 0000 0000 0000 1111 => 15

下标还是15，由此可见当计算e.hash & oldCap等于0的时参与计算的hash值在扩容后计算的下标还是原位置

所以在新数组中保持了原位。

(2)

1111 1010 0000 1111 0000 1111 1101 1111 ---->2号e.hash的二进制 

0000 0000 0000 0000 0000 0000 0001 0000 -----16的二进制 

=>

0000 0000 0000 0000 0000 0000 0001 0000 => 16

由计算结果可知接高位 看下方源码

//判断高位尾节点是否为null 为null就把e赋给高位首节点
                            if (hiTail == null)
                                hiHead = e;
                            //高位尾节点不是null时，证明已经遍历了
                            else
                                //e接在高位尾节点后边
                                hiTail.next = e;
                            //此时应把e声明成为高位尾节点
                            hiTail = e;
---------------------------------------------------------------------------------------------
                            //如果高位尾节点不为null
                            if (hiTail != null) {
                                //这个高位尾节点也没有后继节点了
                                hiTail.next = null;
                                //就把首节点赋值给新数组下标为[j+pldCap]的桶，和旧数组位置一样
                                //[X]重点！！
                                newTab[j + oldCap] = hiHead;
                            }

重点：代码[x]处

也就是把此node放到了新数组newTab[j + oldCap]这个位置 这个下标也就是[原数组下标位置+原数组长度]

为什么会放在下标为(原数组下标位置+原数组长度)上呢？
table扩容16 -> 32

扩容后hash值没变，只是数组长度变了，所以我们再算一次在新数组中的下标

1111 1010 0000 1111 0000 1111 1101 1111 ---->e.hash & oldCap!=0中参与计算的e.hash值的二进制 

0000 0000 0000 0000 0000 0000 0001 1111 -----(32-1)的二进制 

=>

0000 0000 0000 0000 0000 0000 0001 1111 => 31   --->(15 + 16)

下标是31

所以由此可知e.hash & oldCap!=0时参与计算的hash值在扩容后计算的下标为(原数组下标位置+原数组长度)

所以放newTab[j + oldCap]位置上了。

所以也可知e.hash & oldCap 的计算 真正和e.hash参与运算的也就是oldCap的最高位到最低位的位数：5

本博客仅供学习参考，也是个人笔记总结，如果错误请见谅~~