`
zl378837964
  • 浏览: 189357 次
  • 性别: Icon_minigender_2
  • 来自: 北京
社区版块
存档分类
最新评论

HashMap之链表导致死循环

阅读更多



描述:HashMap采用拉链法(数组链表)解决Hash冲突,因为是链表结构,那么就很容易形成闭合的链路。

在单线程情况下,只有一个线程对HashMap的数据结构进行操作,是不可能产生闭合的回路的。
那就只有在多线程并发的情况下才会出现这种情况,那就是在put操作的时候,如果size > nitialCapacity*loadFactor,那么这时候HashMap就会进行rehash操作,随之HashMap的结构就会发生翻天覆地的变化。很有可能就是在两个线程在这个时候同时触发了rehash操作,产生了闭合的回路。

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//存在key,则替换掉旧的value
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//table[i]为空,这时直接生成一个新的entry放在table[i]上
addEntry(hash, key, value, i);
return null;
}


void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}


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];
//将旧的Entry数组的数据转移到新的Entry数组上
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}


void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
/*
* 在转换的过程中,HashMap相当于是把原来链表上元素的的顺序颠倒了。
* 比如说 原来某一个Entry[i]上链表的顺序是e1->e2->null,那么经过操作之后
* 就变成了e2->e1->null
*/
for (int j = 0; j  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);
}
}
}

那么回路究竟是如何产生的呢,问题就出在next=e.next这个地方,在多线程并发的环境下,为了便于分析,我们假设就两个线程P1,P2。src[i]的链表顺序是e1->e2->null。我们分别线程P1,P2的执行情况。
首先,P1,和P2进入到了for循环中,这时候在线程p1和p2中,局部变量分别如下:
|----| e | next|
| p1| e1 | e2 |
| p2| e1 | e2 |
此时两个Entry的顺序是依然是最开始的状态e1->e2->null, 但是此时p1可能某些原因线程暂停了,p2则继续执行,并执行完了do while循环。这时候Entry的顺序就变成了e2->e1->null。在等到P2执行完之后,可能p1才继续执行,这时候在P1线程中局部变量e的值为e1,next的值为e2(注意此时两个元素在内存中的顺序变成了e2->e1->null),下面P1线程进入了do while循环。这时候P1线程在新的Entry数组中找到e1的位置,
e.next = newTable[i];
newTable[i] = e;
下面会把next赋值给e,这时候e的值成为了e2,继续下一次循环,这时候
|----| e | next|
| p1| e2 | e1 |
e2->next=e1,这个是线程P2的"功劳"。程序执行完这次循环之后,e=e1,继续第三次循环,这时候根据算法,就会进行e1->next=e2。
这样在线程P1中执行了 e1->next=e2,在线程P2中执行了 e2->next=e1,这样就形成了一个环。在get操作的时候,next值永远不为null,造成了死循环。
在高并发情况下,不建议使用HashMap,建议采用ConcurrentHashMap。

 

分享到:
评论

相关推荐

    疫苗:Java HashMap的死循环

    然而,在多线程环境中使用HashMap可能会导致死循环的问题。下面我们来分析HashMap的死循环原因。 首先,HashMap的数据结构是一个数组加链表的结构。每个数组元素是一个链表的头结点,每个链表节点包含了key-value对...

    jdk1.7 HashMap中的致命错误:循环链表

    然而,在JDK1.7版本中,HashMap存在一个严重的问题,即“循环链表”(Looping List),这可能导致在多线程环境下性能急剧下降,甚至引发死循环。本文将深入探讨这个问题及其解决方案。 首先,我们来看看JDK1.7 ...

    深入了解JAVA HASHMAP的死循环

    然而,由于HashMap不是线程安全的,因此在多线程环境下直接使用可能会引发一系列问题,其中之一就是所谓的"死循环"。本文将深入探讨这一主题。 首先,死循环问题通常发生在并发环境中,当多个线程同时修改HashMap时...

    马士兵老师HashMap学习笔记

    然而,由于HashMap是非线程安全的,如果多个线程同时put可能导致死循环的问题。这是因为当两个线程同时put并产生哈希冲突时,它们可能会在链表中形成环形结构,导致迭代器遍历时无法正常结束。 为了解决这个问题,...

    关于如何解决HashMap线程安全问题的介绍

    在多线程环境下,两个线程同时触发扩容可能导致循环链表的形成,从而引发死循环,这是一种严重的性能问题。 为了解决HashMap的线程不安全问题,我们可以采取以下几种策略: 1. 使用Collections.synchronizedMap()...

    面试题之详解HashMap

    2. HashMap多线程操作导致死循环问题 在并发环境下,多个线程同时对HashMap进行put和resize操作可能导致元素形成循环链表。在JDK 1.7中,resize过程中使用了头插法,这在并发时可能使链表反转,导致get操作陷入死...

    Hashmap实现了Map接口的底层实现.docx

    HashMap在多线程环境中并不安全,因为其非线程安全的设计可能导致死循环。例如,在并发扩容时,可能产生环形链表。在这种情况下,尝试获取不存在的键时,可能会导致无限循环。因此,多线程场景推荐使用...

    HashMap资料.zip

    线程安全问题可能导致数据不一致或者死循环等问题。 5. **null键和值**:HashMap允许键和值为null,但只能有一个键为null,因为所有null键的哈希值都为0,所有值为null的键都会被存放在数组的第0个槽位。 6. **...

    第9讲 对比Hashtable、HashMap、TreeMap有什么不同?1

    在并发环境下,HashMap的非线程安全可能导致死循环(例如,多个线程同时进行扩容操作)和其他并发问题。 了解Map的整体结构也很重要,HashMap和其他Map实现如LinkedHashMap(保持插入顺序或访问顺序的HashMap)都是...

    java7-8中的 HashMap和ConcurrentHashMap全解析

    `HashMap`是非线程安全的,意味着在多线程环境下,多个线程同时操作`HashMap`可能会导致数据不一致或者死循环。因此,如果需要在并发环境中使用,必须使用同步机制,如`synchronized`关键字或`Collections....

    hashmap-thread-test:测试 Java HashMap 是否是线程安全的

    - **死循环**:在扩容过程中,如果多个线程同时参与,可能导致链表形成循环,从而引发死循环。 - **并发修改异常**:使用`ConcurrentModificationException`,Java会尝试阻止这种情况发生,但并不总是有效。 ### ...

    求职宝典-Java 基础面试题

    在多线程环境下,HashMap的并发操作可能导致死循环问题。在JDK1.7中,rehash过程中的并发修改可能导致链表循环,而在JDK1.8中,虽然采用了红黑树,但仍然存在类似问题。为了解决这个问题,应使用ConcurrentHashMap,...

    大厂真题之蚂蚁金服-Java高级.zip

    但是 hashmap1.7 跟 1.8 中都没有任何同步操作,容易出现并发问题,甚至出现死循环 导致系统不可用。解决方案是 jdk 的 ConcurrentHashMap,位于 java.util.concurrent 下,专门 解决并发问题。

    通过面试题带你了解java的Map

    - 当lastRun节点位于全0或全1的链表上,可能导致在扩容时形成死循环,但Java 8的尾插法解决了这个问题。 6. **红黑树的引入**: - 当链表长度达到8时,HashMap会将链表转换为红黑树,以保持O(logN)的查找效率,而...

    ConcurrentHashMap的实现原理(JDK1.7和JDK1.8).pdf

    在多线程环境中,如果多个线程同时修改HashMap,可能会引发死循环,导致CPU利用率极高。 - `HashTable`是线程安全的,但其线程安全的实现方式过于简单,所有操作都使用`synchronized`关键字,这使得在高并发环境下...

    java后端面试题答案.pdf

    在JDK 1.7版本中,如果扩容操作开始后一个新元素插入到正在扩容的HashMap中,可能会出现链表循环引用的问题,从而导致死循环。 为了优化这一问题,JDK 1.8在实现上做了一些改动。在JDK 1.8中,当链表长度超过8时,...

    常见的面试点1

    5. 并发问题:HashMap在并发环境下可能导致死循环,因为1.7版本使用尾插法。1.8版本虽然使用头插法,但在并发情况下仍然不安全。面试中,你可能会被问到如何在并发环境中安全地使用HashMap,这时可以提到`HashTable`...

    JAVA+面试题+常用的比较齐全

    10. HashMap发生哈希冲突时,JDK1.7以前采用头部插入,可能导致死循环,而JDK1.8改为尾部插入以避免这个问题。 11. Hashtable不允许key或value为null,否则会抛出NullPointerException。它直接取对象的hashCode,而...

    BAT互联网Java面试题汇总.pdf

    - 如果多个线程同时进行扩容,就有可能导致循环链表的形成,这会导致后续的读取操作陷入死循环。 #### 六、线程安全的Map实现类 - **线程安全的Map实现类**包括`Hashtable`和`ConcurrentHashMap`。其中,`...

Global site tag (gtag.js) - Google Analytics