最近对HashMap的扩容问题很感兴趣，看了源码记录一下吧。
相信大家之前在面试的时候一定被问到过，hashmap在使用的过程中遇到过什么异常的情况没有(比如死循环)。那么产生异常情况的原因基本都是多线程同时操作一个HashMap对象导致的是吧，那下面我们就来具体的看一下源码，思考一下多线程到底是怎么使HashMap出现异常情况的。
首先想要说，HashMap在多线程的情况先出现的死循环是在1.7的情况下才会出现的(但是为了安全，如果存在多线程的情况还是建议使用ConcurrentHashMap),在1.8的版本中已经对这部分进行了优化，理论上是不会出现死锁的情况了。下面我们来看看1.7中到底是怎么实现的，才导致出现了死锁的情况。
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}
重点内容是那个transfer方法，作用是将数据从原数组中迁移到新数组中，我们重点关注一下：
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; //循环取出原数组中每一个链表，e本身也是一个链表的节点，同时包含下一个节点的连接,此处e表示第一个节点，next表示链表的下一个节点 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); //计算在新数组中的存储位置 e.next = newTable[i]; //将原数组链表的第一个元素的next指向新数组，若新数组中已经存在元素，则这个元素为第一个元素，next属性为原节点地址 newTable[i] = e; //将新数组的头节点指向e，此时e(原数组中的第一个元素)已经成功的转移到了新数据中 e = next; //继续处理原数组中剩下的节点 } } }
如果上面的transfer方法明白了，那接下来我们说说多线程的情况先是怎么产生的死锁：
比如：
oldArray[ i ] : A->B->null
newArray[ j ] : C->D->->null
那么要将oldArray中的元素移动到 newArray中，按照源码中的逻辑要进行如下的操作：
1.创建节点e指向oldArray[ i ]，也就是指向A
2.e.next指向newArray[ j ]
3.newArray[ j ] 指向e,此时newArray[ j ] 的情况就是：A->C->D->null
4.将e指向B,再次循环上面的操作
最终的结果newArray[ j ] 就是：B->A->C->D->null，原数组中链表的顺序也发生了改变，变成了逆序的。
发生死锁的情况：
线程1执行
Entry<K,V> next = e.next;
此时e指向A,next指向了B
然后被线程2抢占了，接着线程2继续执行扩容的操作，最终newArray[ j ] 就是：B->A->C->D->null
这时线程1回复继续执行
e.next = newTable[i];
这个时候又把A连接到newArray[ j ] 前面，形成了B<->A C->D->null的状况。
接下来再继续执行
newTable[i] = e;
newArray[ j ] 彻底变成B<->A的一个死锁的情况。
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold //容量没有超过最大值，容量变为原来的两倍 } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) //只有一个节点，按照之前的方式转移 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //红黑树 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order //新的优化 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; 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; } } } } } return newTab; }
下面重点内容摘自(清风吹斜阳)：
假如现在容量为初始容量16，再假如5，21，37，53的hash自己（二进制），
所以在oldTab中的存储位置就都是 hash & （16 - 1）【16-1就是二进制1111，就是取最后四位】，
5 ：00000101
21：00010101
37：00100101
53：00110101
四个数与（16-1）相与后都是0101
即原始链为：5--->21--->37--->53---->null
此时进入代码中 do-while 循环，对链表节点进行遍历，判断是留下还是去新的链表：
lo就是扩容后仍然在原地的元素链表
hi就是扩容后下标为 原位置+原数组容量 的元素链表，从而不需要重新计算hash。
因为扩容后计算存储位置就是 hash & （32 - 1）【取后5位】，但是并不需要再计算一次位置，
此处只需要判断左边新增的那一位（右数第5位）是否为1即可判断此节点是留在原地lo还是移动去高位hi：(e.hash & oldCap) == 0 （oldCap是16也就是10000，相与即取新的那一位）
5 ：00000101——————》0留在原地 lo链表
21：00010101——————》1移向高位 hi链表
37：00100101——————》0留在原地 lo链表
53：00110101——————》1移向高位 hi链表
为什么为0就放在原位置，为1就要放到原位置+原数组容量位置呢？
因为上面进行resize的时候，是将数组容量扩大了一倍，原计算位置取模的时候是通过length-1，那么现在与oldCap相与后，如果右边第5位是1，
那就是增加了一个原数组的长度(因为原取模的时候是取4位)，所以如果右边第5位要是1的话，那新的位置就是原位置+原数组容量。
所以在1.8的情况先，resize是不需要对原数组链表中的所有节点都进行再次hash，移动之后的节点也的顺序也不会改变，而且在一定程度上也避免了1.7中死锁的发生。
联系客服
