从面试角度聊聊ConcurrentHashMap的理解

文章目录
前言相关数据结构对比ConcurrentHashMap原理总结

前言

面试中常常问到Hashmap原理,这属于第一阶段的过招,之后面试官可能会顺势问一下,Hashmap是否是线程安全的。连环问于是开始了,如果你回答不是,那么紧接着面试官会问有没有什么数据结构可以保证线程安全。有一定研究的你可以会马上联想到有,比如ConcurrentHashMap。好戏开始上演……

请先看下面代码:

public class Test {
private ConcurrentHashMap mMap = new ConcurrentHashMap();
// map中不存在才加入,否则不加入
public void addIfNotExists(String key, String value) {
if (!mMap.containsKey(key)) {
mMap.put(key, value);
}
}
}

请问:是否是线程安全?

可能你会条件反射的回答,是线程安全的。因为之前的回答已经做了一定的铺垫。那么到底是不是线程安全的呢?

问题的背后,往往是深层次的原理考察。于是,我开始了相关知识模块V1.0的构建。

第一步,了解HashMap原理和特点,并同时对比联想相邻的知识点,在查阅大量资料后,下面直接说结论,不再此一一展开。

相关数据结构对比

HashMap

读取快,插入慢,线程不安全

底层是数组+链表 结构,当两个线程同时插入需要扩容的时候,获得改map的size()大小不一样,则会报错。当有两个线程在读,第三个线程正好在对map扩容时,这两个线程就会进入死循环,cup占用率就会高。

在多线程,使用HaspMap就行put操作会引起死循环,导致cpu100%。所在在并发情况不能使用HashMap。

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

LinkedHashMap

​ 读取快,插入慢

treeMap

可以实现元素的自动排序

HashTable

线程安全。

HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下,因为在一个线程访问HashTable的同步方法,其它线程也访问HashTable的同步方法是,会进入阻塞或轮询状态

concurrentHashMap

线程安全,支持高并发的操作,特点:效率比Hashtable高,并发性比hashmap好。结合了两者的特点。(本文介绍的主角)

HashTable容器在竞争激烈的并发下表现出的效率低下的原因是所有访问HashTable的线程都必须竞争同一把锁,加入容器里有多把锁,每一把锁用于容器其中一部分数据,那么当多线程访问容器里不同的数据段是,线程间就不会出现锁竞争,从而可以有效的提高并发效率。将数据分成一段一段的存储,然后给每一段分配一把锁,当前程占用锁访问其中的一个段的数据的时候,其它的数据也能被其它的线程访问

ConcurrentHashMap原理

ConcurrentHashMap 采用了分段锁技术,其中 Segment 继承于 ReentrantLock。

不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理,理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。

每当一个线程占用锁访问一个 Segment 时,不会影响到其他的 Segment。

ConcurrentHashMap和Hashtable主要区别就是围绕着锁的粒度以及如何锁,可以简单理解成把一个大的HashTable分解成多个,形成了锁分离。

而Hashtable的实现方式是—锁整个hash表。
从面试角度聊聊ConcurrentHashMap的理解
(图片来源于网络)

走进源码:

public V put(K key, V value) {
return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
//不允许 key或value为null
if (key == null || value == null) throw new NullPointerException();
//计算hash值
int hash = spread(key.hashCode());
int binCount = 0;
//死循环 何时插入成功 何时跳出
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//如果table为空的话,初始化table
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//根据hash值计算出在table里面的位置
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果这个位置没有值 ,直接放进去,不需要加锁
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//当遇到表连接点时,需要进行整合表的操作
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//结点上锁 这里的结点可以理解为hash值相同组成的链表的头结点
synchronized (f) {
if (tabAt(tab, i) == f) {
//fh〉0 说明这个节点是一个链表的节点 不是树的节点
if (fh >= 0) {
binCount = 1;
//在这里遍历链表所有的结点
for (Node<K,V> e = f;; ++binCount) {
K ek;
//如果hash值和key值相同 则修改对应结点的value值
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
//如果遍历到了最后一个结点,那么就证明新的节点需要插入 就把它插入在链表尾部
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//如果这个节点是树节点,就按照树的方式插入值
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//如果链表长度已经达到临界值8 就需要把链表转换为树结构
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//将当前ConcurrentHashMap的元素数量+1
addCount(1L, binCount);
return null;
}

ConcurrentHashMap的put方法和HashMap的逻辑差不多,主要是新增了线程安全部分,在添加元素时候,采用synchronized来保证线程安全,然后计算size的时候采用CAS操作进行计算。put流程小结:

1.判断key和vaule是否为空,如果为空,直接抛出异常。

2.判断table数组是否已经初始化完毕,如果没有初始化,进行初始化。

3.计算key的hash值,如果该位置为空,直接构造节点放入。

4.如果table正在扩容,进入帮助扩容方法。

5.最后开启同步锁,进行插入操作,如果开启了覆盖选项,直接覆盖,否则,构造节点添加到尾部,如果节点数超过红黑树阈值,进行红黑树转换。如果当前节点是树节点,进行树插入操作。

6.最后统计size大小,并计算是否需要扩容。

总结

JDK6,7中的ConcurrentHashmap主要使用Segment来实现减小锁粒度,把HashMap分割成若干个Segment,在put的时候需要锁住Segment,get时候不加锁,使用volatile来保证可见性,当要统计全局时(比如size),首先会尝试多次计算modcount来确定,这几次尝试中,是否有其他线程进行了修改操作,如果没有,则直接返回size。如果有,则需要依次锁住所有的Segment来计算。

最后,回答开头的问题。

我的研究结果是:线程安全,因为通过put源码分析,在插入数据时用了同步锁synchronized

对于赶时间的面试官来说,是还是不是,就够了,至于为什么,想扩展什么的根据情况再说,但是我们自己得知道问题的背后以及是否触及到你的知识的盲区,这也是本文总结的动机由来。

如有不足之处,欢迎PK。毕竟,知识无边界,我们需要多个角度看世界。

参考资料:

1.多线程为什么要用ConcurrentHashMap

2.ConcurrentHashMap总结

3.ConcurrentHashMap的实现 get put remove 详解

关注博主即可阅读全文
从面试角度聊聊ConcurrentHashMap的理解

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

从面试角度聊聊ConcurrentHashMap的理解

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 从面试角度聊聊ConcurrentHashMap的理解
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏