jdk1.7中的HashMap
扩容部分源码
扩容分为两步
1.创建一个数组容量为原来2倍的HashMap
2.遍历旧的Entry数组，把所有的Entry重新Hash到新数组
在开始之前我们先看一下扩容部分的源码
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历旧数组中的每个桶
for (Entry<K,V> e : table) {
// 遍历桶中的元素Entry(是一个链表)
while(null != e) {
Entry<K,V> next = e.next;
//如果是重新Hash，则需要重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//计算该Entry在新table数组中对应桶的下标Index
/*
* indexFor中的代码是return h & (length-1);
*可见hash对应的数组下标index是与hashmap的大小有关的，所以扩容不能直接把旧数据复制过来，需要遍历重新计算下标index的值
*/
int i = indexFor(e.hash, newCapacity);
//头插法
e.next = newTable[i];
newTable[i] = e;
//继续下一个元素(next是再上面就存下来了的，是原来链表的下一个元素)
e = next;
}
}
}
扩容导致死循环
假设的前提条件：
- index求解为简单的用key mod 数组的长度
- 最开始size=2 , key=3,7,5,则由假设1可知3 7 5 都在table[1]中
- 然后进行resize，使size变为4
未resize前的数据结构：
单线程
如果在单线程下根据上方transfer的源码理解（遍历+头插法），最后扩容结果如下：
多线程
假设有两个线程A,B都在进行扩容操作，但是线程A遍历的时候在*处被暂时挂起了
1 void transfer(Entry[] newTable, boolean rehash) {
2 int newCapacity = newTable.length;
3 for (Entry<K,V> e : table) {
4 while(null != e) {
5 Entry<K,V> next = e.next;
6 if (rehash) {
7 e.hash = null == e.key ? 0 : hash(e.key);
8 }
9 int i = indexFor(e.hash, newCapacity);
10 e.next = newTable[i];
11 newTable[i] = e;--------* A被挂起
12 e = next;
13 }
14 }
15 }
①此时A线程e=3 | next=7（上方代码第5行得）| i=3 (由假设1可知3%4=3) | e.next=null（10行代码 3.next=null）| 在执行第11行的时候被线程挂起
此时A线程的结果
A线程被挂起，B线程正常执行，完全执行完resize扩容操作后，结果如下:
★由于B执行完了，所以现在java内存中newtable和table中的Entry都是B线程执行完的最新值★
★即： newTable[1]=5 | 5.next=null | newTable[3]=7 | 7.next=3 | 3.next=null★
此时再切换回A线程，A线程重新继续执行11行的代码，①已经求得的临时变量的值是没变的。
上面①中的临时变量继续使用
11 newTable[i] = e; -----(i=3,e=3带入得newTable[3]=3)
12 e = next; -----(next=7，带入得e=7)
执行结果如下:
继续循环（此时e=7 由上次循环的代码可知）：
5 next = e.next; -----(由上图可知7.next=3故得next=3)
9 i = indexFor(e.hash,newCapacity); -----(由假设1可知index=7%4=3)
10 e.next = newTable[i]; -----(由上图可知newTable[3]=3故得e.next=3)
11 newTable[i] = e; -----(newTable[3]=7)
12 e = next -----(e=3)
结果如下：
继续循环（此时e=3 由上次循环的代码可知）：
5 next = e.next; -----(由上图可知3.next=null故得next=null)
9 i = indexFor(e.hash,newCapacity); -----(由假设1可知index=3%4=3)
10 e.next = newTable[i]; -----(由上图可知newTable[3]=7故得e.next=7)
11 newTable[i] = e; -----(newTable[3]=3)
12 e = next -----(e=null)
至此e=null，循环结束
结果如下：
可见这出现了一个循环链表，在之后只要涉及轮询hashmap数据结构，就会在这里发生死循环。
扩容导致数据丢失
假设前提条件
- index求解为简单的用key mod 数组的长度
- 最开始size=2 , key=7,5,3,则由假设1可知7 5 3 都在table[1]中
- 然后进行resize，使size变为4
同样两个线程A,B都在进行扩容，A在*处被挂起
1 void transfer(Entry[] newTable, boolean rehash) {
2 int newCapacity = newTable.length;
3 for (Entry<K,V> e : table) {
4 while(null != e) {
5 Entry<K,V> next = e.next;
6 if (rehash) {
7 e.hash = null == e.key ? 0 : hash(e.key);
8 }
9 int i = indexFor(e.hash, newCapacity);
10 e.next = newTable[i];
11 newTable[i] = e;--------* A被挂起
12 e = next;
13 }
14 }
15 }
①此时A线程e=7 | next=5（上方代码第5行得）| i=3 (由假设1可知7%4=3) | e.next=null（10行代码 3.next=null）| 在执行第11行的时候被线程挂起
执行结果如下：
A线程被挂起，B线程正常执行，完全执行完resize扩容操作后，结果如下:
★由于B执行完了，所以现在java内存中newtable和table中的Entry都是B线程执行完的最新值★
★即： newTable[1]=5 | 5.next=null | newTable[3]=3 | 3.next=7 | 7.next=null★
此时再切换回A线程，A线程重新继续执行11行的代码，①已经求得的临时变量的值是没变的。
上面①中的临时变量继续使用:①此时A线程e=7 | next=5（上方代码第5行得）| i=3 (由假设1可知3%4=3) | e.next=null（10行代码 7.next=null）| 在执行第11行的时候被线程挂起
11 newTable[i] = e; -----(i=3,e=7带入得newTable[3]=7)
12 e = next; -----(next=5，带入得e=5)
执行结果如下：
继续循环（此时e=5 由上次循环的代码可知）：
5 next = e.next; -----(由上图可知5.next=null故得next=null)
9 i = indexFor(e.hash,newCapacity); -----(由假设1可知index=5%4=1)
10 e.next = newTable[i]; -----(由上图可知newTable[1]=5故得e.next=5)
11 newTable[i] = e; -----(newTable[1]=5)
12 e = next -----(e=null)
至此e=null，循环结束
结果如下：
3元素丢失，并形成环形链表。并在后续操作hashmap时造成死循环。
jdk1.8中的HashMap
jdk1.8中对HashMap进行了优化，如果发生hash碰撞，不采用头插法，改成了尾插法，因此不会出现循环链表的情况。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果插入的位置为null，没有hash碰撞，则直接插入元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
.........
但是在多线程的环境下仍然不安全，当两个线程A,B同时进行Put的操作的时候，都判断当前没有hash碰撞，然后同时进行直接插入，那么后面哪个线程的值Entry会把前一个线程插入的Entry给**覆盖**掉，发生线程不安全