江苏龙网

  1. 首页 > 人文 > >

精英联盟总队|面试官：说一下HashMap原理，为什么会产生死循环( 三 )

transfer函数
transfer逻辑其实也简单 ， 遍历旧数组 ， 将旧数组元素通过头插法的方式 ， 迁移到新数组的对应位置问题出就出在头插法 。
void transfer(Entry[] newTable) {//src旧数组Entry[] src = http://kandian.youth.cn/index/table;int newCapacity = newTable.length;for (int j = 0; j < src.length; j++) {Entry e = src[j];if (e != null) {src[j] = null;do {Entry next = e.next;int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;} while (e != null);//由于是链表 ， 所以是个循环过程}}}static int indexFor(int h, int length) {return h }下面举个实际例子：
① 我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度） 。
② 最上面的是old hash 表 ， 其中的Hash表的size=2, 加载阈值为2?0.75=1 ， 所以key = 3, 7, 5 ， 在mod 2以后都冲突在table[1]这里了 。
③ 接下来的三个步骤是Hash表 resize成4 ， 然后所有的 重新rehash的过程
正常的Rehash的过程：
精英联盟总队|面试官：说一下HashMap原理，为什么会产生死循环并发下的Rehash过程：
1）假设我们有两个线程 ， 用红色和浅蓝色标注了一下 。
我们再回头看一下transfer代码中的这个细节：
do {Entry next = e.next; //假设线程一执行到这里就被调度挂起了int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;} while (e != null);而我们的线程二执行完成了 。 于是我们有下面的这个样子 。
精英联盟总队|面试官：说一下HashMap原理，为什么会产生死循环注意 ， 因为Thread1的 e 指向了key(3) ， 而next指向了key(7) ， 其在线程二rehash后 ， 指向了线程二重组后的链表 。 我们可以看到链表的顺序被反转了 。
2）线程一被调度回来执行
先是执行 newTalbe[i] = e；然后是e = next ， 导致了e指向了key(7) ， 而下一次循环的next = e.next导致了next指向了key(3)
精英联盟总队|面试官：说一下HashMap原理，为什么会产生死循环3）一切安好
线程一接着工作 。 把key(7)摘下来 ， 放到newTable[i]的第一个 ， 然后把e和next往下移 。
精英联盟总队|面试官：说一下HashMap原理，为什么会产生死循环4）环形链表出现
e.next = newTable[i] 导致 key(3).next 指向了 key(7)
注意：此时的key(7).next 已经指向了key(3) ，环形链表就这样出现了 。
精英联盟总队|面试官：说一下HashMap原理，为什么会产生死循环于是 ， 当我们的线程一调用到 ， HashTable.get(11)时 ， 悲剧就出现了Infinite Loop 。
有人把这个问题报给了Sun ， 不过Sun不认为这是一个问题 。 因为HashMap本来就不支持并发 ， 要并发就用ConcurrentHashmap 。
这个循环链表问题只存在于JDK1.7中 ， 在JDK1.8中使用了不同的扩容实现方式 ， 所以不会出现这种情况 。 JDK1.8中HashMap是如何实现的我们后续讲解 。
【精英联盟总队|面试官：说一下HashMap原理，为什么会产生死循环】


推荐阅读


上一篇：丈农尺|“驴皮冻”和“燕口水”之争，谁会赢？，又一滋补品爆火

下一篇：光明网社会|但投入结构仍有不足，我国科技经费投入规模稳步增加