Jdk1.7HashMap如何扩容及解决死循环问题

上一篇 <<<Jdk1.7HashMap源码分析
下一篇 >>>

扩容原理

初始容量默认为16，负载因子默认为0.75，HashMap在扩容时，新数组的容量将是原来的2倍
负载因子越小，容易扩容，浪费空间，但查找效率高 链表特别短 减少hash冲突
负载因子越大，不易扩容，对空间的利用更加充分，查找效率低（链表拉长）hash冲突比较多，链表比较长
由于容量发生变化，原有的每个元素需要重新计算数组索引Index，再存放到新数组中去，这就是所谓的rehash。

扩容逻辑步骤

1、条件：map节点大小size>=阈值threshold，并且当前添加节点的数组下标已经存在数据的情况下才可以扩容
 (size >= threshold) && (null != table[bucketIndex])
2、新容量大小：旧容量的2倍
Entry[] newTable = new Entry[2*table.length];
3、遍历老数组，重新计算新的下标，并将数据设置到新数组中
for (Entry<K,V> e : table) {
   while(null != e) {
       Entry<K,V> next = e.next;
       //下标重新计算
       int i = indexFor(e.hash, newCapacity);
       e.next = newTable[i];
       newTable[i] = e;
       // 继续遍历下一个节点
       e = next;
   }
}
4、新数组设置为当前map的对象数组
   table = newTable;
5、阈值重新计算
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

 为什么加载因子是0.75 而不是0.8或1 呢？
 加载因子越大，扩容的几率越小，空间的利用率会非常的高，但index下标冲突概率也就越大，每个下标里对应的链表数据会增多，查询效率会低下成本会增高。
 加载因子越小，index下标冲突概率也就越小，每个下标里的链表数据少，查询效率会提高，但反复扩容会导致扩容成本增大，未利用的空间也很多，空间的利用率不高
 因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷

扩容效果

扩容产生死循环的问题说明

jdk8已解决了该问题

原理分析：当在多线程的情况下，同时对hashMap实现扩容，因为每次数组在扩容的时候，新的数组长度发生了变化，需要重新计算index值；需要将原来的table中的数据移动到新的table中，在hashMap1.7版本598行 e.next=newTable[i]；直接改变了原来的next关系，导致出现脏读的数据。
e.next=newTable[i]； 目的获取当前index在新table中是否存在index冲突问题。
如何解决：同步锁或使用concurrentMap解决。

 
  假设链表数据有：A.next=B
 
  第一次：
  a、next = e.next;
  e = A
  next = B
 
  b、i = indexFor(e.hash, newCapacity);
  假设i=2
 
  c、e.next = newTable[i];
  由于newTable[i]的值为null，也就是A.next = null
 
  d、newTable[i] = e;
  A填充到新table中
 
  第二次：
  a、next = e.next;
  e = B
  next = null
 
  b、i = indexFor(e.hash, newCapacity);
  假设i也为2
 
  c、e.next = newTable[i];
  由于newTable[i]的值为A，此时变为了B.next = A
 
  d、newTable[i] = e;
  B填充到新table中
 
  总结：
  1、扩容后，结构顺序倒了，原有A.next=B变成了B.next=A
  2、如果多线程同时在扩容，由于A和B节点是共用的，会导致遍历了A后获取B时，B.next=A,就会出现了死循环的情况。