HashMap 在 JDK 1.8 与 JDK 1.7 上实现的差异比较

上篇文章 HashMap 基于 JDK 1.7 源码解析对 HashMap 做了基本的分析，但是在 JDK 1.8 之后 HashMap 发生了一些变化，主要做了一些微小比较大的贡献优化，本文主要关注的是发生变更的地方。

数据结构

通过上篇文章我们知道 HashMap 底层实现的数据结构是 $\color{red}{数组}$ + $\color{red}{链表}$ 的方式，但是这样带来的一个问题是当发生哈希碰撞后链表过长，从而影响索引效率，因此在 Java 1.8 引入了红黑树，利用红黑树快速增删查改的特点，在链表过长的时候将其转换为红黑树，默认是链表的长度大于 8 的时候就转换。
因此 JDK 1.8 HashMap 的数据结构是 $\color{red}{数组}$ + $\color{red}{链表}$ + $\color{red}{红黑树}$ 。而且出现哈希碰撞时插入数据的方式是尾插法，而 JDK 1.7 是头插法。

Hash 值的计算方式

JDK 1.7 进行了多次扰动高位运算，4 次位运算 + 5 次异或运算，源码如下：

 static final int hash(int h) {
   h ^= k.hashCode(); 
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4)
 }

JDK 1.8 只进行 2 次扰动运算，1 次位运算 + 1 次异或运算，通过 hashcode() 的高 16 位异或低 16 位实现的，这么做考虑了速度、功效和质量，在数组 table 的 length 比较小的时候，也能保证高低 bit 都参与到 Hash 的计算中，同时不会有太大的开销。源码如下：

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

扩容机制

扩容即重新计算容量，JDK 1.7 进行扩容时会按照原来方法进行重新计算，即 hashCode() —> 高位扰动运算 —> （h & table.length - 1）重新确定索引，而且旧链表迁移新链表的时候，如果在新表的数组索引位置会倒置。源码如下：

   void resize(int newCapacity) { //传入新的容量
        Entry[] oldTable = table;  //引用扩容前的 Entry 数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到（2^30）了
            threshold = Integer.MAX_VALUE;  //修改阈值为 int 的最大值（2^31-1），这样以后都不会扩容了
            return;
        }

        Entry[] newTable = new Entry[newCapacity];  //初始化一个新的 Entry 数组
        transfer(newTable); //用来将原先table的元素全部移到newTable里面
        table = newTable;  //再将newTable赋值给table
        threshold = (int)(newCapacity * loadFactor);//修改阈值
    }

transfer() 方法使用一个容量更大的数组来代替已有的容量小的数组，源码如下：

 void transfer(Entry[] newTable) {
     Entry[] src = table;                   //src引用了旧的Entry数组
     int newCapacity = newTable.length;
     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
         Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
         if (e != null) {
             src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
             do {
                 Entry<K,V> next = e.next;
                 int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                 e.next = newTable[i]; //标记[1]
                 newTable[i] = e;      //将元素放在数组上
                 e = next;             //访问下一个Entry链上的元素
             } while (e != null);
         }
     }
 }

但是经过观测可以发现，使用 2 次幂扩展（指长度扩大位原来 2 倍），元素要么是在原位置，要么是在原位置再移动 2 次幂的位置。如下图所示，n 为 table 的长度，图（a）表示扩容前的 key1 和 key2 两种确定索引位置的示例，，其中 hash 1 是 key1 对应的哈希与高位运算结果。

元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的 mask 范围在高位多 1 bit（红色），因此新的 index 就会发生如下图的变化：

因此，在扩充 HashMap 的时候，不需要像 JDK 1.7 的实现那样重新计算 hash，只需看看原来的 hash 值新增那个 bit 是 1 还是 0 就好了，是 0 的索引没变，是 1 的话索引变成 “原索引 + oldCap”。这样既省去了重新计算 hash 值得时间，而且同时，由于新增得 1 bit 是 0 还是 1 可以认为是随机得，因此 resize 的过程中，均匀的把之前的冲突节点分散到新的 bucket 了，源码如下：

 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;
         }
         // 没超过最大值，就扩充为原来的2倍
         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);
     }
     // 计算新的resize上限
     if (newThr == 0) {
 
         float ft = (float)newCap * loadFactor;
         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                   (int)ft : Integer.MAX_VALUE);
     }
     threshold = newThr;
     @SuppressWarnings({"rawtypes"，"unchecked"})
         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
     table = newTab;
     if (oldTab != null) {
         // 把每个bucket都移动到新的buckets中
         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 { // 链表优化重hash的代码块
                     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;
                         }
                         // 原索引+oldCap
                         else {
                             if (hiTail == null)
                                 hiHead = e;
                             else
                                 hiTail.next = e;
                             hiTail = e;
                         }
                     } while ((e = next) != null);
                     // 原索引放到bucket里
                     if (loTail != null) {
                         loTail.next = null;
                         newTab[j] = loHead;
                     }
                     // 原索引+oldCap放到bucket里
                     if (hiTail != null) {
                         hiTail.next = null;
                         newTab[j + oldCap] = hiHead;
                     }
                 }
             }
         }
     }
     return newTab;
 }

结语

以上就是 HashMap 在 JDK 1.7 与 JDK 1.8 主要的实现差异，当然还有一些细节不同，有兴趣的同学可以自行对比源码研究一波。