当HashMap有数据插入时,都会检查容量有没有超过设定的thredhold,如果超过就要做rehash操作。代码如下:
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
);
}
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;
if
(rehash) {
e.hash =
null
== e.key ?
0
: hash(e.key);
}
int
i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
大概看下transfer的步骤:
- 1.对索引数组中的元素遍历
- 2.对链表上的每一个节点遍历:用 next 取得要转移那个元素的下一个,将 e 转移到新 Hash 表的头部,使用头插法插入节点。
- 3.循环2,直到链表节点全部转移
- 4.循环1,直到所有索引数组全部转移
经过这几步,我们会发现转移的时候是逆序的。假如转移前链表顺序是1->2->3,那么转移后就会变成3->2->1。这时候在多线程场景下,就会产生死锁问题了,因为可能会造成1->2的同时2->1。
关键代码分析:
while
(
null
!= e) {
Entry<K,V> next = e.next;
e.next = newTable[i];
newTable[i] = e;
e = next;
}
1. Entry<K,V> next = e.next;——因为是单链表,如果要转移头指针,一定要保存下一个结点,不然转移后链表就丢了
2. e.next = newTable[i];——e 要插入到链表的头部,所以要先用 e.next 指向新的 Hash 表第一个元素(为什么不加到新链表最后?因为复杂度是 O(N))
3. newTable[i] = e;——现在新 Hash 表的头指针仍然指向 e 没转移前的第一个元素,所以需要将新 Hash 表的头指针指向 e
4. e = next——转移 e 的下一个结点
假设HashMap某位的链表有两个对象,且有两个线程同时执行了put()
操作,并进入了transfer()
环节。 线程1在执行到第1步时挂起了,然后线程2先执行完毕。线程1继续执行。执行到转移到链表中第二个对象时,由于线程2已执行完,把对象2本应是null的next变成了对象1,于是transfer又继续执行转移对象1,于是对象1的next指向对象2,环形链表出现了。
详见http://www.importnew.com/22011.html
相关推荐
HashMap之resize()方法源码解读,分两部分概述扩容方法涉及到的处理:创建新数组,将旧数组元素转移到新数组上
HashMap死循环原因分析.docx
疫苗:Java HashMap的死循环
详 解 hashmap 1.7 扩 容 机 制 的 数 据 迁 移 以 及 出 现 环 形 列 表 导 致 死 锁 情 况 视 频
HASHMAP基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)下面小编来带大家详细了解下吧
本篇文章是对Java HashMap的死循环进行了详细的分析介绍,需要的朋友参考下
java1.7 HashMap用的是数组+链表实现的,同时采用的头插入法,存在死循环的问题 java1.8 HashMap用的是数组+链表+红黑树实现的,采用尾插法实现的,解决了死循环的问题,今天分析的就是1.8 // 初始容量为16 ...
主要介绍了Java HashMap三种循环遍历方式及其性能对比,结合具体实例形式分析了Java HashMap三种循环遍历方式的实现方法、运行效率及性能优劣,需要的朋友可以参考下
今天小编就为大家分享一篇关于Java源码解析HashMap的resize函数,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
hashmap实例 hashmap实例hashmap实例hashmap实例
hashmap相关的面试题
HashMap介绍和使用
HashMap数据结构,HashMap的构造方法,HashMap的put,HashMap的get
java7 hashmap源码 随着Java学习的不断深入,发现...多线程下,hashmap的resize()方法为什么容易出现死循环? 答: 其他面试题? 答: 并发 概述 :star::star: :star::star: 线程池 :star: AQS :star: 锁 ListenalbeFut
jdk1.7 HashMap中的”致命错误”:循环链表 ...多线程同时put时,如果同时调用了resize操作,可能会导致循环链表产生,进而使得后面get的时候,会死循环。下面详细阐述循环链表如何形成的。 resize函数 数组扩容函数,主
HashMap存放.doc
HashMap是一个散列桶(数组和链表),它存储的内容是键值对(key-value)映射HashMap采用了数组和链表的数据结构,能在查询和修改方便继承了数组的线性查找和链表的寻址修改HashMap是非synchronized,所以HashMap很快...
hashmap的底层及源码解析,很适合大家的学习,不要积分。
hashMap排序,hashmap使用还是比较频繁。这时自己写的一个实现hashmap排序的例子