接着上一篇文章的内容，这篇我们将阐述hashmap在jdk1.8中的扩容机制。

jdk1.8中对hashmap有着非常棒的扩容机制，我们在上一篇文章提到了当链表长度大于某个值的时候，hashmap中的链表会变成红黑树结构，但是实际上真的是这样么？我们来看一下树化的函数是怎样进行的：

final void treeifyBin(Node
     
      [] tab, int hash) {        int n, index; Node
      
        e;        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)            resize();        else if ((e = tab[index = (n - 1) & hash]) != null) {            TreeNode
       
         hd = null, tl = null;            do {                TreeNode
        
          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);        }    }
        
       
      
     

 

我们从第一个判断语句就发现，如果hashmap中table的长度小于64（MIN_TREEIFY_CAPACITY）的时候，其实是不会进行树化的，而是对这个hashmap进行扩容。所以我们发现，扩容不仅仅用于node的个数超过threshold的时候。

这个树化函数的设计便是想保持算法设计中的相对较好。

 

要了解扩容机制，我们先来看看jdk1.7是怎么设计的，因为我用的是jdk1.8，所以一下代码是从网上摘取，如果和源码有区别，请各位告知：

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);                         //！！将数据转移到新的Entry数组里      table = newTable;                           //HashMap的table属性引用新的Entry数组      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
     
       e = src[j];             //取得旧Entry数组的每个元素          if (e != null) {              src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）              do {                  Entry
      
        next = e.next;                  int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置                  e.next = newTable[i]; //标记[1]                  newTable[i] = e;      //将元素放在数组上                  e = next;             //访问下一个Entry链上的元素              } while (e != null);          }      }  }
      
     

 

 

我们通过上面代码可以知道，我们其实是遍历这个链表，然后将新的元素位置从头位置插入。这样我们可以知道，我们链表中的先后顺序是会改变的。前后顺序会反过来。下图可以很明白的开出这种变换关系：

 

那么，关于jdk1.8，我们做了哪些优化呢？

我们一定要先明确一个很重要的东西！！jdk1.8的table长度一定是2的幂！！

也就是说在jdk1.8中 resize（）一定是扩大两倍的容量

 

我们在上篇文章中提到，jdk1.8中的索引和1.7的原则是一样的，都采用的是：h & (length - 1)作为node的索引

如果我们扩展长度为两倍，那么作为length-1就是尾端为一串1，其余为0的位序列。

那么位运算可以得到下图：

图a是扩展前产生的index，图二为扩展两倍容量的index，java1.8很巧妙的运用扩展2倍产生index这一点，我们直接判断hash值在位中，比n-1高一位的比特是1还是0来移动：

这就是上图中，红点标出的比特位便成了一种标志，我们通过判断它为0为1来进行扩容操作。红圈的16不是定值，而是原hashmap的table的长度。

 

上面的例子，也说明，我们table长度只有16的时候，有很大的情况能够让index相同，但是扩容后又不在拥有相同的index。

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置，这一点正如之前的代码所示。

 

我们可以用一张图略微表示一下，下图中蓝色为新增的index位为0，绿色的表示1：

 

当然，jdk1.8的resize代码复杂了很多，虽然大家都说它写的很好，我还是在判断语句的执行中有很多疑惑，感觉很多判断语句都是相互包含的。具体的我还要继续学习一下，但是jdk1.8中的resize（）流程还是很清晰的，怎么扩展，怎么移动链表，代码都很棒的：

final Node
     
      [] resize() {        Node
      
       [] 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({
    "rawtypes","unchecked"})            Node
       
        [] newTab = (Node
        
         [])new Node[newCap];        table = newTab;        if (oldTab != null) {            for (int j = 0; j < oldCap; ++j) {                Node
         
           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
          
           )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; 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) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
             
            
           
          
         
        
       
      
     

 

 

其实说了这么多，hashmap如果只是运用的话，我们只需要了解她的基础函数和结构即可，但是我相信对hashmap的原理有了解肯定能加强对它理解和应用，对不同情况的使用也有理解。

当然，我还是那句话，源码一定是最好的老师。