3月19日晚上参加了京东base成都的研发工程师电话面试，其中对面试官提出的一个问题印象比较深，特别记录一下；
Q1： 你能聊聊hashMap扩容机制嘛？
A1：是这样的，在JDK1.7及以前，hashmap在判断是否需要扩容前，需要满足两个条件
①会先去比较当前的enrty数量是否达到阈值(初始长度*负载因子)，如果达到了则进入②
②再去判断当前的key所计算出来的hash值是否会产生hash冲突？如果会 则进行扩容，扩容为原来的两倍 然后在把原来的enrty节点放到新的map中，在此之前需要rehash
Q2： 那么在扩容的时候会出现什么问题呢？
A2：可能会造成链表循环把........
Q3：那你能聊聊为什么会造成链表循环呢？ 是如何解决的呢？
A3：.........10:40:51
面试完后马上看了源码，然后进行了分析如下：
jdk 1.7 hashmap
1.7中是数据是先扩容后插入
链表循环问题发生在链表转移的方法中
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; 12 e = next; 13 } 14 } 15 }
如果元素个数已经达到数组阈值，则扩容，并把原来的元素移动过去。
假设HashMap初始化大小为4，插入个3节点，不巧的是，这3个节点都hash到同一个位置，如果按照默认的负载因子的话，插入第3个节点就会扩容，为了验证效果，假设负载因子是1
插入第4个节点时，发生rehash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组。
假设 线程2 在执行到Entry<K,V> next = e.next;之后，cpu时间片用完了，这时变量e指向节点a，变量next指向节点b。
线程1继续执行，很不巧，a、b、c节点rehash之后在同一个位置7，开始移动节点
第一步，移动节点a
第二步，移动节点b
注意，这里的顺序是反过来的，继续移动节点c
这个时候 线程1 的时间片用完，内部的table还没有设置成新的newTable， 线程2 开始执行，这时内部的引用关系如下：
这时，在 线程2 中，变量e指向节点a，变量next指向节点b，开始执行循环体的剩余逻辑
1 Entry<K,V> next = e.next; 2 int i = indexFor(e.hash, newCapacity); 3 e.next = newTable[i]; 4 newTable[i] = e; 5 e = next;
执行之后的引用关系如下图
执行后，变量e指向节点b，因为e不是null，则继续执行循环体，执行后的引用关系
变量e又重新指回节点a，只能继续执行循环体，这里仔细分析下：
1、执行完Entry<K,V> next = e.next;，目前节点a没有next，所以变量next指向null；
2、e.next = newTable[i]; 其中 newTable[i] 指向节点b，那就是把a的next指向了节点b，这样a和b就相互引用了，形成了一个环；
3、newTable[i] = e 把节点a放到了数组i位置；
4、e = next; 把变量e赋值为null，因为第一步中变量next就是指向null；
所以最终的引用关系是这样的：
jdk 1.8 hashmap
1.8中数据是先插入再扩容
1 //规避了8版本以下的成环问题 2 else { // preserve order 3 // loHead 表示老值,老值的意思是扩容后，该链表中计算出索引位置不变的元素 4 // hiHead 表示新值，新值的意思是扩容后，计算出索引位置发生变化的元素 5 // 举个例子，数组大小是 8 ，在数组索引位置是 1 的地方挂着一个链表，链表有两个值，两个值的 hashcode 分别是是9和33。 6 // 当数组发生扩容时，新数组的大小是 16，此时 hashcode 是 33 的值计算出来的数组索引位置仍然是 1，我们称为老值 7 // hashcode 是 9 的值计算出来的数组索引位置是 9，就发生了变化，我们称为新值。 8 Node<K,V> loHead = null, loTail = null; 9 Node<K,V> hiHead = null, hiTail = null; 10 Node<K,V> next; 11 // java 7 是在 while 循环里面，单个计算好数组索引位置后，单个的插入数组中，在多线程情况下，会有成环问题 12 // java 8 是等链表整个 while 循环结束后，才给数组赋值，所以多线程情况下，也不会成环,也就是找到链表最后一个值之后才赋值，尾插法 13 do { 14 next = e.next; 15 // (e.hash & oldCap) == 0 表示老值链表 16 if ((e.hash & oldCap) == 0) { 17 if (loTail == null) 18 loHead = e; 19 else 20 loTail.next = e; 21 loTail = e; 22 } 23 // (e.hash & oldCap) == 0 表示新值链表 24 else { 25 if (hiTail == null) 26 hiHead = e; 27 else 28 hiTail.next = e; 29 hiTail = e; 30 } 31 } while ((e = next) != null); 32 // 老值链表赋值给原来的数组索引位置 33 if (loTail != null) { 34 loTail.next = null; 35 newTab[j] = loHead; 36 } 37 // 新值链表赋值到新的数组索引位置 38 if (hiTail != null) { 39 hiTail.next = null; 40 newTab[j + oldCap] = hiHead; 41 } 42 }