上一篇 <<<Jdk1.7HashMap源码分析
下一篇 >>>JDK1.8HashMap源码分析
扩容原理
初始容量默认为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,就会出现了死循环的情况。
相关文章链接：
<<<Java集合类图总览
<<<ArrayList的添加和删除操作实现原理图解
<<<ArrayList的动态扩容、ModCount及fail-fast原理
<<<LinkedList增删改查操作底层实现原理
<<<数组拷贝的几种方式及和链表结构的对比
<<<Jdk1.7HashMap源码分析
<<<JDK1.8HashMap源码分析
<<<ConcurrentHashMap在JDK1.8版本比1.7改进了什么
<<<JDK8的HashMap中红黑树左旋右旋原理图解
<<<基于LinkedHashMap手写LRU淘汰策略
<<<HashSet集合底层实现原理
<<<HashTable底层实现原理及和ConcurrentHashMap区别
<<<java集合常见面试题
