Java程序员必知,执行以下代码会引起死循环

日期:2020-07-05 17:39:04 来源:互联网 编辑:小优 阅读人数:792

HashMap进行put操作会引起死循环?

最近在磕《java并发编程艺术》在看到第六章的时候出现了下面这段我不是很理解的东西,如下

java并发编程艺术截取

为什么要使用ConcurrentHashMap

在并发编程中使用HashMap可能导致程序死循环。而使用线程安全的HashTable效率又非常低下,基于以上两个原因,便有了ConcurrentHashMap的登场机会。

1. 线程不安全的HashMap

在多线程环境下,使用HashMap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。例如,执行以下代码会引起死循环。

Java程序员必知,执行以下代码会引起死循环(图1)

HashMap在并发执行put操作时会引起死循环,是因为多线程会导致HashMap的Entry链表形成环形数据结构,一旦形成环形数据结构,Entry的next节点永远不为空,就会产生死循环获取Entry。

结论

1. JDK1.8之前,为了提高rehash的速度,冲突链表是使用头插法,因为头插法是操作速度最快的,找到数组位置就直接找到插入位置了,头插法在多线程下回引起死循环

2.JDK1.8之后开始加入红黑树,当链表长度大于8时链表就会转换成红黑树,这样就大大提高了在冲突链表查找的速度,同时因为链表的长度不可能大于8,链表在rehash的消耗就小很多,所以JDK1.8使用尾插法也避免了死循环问题

本文相关词条概念解析:

链表

链表(Linkedlist)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

网友评论
相关文章
Visual,Studio,VS,C,——简单应用程序

Visual,Studio,VS,C,——简单应用程序

Visual,Studio,VS,C,——简单应用程序[详情]

提起程序员,给公司其他人讲代码,老板居然叫他回去

提起程序员,给公司其他人讲代码,老板居然叫他回去

提起程序员,给公司其他人讲代码,老板居然叫他回去[详情]

唏嘘啊,他都是典型的万金油球员,才2年时间,却在走下坡路了

唏嘘啊,他都是典型的万金油球员,才2年时间,却在走下坡路了

唏嘘啊,他都是典型的万金油球员,才2年时间,却在走下坡路了[详情]

网站地图    Copyright     2016-2018  资讯网   All rights reserved.