描述: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。
相关推荐
详细解读了HashMap中链表转红黑树的treefyBin方法,该方法中涉及到的诸如:replacementTreeNode方法、treeify方法、comparableClassFor方法、compareComparables方法、tieBreakOrder方法、balanceInsertion方法、...
详 解 hashmap 1.7 扩 容 机 制 的 数 据 迁 移 以 及 出 现 环 形 列 表 导 致 死 锁 情 况 视 频
这种链表结构使得HashMap容易形成闭合的链路,这就是死循环的根源。 在单线程情况下,只有一个线程对HashMap的数据结构进行操作,是不可能产生闭合的回路的。那就只有在多线程并发的情况下才会出现这种情况。那就是...
工程(VS2013)主要构造了HashMap和list集合,通过查找集合中的元素对两者的效率进行比较
Java基础-模拟HashMap集合(基于数组和链表) 数组和链表.pdf
LRU缓存HashMap+双向链表实现,java版本,导入即用
疫苗:Java HashMap的死循环
jdk1.7 HashMap中的”致命错误”:循环链表 ...多线程同时put时,如果同时调用了resize操作,可能会导致循环链表产生,进而使得后面get的时候,会死循环。下面详细阐述循环链表如何形成的。 resize函数 数组扩容函数,主
Java用数组和链表的方式简单实现HashMap的增删改功能 数组和链表.pdf
HASHMAP基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)下面小编来带大家详细了解下吧
3. 如果数组中的该索引处已经存在键值对,则循环遍历链表,直到找到相同的键值对。 4. 如果找到了相同的键值对,则将新值覆盖旧值,并返回旧值。 5. 如果没有找到相同的键值对,则将键值对添加到链表中。 Hash 码的...
HashMap导致CPU100% 的分析
HashMap是一个散列桶(数组和链表),它存储的内容是键值对(key-value)映射HashMap采用了数组和链表的数据结构,能在查询和修改方便继承了数组的线性查找和链表的寻址修改HashMap是非synchronized,所以HashMap很快...
Java数组+链表简单实现HashMap的put和get 数组和链表.pdf
HashMap之resize()方法源码解读,分两部分概述扩容方法涉及到的处理:创建新数组,将旧数组元素转移到新数组上
java1.7 HashMap用的是数组+链表实现的,同时采用的头插入法,存在死循环的问题 java1.8 HashMap用的是数组+链表+红黑树实现的,采用尾插法实现的,解决了死循环的问题,今天分析的就是1.8 // 初始容量为16 ...
Java集合,HashMap底层实现和原理(1.7数组+链表与1.8+的数组+链表+红黑树) 数组和链表.pdf
如果多个键的哈希码相同,则会形成哈希冲突,此时HashMap会使用链表或红黑树等数据结构来解决冲突。 HashMap与HashTable区别: HashMap和HashTable都基于哈希表实现,但是它们在使用和性能上存在一些差异。具体来说...
HashMap 底层的数据结构主要是:数组 + 链表 + 红黑树。其中当链表的长度大于等于 8 时, 链表会转化成红黑树,当红黑树的大小小于等于 6 时,红黑树会转化成链表 HashMap是数组结构,数组的元素可能是单个 Node,...
版本之更迭: –》JDK 1.7 : Table数组+ Entry链表; –》JDK1.8 : Table数组+ Entry链表/红黑树;(为什么要使用红黑树?) 一问HashMap的实现原理 你看过HashMap源码吗,知道底层的原理吗 为什么使用数组+链表 用...