最近对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中死锁的发生。
联系客服