HashMap扩容原理

这里只截取链表元素的再分配源码 “(e.hash & oldCap) == 0” 来说说个人理解：

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;
  }

• 源码： (e.hash & oldCap) == 0 分析：
  • 此源码的目的就是要判断元素是需要重新分配；
  • 下边所有的计算都是基于int类型，即32位二进制的计算方式，部分二进制有所简化方便观察计算
  • 以oldCap = 16 = 10000，元素A.hash = 00011011 00001011 , 元素B.hash = 00011011 00011011 为例
  • 计算元素在数组中的位置方法：hash & (oldCap - 1) ， 此时数组下标位置取决于hash值的低4位，如下A、B的案例
  • A元素的索引index = A.hash & (oldCap - 1) = 00011011 00001011 & 00000000 00001111 = 1011 = 11
  • B元素的索引index = B.hash & (oldCap - 1) = 00011011 00011011 & 00000000 00001111 = 1011 = 11
  • 我们用A元素执行我们分析的源码：(A.hash & oldCap) = 00011011 00001011 & 00000000 00010000 = 0
  • 我们用B元素执行我们分析的源码：(B.hash & oldCap) = 00011011 00011011 & 00000000 00010000 = 1
  • 此时数组扩容：newCap = oldCap<<1 = 32 = 100000, 数组的下标位置取决于hash值的低5位，再来计算元素的下标位置就会发现值不对了
  • A元素的索引index = A.hash & (newCap - 1) = 00011011 00001011 & 00000000 00011111 = 01011 = 11
  • B元素的索引index = B.hash & (newCap - 1) = 00011011 00011011 & 00000000 00011111 = 11011 = 27
  • 如果不从新分配元素，那我们以后访问table[27]的时候就找不到元素
  • 什么元素需要分配，什么元素又不需要分配呢？ 我们上边用源码（e.hash & oldCap）执行了两A和B元素；
  • 我们发现A元素执行(A.hash & oldCap)后的结果为0，而且A元素的索引与我们在扩容后的索引一致，也就是说为0则不需要进行从新分配
  • 我们发现B元素执行(B.hash & oldCap)后的结果为1，B元素原来的索引与我们在扩容后计算出的索引不一致，也就是说不为0则需要进行从新分配
  • 以上述元素A为例，(A.hash & oldCap) = (00011011 00001011 & 00000000 00010000) = 0 ，会发现结果是否为0取决于hash值的从右往左第5位是不是0
  • 例如现在我们又需要进行扩容，oldCap = 32 ， 此时需不需要扩容则取决于hash值从右往左的第6位是不是0，为0则不需要
  • 不得不说源码的设计很巧妙，不过需要注意的是JDK1.7和JDK1.8扩容会有区别，1.7的头插法扩容方式在多线程环境下会有链表死循环的风险，1.8使用尾插法很好的解决了该问题；
  • 元素从新分配的两个好处是，使得索引计算公式成为固定，我们只需要关注元素位置在扩容时的变化，另外元素再散列可以提高访问速度
  • 以上是个人理解，如有不对的理解欢迎讨论；