那些年，我们又爱又恨的HashMap（二）-源码篇

put() 方法较为复杂的，也是面试中最常问的方法，实现步骤大致如下：

• 计算出需要添加的元素的key的哈希值；

• 使用该哈希值结合数组长度采用位运算 hash&length-1 计算出索引值；

• 如果该位置无数据，则直接插入；

• 如果有数据，比较哈希值是否相等：

  ​ 不相等：在此索引位置划出一个节点存储数据，此为拉链法；

  ​ 相等：发生哈希冲突，使用链表或红黑树解决，调用equals()比较内容是否相同；

  ​ 相同：新值覆盖旧值；

  ​ 不相同：划出一个节点直接存储；

• 如果 size 大于 threshold ，进行扩容。

2. put() 方法源码：

public V put(K key, V value) {
    //调用putVal()方法，putVal()调用hash(key)
    return putVal(hash(key), key, value, false, true);
}
复制代码

3. hash() 方法源码：

static final int hash(Object key) {
    int h;
    /**
      * 如果key为null，返回0；
      * 如果key不为null，计算出key的哈希值并赋给h，然后与h无符号右移16位后进行按位异或得到最终哈希值
      */
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
-----------------------------------------------------------------------------------------
(h = key.hashCode()) ^ (h >>> 16)的计算过程如下所示：
假设h = key.hashCode()计算出的h为 11111111 11111111 11110000 11101010；
无符号右移，无论是正数还是负数，高位都补0；
^（按位异或运算）：相同二进制数位上相同为0，不同为1。
  11111111 11111111 11110000 11101010  //h
^ 00000000 00000000 11111111 11111111  //h >>> 16：
--------------------------------------------------------
  11111111 11111111 00001111 00010101  //返回的哈希值
复制代码

在 putVal() 方法中使用到了上述hash函数计算的哈希值。

4. putVal() 方法源码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //此处省略一千行，如果需要，请自行查看jdk源码
    if ((p = tab[i = (n - 1) & hash]) == null)  //这里使用到了上面计算得到的哈希值
    //此处省略一千行，如果需要，请自行查看jdk源码
}
-----------------------------------------------------------------------------------------
利用hash()方法返回的哈希值计算索引，(n - 1) & hash])；
n为数组长度，默认为16；
&（按位与运算）：相同的二进制数位都是1，结果为1，否则为0。
  00000000 00000000 00000000 00001111  //n - 1 = 15
& 11111111 11111111 00001111 00010101  //hash
--------------------------------------------------------
  00000000 00000000 00000000 00000101  //索引为5

复制代码

5.为什么要这样运算呢？又是无符号右移16位，又是异或，最后还要按位与，这样不是很麻烦吗？

这样做是为了避免发生哈希冲突。

如果数组长度 n 很小，假设是 16 的话，那么 n-1=15 即 1111 ，这样的值和哈希值直接按位与运算，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。

举例说明这个问题：

key.hashCode()计算出的哈希值与n - 1直接按位与运算：
  11111111 11111111 11110000 11101010  //h
& 00000000 00000000 00000000 00001111  //n - 1 = 15
--------------------------------------------------------
  00000000 00000000 00000000 00001010  //索引为10
  
再存储一个key.hashCode()计算出的哈希值，并且高16位变化很大
  11000111 10110011 11110000 11101010  //新存储的哈希值h，并且高16位变化很大
& 00000000 00000000 00000000 00001111  //n - 1 = 15
--------------------------------------------------------
  00000000 00000000 00000000 00001010  //索引仍为10

结论：直接按位与，并且哈希值的高位变化大，低位变化小甚至不变时，容易出现索引值一样的情况，进而造成哈希冲突
复制代码

二、 HashMap 中的两个重要方法源码分析

1.最难的 putVal() 源码分析：

transient Node<K,V>[] table;  //表示HashMap中的数组主体
/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key（key的哈希值）
 * @param key the key（key）
 * @param value the value to put（添加元素的值）
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
     /*
      1.transient Node<K,V>[] table;表示HashMap中的数组主体；
      2.(tab = table) == null：将空的table赋值给tab，第一次是null，结果为true；
      3.(n = tab.length) == 0：表示将数组的长度0赋值给n,然后判断n是否等于0，结果为true；
      4.由于if使用双或判断，一边为true就为true，所以执行代码 n = (tab = resize()).length; 
      5.n = (tab = resize()).length：调用resize方法对数组进行扩容，并将扩容后的数组长度赋值给n；
      6.执行完 n = (tab = resize()).length 后，数组tab的每个桶（每个索引位置）都是null。
     */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
     /*
      1.i = (n - 1) & hash：计算出索引并赋值给i，即确定元素存放在哪个桶中；
      2.p = tab[i = (n - 1) & hash]：将该索引位置上的数据赋值给节点p；
      3.(p = tab[i = (n - 1) & hash]) == null：判断索引位置上的内容是否为null；
      4.如果为null，则执行代码 tab[i] = newNode(hash, key, value, null);
     */ 
    if ((p = tab[i = (n - 1) & hash]) == null)
        //根据键值对创建新的节点，并将该节点存入桶中。
        tab[i] = newNode(hash, key, value, null);
    else {
        //执行else，说明tab[i]不等于null，表示这个位置已经有值了。
        Node<K,V> e; K k;
         /*
          1.p.hash == hash：p.hash表示已存在key的哈希值，hash表示新添加数据key的哈希值；
          2.(k = p.key) == key：将已存在数据的key的地址赋值给k，然后与新添加数据的key的地址进行比较
          3.(key != null && key.equals(k))))：执行到这里说明两个key的地址值不相等，那么先判断后				添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等
          */
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //如果两个key的哈希值相等，并且value值也相等，则将旧的元素整体对象赋值给e，用e来记录
            e = p;
         //哈希值不相等或者key的地址不相等，则判断p是否为红黑树结点
        else if (p instanceof TreeNode)
            //是红黑树几点，则放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //否则说明是链表节点
        else {
            //是链表的话需要遍历到结尾然后插入（尾插法）；采用循环遍历的方式，判断链表中是否有重复的key
            for (int binCount = 0; ; ++binCount) {
                /*
                 1.e = p.next：获取p的下一个元素赋值给e
                 2.(e = p.next) == null：判断p.next是否等于null，等于null，说明p没有下一个元素;那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键,则将该键值                    对插入链表中。
                */
                if ((e = p.next) == null) {
                     /*
                      1.p.next = newNode(hash, key, value, null)：创建一个新节点并插入到尾部；
                      2.这种添加方式也满足链表数据结构的特点，每次向末尾添加新的元素。
                    */
                    p.next = newNode(hash, key, value, null);
                     /*
                      1.节点添加完成之后判断此时节点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于则将链表转换为红黑树；
                      2.binCount表示for循环的初始值，从0开始计数，记录着遍历节点的个数；值是0表示第1个节点，1表示第2个节点，以此类推，7就表示第8个节点，8个节点则存储着9个元素；
                      3.TREEIFY_THRESHOLD-1 =8-1=7；此时如果binCount的值也是7，则转换红黑树。
                    */
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                         //转换为红黑树
                        treeifyBin(tab, hash);
                    //转化为红黑树就跳出循环
                    break;
                }
                /*
                 执行到这里说明e = p.next不是null，不是最后一个元素，继续判断链表中结点的key值与插入的数据的key值是否相等
                */
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                	 //相等，跳出for循环，不用再继续比较，直接执行下面的if (e != null)语句
                    break;
                p = e;
            }
        }
        /*
         为true表示在桶中找到key的哈希值和key的地址值与插入数据相等的结点；也就是说找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值，使用的是put方法的修改功能。
        */
        if (e != null) { // existing mapping for key（存在重复的键）
            //记录e的value
            V oldValue = e.value;
            //如果onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            //访问后回调
            afterNodeAccess(e);
            //返回旧值
            return oldValue;
        }
    }
    //记录修改次数
    ++modCount;
    //判断实际大小是否大于threshold阈值，如果大于则扩容
    if (++size > threshold)
        //扩容
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}
复制代码

2.将链表转换为红黑树的 treeifyBin() 方法源码分析：

链表什么时候转化为红黑树？在 putVal() 方法中给出了答案：

//当链表长度大于阈值8时转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    //转换为红黑树，tab表示数组名，hash表示哈希值
    treeifyBin(tab, hash);
复制代码

treeifyBin() 方法源码分析：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
     /*
      1.如果当前数组为空或者数组的长度小于64(MIN_TREEIFY_CAPACITY = 64)，则进行去扩容，而不是将链表变为红黑树；
      2.原因：如果数组很小就转换红黑树，遍历效率要低一些（红黑树结构复杂）；这时进行扩容，重新计算哈希值，将数据重新分配到数组主体中，链表长度有可能就变短了，这样做相对来说效率高一些。
      */
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //扩容方法
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        /*
         1.执行到这里说明哈希表中的数组长度大于64，开始由链表转化为红黑树；
         2.e = tab[index = (n - 1) & hash]表示将数组中的元素取出赋值给e，e是哈希表中指定位置桶里的链表节点，从第一个开始；
         3.这里hd表示红黑树的头结点，tl表示红黑树的尾结点，默认都为null。
         */
        TreeNode<K,V> hd = null, tl = null;
        do {
             //新创建一个树节点，内容和当前链表节点e一致
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                //将新创键的树节点p赋值给红黑树的头结点
                hd = p;
            else {
                /*
                  1.p.prev = tl：将上一个节点p赋值给现在的p的前一个节点；
                  2.tl.next = p：将现在节点p作为树的尾结点的下一个节点。
                    */
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
            /*
              e = e.next：将当前节点的下一个节点赋值给e,如果下一个节点不等于null，则回到上面继续取出链表中节点转换为红黑树
            */
        } while ((e = e.next) != null);
        /*
          让桶中的第一个元素即数组中的元素指向新建的红黑树的节点，以后这个桶里的元素就是红黑树而不是链表了，至此，链表转化红黑树完成
          */
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}
复制代码

上述操作一共做了如下三件事：

1.根据哈希表中元素个数确定是扩容还是树形化；

2.如果是树形化遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系；

3.然后让桶中的第一个元素指向新创建的树根节点，替换桶的链表内容为树形化内容。

三、 HashMap 的 resize() 扩容方法

1.首先，什么时候开始扩容？

当 HashMap 中的元素个数超过 n（数组长度）*loadFactor（负载因子） 时，就会进行数组扩容。 n 的默认值为 16 ， loadFactor 的默认值是 0.75 ，那么当 HashMap 中的元素个数超过 16×0.75=12 （边界值 threshold ）时，就把数组的大小扩大为原来的2倍，即32，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经知道 HashMap 中元素的个数，那么使用 HashMap 的有参构造指定初始化大小是一个不错的选择。

说明：

当 HashMap 中的一个链表长度大于8时，但数组长度没有达到64，那么 HashMap 会先扩容解决，如果已经达到了64，那么这个链表会变为红黑树，节点类型由Node变成TreeNode类型。当然，如果移除元素使红黑树的节点个数小于6时，也会再把红黑树转换为链表。

2.扩容的实质是什么？

说白了，扩容就是一个 rehash 的过程，即重新计算 HashMap 中元素的位置并分配到扩容后的 HashMap 中。

在JDK1.8之后，HashMap对 resize() 方法进行了优化，使用到了非常巧妙的 rehash 方式进行索引位置的计算。

下面分析一下这个 rehash 方式怎么巧妙？

我们知道，HashMap在扩容的时候，总是扩大为原来的两倍，这样的话，与原始HashMap相比，扩容后计算的索引只是比原来的索引多了一个bit位（二进制位）；

所以：扩容后的索引要么为原来的索引，要么变为原索引+旧容量。

如果没有看明白这句话，请看下面的例子：

例如我们将HashMap由原来的16扩展为32，变化前后索引的计算过程如下所示：
索引计算公式：index=（n-1） & hash；按位与运算：相同二进制位都为1，结果为1，否则为0
hash1（key1）： 11111111 11111111 00001111 00000101；
hash2（key2）： 11111111 11111111 00001111 00010101；
原HashMap容量n=16，   二进制表示为： 00000000 00000000 00000000 00010000；
扩容后HashMap容量n=32，二进制表示为： 00000000 00000000 00000000 00100000；
-----------------------------------------------------------------------------------------
原HashMap的key1索引：
  00000000 00000000 00000000 00001111  //n-1=16-1=15
& 11111111 11111111 00001111 00000101  //hash1（key1）
------------------------------------------------------
  00000000 00000000 00000000 00000101  //索引为5
原HashMap的key2索引：
  00000000 00000000 00000000 00001111  //n-1=16-1=15
& 11111111 11111111 00001111 00010101  //hash2（key2）
------------------------------------------------------
  00000000 00000000 00000000 00000101  //索引为5
结果：key1和可以key2的索引都为5；
-----------------------------------------------------------------------------------------
扩容后的HashMap的key1索引：
  00000000 00000000 00000000 00011111  //n-1=32-1=31
& 11111111 11111111 00001111 00000101  //hash1（key1）
------------------------------------------------------
  00000000 00000000 00000000 00000101  //索引为5
原HashMap的key2索引：
  00000000 00000000 00000000 00011111  //n-1=32-1=31
& 11111111 11111111 00001111 00010101  //hash2（key2）
------------------------------------------------------
  00000000 00000000 00000000 00010101  //索引为5+16
结果：key1的索引为5；key2的索引为 16+5，即为原索引+旧容量
复制代码

由上面的推理过程可以得出这样的结论：

元素在重新计算哈希值后，因为n变为2倍，那么n-1的标记范围在高位多 1bit （红色），因此新的index就会发生这样的变化：

即红色所示的高位为0，还是原来的索引位置；为1，索引变为原索引+旧容量。

因此，在扩容 HashMap 时，不需要重新计算哈希值，只需要看原来的哈希值新增的那个bit是1还是0就可以了，是0的话索引不变，是1的话索引变成“原索引+oldCap( 原位置+旧容量 )”，具体可以看下面16扩容32的示意图：

正是因为这样巧妙的 rehash 方式，省去了重新计算哈希值的时间，而且由于新增的 1bit 是0还是1可以认为是随机的，在 resize 的过程中保证了 rehash 之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的哈希冲突，均匀地把之前冲突的节点分散到新的桶中了。

3.扩容方法 resize() 源码分析：

看完了上面的扩容原理，再来看源码会容易些。

不要看这个方法长，觉得难就看不下去了，静下心，好好分析完，对自己的技术肯定有提升，我们开始吧！

final Node<K,V>[] resize() {
    //得到当前数组
    Node<K,V>[] oldTab = table;
    //如果当前数组为null返回0，否则返回当前数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //当前边界值，默认是12(16*0.75)
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果旧数组长度大于0，则开始计算扩容后的大小
    if (oldCap > 0) {
        //如果旧数组长度大于最大值，就不再扩容，就只好随你碰撞去吧！
        if (oldCap >= MAXIMUM_CAPACITY) {
            //修改边界值为Integer数据类型的最大值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        /*
         没超过最大值，就扩充为原来的2倍;
         1.(newCap = oldCap << 1) < MAXIMUM_CAPACITY：扩大到2倍之后容量是否小于最大容量
         2.oldCap >= DEFAULT_INITIAL_CAPACITY：旧数组长度是否大于等于数组初始化长度16
        */
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //旧边界值左移一位，相当于扩大一倍
            newThr = oldThr << 1; // double threshold
    }
    //旧边界值大于0则直接赋值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;//16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //计算新的resize最大上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //新的边界值原来默认是12，扩大一倍变为24
    threshold = newThr;
    //创建新的哈希表
    @SuppressWarnings({"rawtypes","unchecked"})
        //newCap是扩容后的数组长度32
        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) {
                //将旧数组中的数据都置为null，便于GC回收
                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 {
                    //不是红黑树，则采用链表处理冲突
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                     //通过上述讲解的原理来计算节点的新位置
                    do {
                        //原索引
                        next = e.next;
                        //如果为true，则e这个节点在扩容后还是原索引位置，说明高位为0
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //原索引+旧容量，说明高位为1
                        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) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

复制代码