JDK1.8HashMap源码学习-put操作以及扩容(一)

木左

修改于 2020-10-20 16:53:48

5220

修改于 2020-10-20 16:53:48

文章被收录于专栏：木左侃技术人生木左侃技术人生

“本文将主要介绍HashMap的put操作以及相应的扩容。”

前文链接地址:

JDK1.8HashMap源码学习-数据结构

JDK1.8HashMap源码学习-初始化

我们先看下HashMap的hash方法。在之后的源码阅读中会经常看到。

以下是采用知乎“胖君”的高赞回答。原文地址

key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。2进制32位带符号的int表值，右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。 https://www.zhihu.com/question/20733617

算出的hash值范围还是比较大，而我们的数组长度有限，需要做取模运算，类似 100%16 = 4 而源码采用的&操作，因为数组的长度是2的整数幂，减去1正好是一个“低位掩码”。&操作高位全部归零，只保留低位值。计算后正好是下标索引。

—

put操作

直接看下put的源码如下:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

多么简洁，直接调用另一个方法了putVal了。下面就是我们的主角登场了。

/**
* 真正执行put的操作
* hash key的hash值 是通过hash函数计算得出
* key 我们要放入的key
* value 要放入的值
* onlyIfAbsent true 不覆盖存在key的值 
*              false 覆盖存在key的值
*              put传入的false 即覆盖
* evict false 则处于创建模式 put传入true
*       留给了子类去扩展使用
*/
final V putVal(int hash, K key, V value, 
    boolean onlyIfAbsent, boolean evict) {
    
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判断Node数组是否为空 为空则进行初始化
    if ((tab = table) == null || (n = tab.length) == 0){
        n = (tab = resize()).length;
     }
    //如果对应数组下标的数据为空 则直接放入 而且放入的是单链的头节点
    if ((p = tab[i = (n - 1) & hash]) == null){
        tab[i] = newNode(hash, key, value, null);
     }else {
        //e是我们要查找的已存在的key节点
        Node<K,V> e; K k;
        //头节点判断 和要放入数据key的hash和key相等
        //已存在 赋值到临时变量
        if (p.hash == hash 
            && ((k = p.key) == key 
            || (key != null && key.equals(k)))){
            e = p;
        //如果是树的节点 执行树节点的放入操作
        }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);
                    //判断是否达到出发链表转红黑树的阈值
                    //是的话就调用转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1){ // -1 for 1st
                        treeifyBin(tab, hash);
                    }
                    //退出继续循环
                    break;
                 }
                //如果下一节点的hash一致且key相等 则说明原先存在 退出循环
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
                    break;
                }
                //执行移动到下一个节点 接着循环
                p = e;
            }
        }
        //e不为空 说明原先存在key相同的节点 执行是否覆盖操作
        if (e != null) { // existing mapping for key
            //去除旧值
            V oldValue = e.value;
            //判断是否允许覆盖原值
            if (!onlyIfAbsent || oldValue == null){
                 //覆盖旧值
                e.value = value;
             }
            //无操作 留给子类去扩展
            afterNodeAccess(e);
            //返回旧值
            return oldValue;
        }
    }
    //变更次数+1
    ++modCount;
    //容量+1 如果已经达到阈值 就执行扩容操作
    if (++size > threshold){
        resize();
    }
    //无操作 留给子类去扩展
    afterNodeInsertion(evict);
    return null;
}

为了方便，我们的节点仅展示hash值，而且put值走的路径是在一个桶中增加值，达到容量阀值后先进行数组扩容，直到数组长度达到64，然后接着在该桶中增加值，链表长度达到8后，触发该桶从单向列表转变为双向列表再树化，这样我们可以把主要的情况都涉及到。

先看下准备的插入节点的准备hash值，6%16=6，22%16=6 以此类推。当我们第一次put值，即hash为6的时候，因为数组并没有初始化，先会初始化一个长度为16的数组，接着计算放入的key的数组下标是多少，即

i = (n - 1) & hash] 计算出下标后判断该数组下标中是否有节点，如果没有则直接创建一个节点并赋值到该数组下标中。即

tab[i] = newNode(hash, key, value, null);

接着完成了数组变更次数加1 即

++modCount;

容量值加1，如果容量值大于阀值则触发扩容操作，即

if (++size > threshold){ resize(); }

返回空因为不存在旧值。我们看下现在的结构图

接着我们放入第二个，此时数组不为空且桶中的根节点不为空，则会判断根节点是否是一个树的节点，即

}else if (p instanceof TreeNode){
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

如果是一个树的节点，就会执行树的put操作，我们现在明显还不是，就会进入到下面的代码中

}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;
         }
         //如果下一节点的hash一直且key相等 则说明原先存在 退出循环
         if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
             break;
          }
          //执行移动到下一个节点 接着循环
          p = e;
      }
}

即执行单向链表的挂载操作，刚进入循环p代表的是根节点前面判断根节点是否为空进行的赋值操作，将p的下一节点赋值给e，

如果为空则直接创建新的节点并挂载到p节点的后面，接着判断桶中原节点数是否大于等于7 ，因为这个时候虽然节点挂载完成，但是节点的计数并没有加1 如果满足条件则调用转红黑树操作，还有个另外一个条件是在treeifyBin方法中，稍后解释。

如果不为空，则判断hash值和key时候一致，如果一致直接退出循环，说明key已经存在，是否替换值退出循环后有处理。如果hash值和key不一致则将p赋值为e，即指向p的下一节点，继续循环操作。直到完成挂载或者找到存在的key。

在退出循环后，如果是已存在的key，根据条件判断是否覆盖原值，HashMap是覆盖原值并返回旧值。最后完成的是统一操作，数组变更次数加1和容量值加1以及判断是否扩容。

接着我们继续执行put操作，将一系列值均put到数组下标为6的桶中。直到该桶中的节点数达到8。也就是会调用treeifyBin方法，我们简单的看下这个方法

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();
    }
    ... 
}

发现一进来的判断条件是判断数组是否为空以及数组的长度是否小于MIN_TREEIFY_CAPACITY即64，如果有任意一个条件满足就调用扩容，我们现在的情况是数组不为空但是长度才16，于是我们执行了非空数组扩容。

—

非空数组扩容(仅单向链表)

此时我们的数据结构图如下

接来下我们来到了非空扩容

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        //已经达到数组的最大长度值 不再进行扩容 直接使用旧数组
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
            //数组容量直接扩大为原先的两倍 且小于最大容量 而且旧数组的容量也大于等于最大容量
        }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY 
            && oldCap >= DEFAULT_INITIAL_CAPACITY){
            //使用率阈值也扩大为原先的两倍
            newThr = oldThr << 1; // double threshold
        }
    }else if (oldThr > 0){ // initial capacity was placed in threshold
            newCap = oldThr;
    }else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //原数组下标保存数据不为空 执行数据从旧数组下标到新数组下标的迁移
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;//旧数组下标数据清空
                if (e.next == null){//如果根节点的下一节点为空 说明只有一个节点数据 直接计算新数组下标位置并放入
                    newTab[e.hash & (newCap - 1)] = e;
                }else if (e instanceof TreeNode){//如果是红黑树 执行红黑树数据迁移
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                }else{ // preserve order 都不是就是单向链表 行拆链
                    //loHead 低位置(下标)头节点 loTail 低位置(下标)尾节点 但是是一致移动变化的 直到最后
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;//同上 只不过是高位置链
                    Node<K,V> next;
                    //将原先的单链拆分成了双链 因为数据扩大了两倍 原先的单链可能会拆分为双链 然后移动另一条链到新的数组下标位置
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {//符合低位置
                            if (loTail == null){//第一次进入 符合低位置链 赋值低位置链的头节点
                                loHead = e;
                            }else{//其他则是在低位置链后追加
                                loTail.next = e;
                            }
                            loTail = e;//移动链到链条尾部
                         }else {//符合高位置
                            if (hiTail == null){//第一次进入 赋值头节点
                                hiHead = e;
                            }else{//其他在高位置链后追加
                                hiTail.next = e;
                            }
                            hiTail = e;//移动链到链条尾部
                        }
                    } while ((e = next) != null);//只要链条没有结束 就一直循环
                    
                    if (loTail != null) {//如果低位置链尾节点不为空 则赋值尾节点的下一节点为空 并将低位置链的头节点放到新数组原位置处
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {//如果高位置链尾节点不为空 则赋值尾节点的下一节点为空 并将高位置的头节点放到新数组原位置+旧数组长度处 以为扩容是2倍
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

此时我们的数组不为空即长度大于0，则判断数组长度是否已经达到最大值，如果已经达到最大值，而赋值阀值为最大值并返回，即不再进行扩容操作。

如果没有则直接进行原数组长度左移1位，即扩容为原先的两倍，接着做了判断，如果新数组的长度小于数组长度最大值且旧数组长度大于等于默认值16，则阀值也直接左移一位，扩容为原先的两倍。否则新阀值为0，交给后面进行计算。

if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY 
        && ft < (float)MAXIMUM_CAPACITY ? 
        (int)ft : Integer.MAX_VALUE)
}

如果新阀值为空，采用新数组长度乘以数组使用率，如果新数组长度小于最大长度且新阀值小于数组最大容量，则直接取int值即可，否则赋值为最大值。最后赋值给我们的成员变量。

接着用新计算的数组长度创建新的数组，并赋值给成员变量，即

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

在接下来就是进行我们数据拆分，此时我们的数组长度变为了32，那么针对新的数组长度，原先放入的key值hash与新长度取余下标可能就有新的值，比如，6%32=6，54%32=22，那么就是遍历旧数组每个桶中的每个节点的值，然后重新计算位置，并进行操作。

如果原数组桶中节点为空，则继续下一个桶
如果不为空，则赋值桶中根节点到临时变量e 并赋值原桶根节点为空
判断临时节点e是否有后续节点，如果没有则直接计算新的数组下标并存入，继续下一个桶
e没有后续节点判断临时节点e是否是树节点，是则执行树的裁剪操作(后面我们再讲)
如果e不是树节点，那就是单向链表，这遍历单向链表，将一条链可能转换为两条链。

我们先看下单向链表的迁移操作

//loHead 低位置(下标)头节点 loTail 低位置(下标)尾节点 但是是一直移动变化的 直到最后
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;//同上 只不过是高位置链
Node<K,V> next;
//将原先的单链拆分成了双链 因为数据扩大了两倍
// 原先的单链可能会拆分为双链 然后移动另一条链到新的数组下标位置
  do {
     next = e.next;
     if ((e.hash & oldCap) == 0) {//符合低位置
         if (loTail == null){//第一次进入 符合低位置链 赋值低位置链的头节点
             loHead = e;
         }else{//其他则是在低位置链后追加
             loTail.next = e;
         }
         loTail = e;//移动链到链条尾部
     }else {//符合高位置
         if (hiTail == null){//第一次进入 赋值头节点
             hiHead = e;
         }else{//其他在高位置链后追加
             hiTail.next = e;
          }
          hiTail = e;//移动链到链条尾部
      }
   } while ((e = next) != null);//只要链条没有结束 就一直循环
                        
   if (loTail != null) {//如果低位置链尾节点不为空 则赋值尾节点的下一节点为空 并将低位置链的头节点放到新数组原位置处
       loTail.next = null;
       newTab[j] = loHead;
   }
   if (hiTail != null) {//如果高位置链尾节点不为空 则赋值尾节点的下一节点为空 并将高位置的头节点放到新数组原位置+旧数组长度处 以为扩容是2倍
       hiTail.next = null;
       newTab[j + oldCap] = hiHead;
   }

过程就是遍历链表，判断(e.hash & oldCap) == 0，按位与，两个数是二进制，如果相同位数都是1则该位结果是1否则为0。而oldCap是2的幂次方，比如16，二进制为0000 0000 0000 0000 0000 0000 0001 0000，那么其他数与该值进行&操作时，除去1的位置，其他的都是0。如果其他数该位置为0则&结果即为0，否则为该容量值。通过这个判断将单条链表拆解成了两条链表，初入时链表的头节点为空，赋值头节点，接着赋值尾节点为当前节点，即移动尾节点到新链表的尾部，接着做下一次遍历操作，直到遍历结束。

最后将两条链表的头节点放入到新的数组桶中的根节点。原低位链表位置不变，直接为新数组的原桶，而高位链表就是低位链表位置+原数组容量，通过6%32=6，54%32=22，6+16=22 我们可以进行类比理解。这也是为什么扩容的时候直接扩容为2倍。非常容易操作，而节点也可以均匀的分布在各个桶中。

此时我们的数据结构下图