专栏首页Hello知识库-JAVA基础3秒搞定ConcurrentHashMap
原创

3秒搞定ConcurrentHashMap

Jdk8

总结

1、ConcurrentHashMap,是Java并发包中自JDK1.5后提供的一个线程安全且高效的HashMap实现,可以用来替代HashTable。直接实现了ConcurrentMap接口,同时继承了AbstractMap抽象类。

2、JDK1.8后,ConcurrentHashMap使用CAS算法结合synchronized同步锁的方式保证线程安全。

3、ConcurrentHashMap的存储结构与HashMap基本一致,使用内部子类Node作为基本单元,存储链表节点数据,使用内部子类TreeNode存储树节点数据。同时增加了几个子类节点对象:ForwardingNode(转发节点)、TreeBin(红黑树根节点)、ReservationNode(保留节点)

UML

功能介绍

基本信息

包路径:java.util.concurrent

说明:ConcurrentHashMap,是Java并发包中自JDK1.5后提供的一个线程安全且高效的HashMap实现,可以用来替代HashTable。直接实现了ConcurrentMap接口,同时继承了AbstractMap抽象类。

它沿用了与它同时期的HashMap版本的思想,(jdk1.8)底层依然由“数组”+链表+红黑树的方式。但是为了做到并发,又增加了很多辅助的类,例如TreeBin,Traverser等对象内部类。

特点:1、线程安全【JDK1.7之前使用分段锁实现,JDK1.8开始使用CAS算法实现】

2、不支持null的key和value

ConcurrentMap是如何保证线程安全的?

我们知道,HashTable通过synchronized同步锁保证线程安全,同一时间只要有一个线程操作某个数据,就会锁定整个哈希表,其他线程就无法对HashTable进行任何操作,只能等待该线程执行完毕或释放锁,那这种方式其实是很不友好且效率很低的。

分段锁

于是ConcurrentHashMap在JDK1.7使用了“分段锁”这种机制,线程访问数据时锁定一段范围的数据,这样在容器内就会存在多个锁定区间的锁(类似数据库的“间隙锁”),每一把锁锁一段数据,这样在多线程访问时不同段的数据时,就不会存在锁竞争了,这样便可以有效地提高并发效率

在ConcurrentHashMap中,Segment是一个类,实际上每一个segment都是一个HashEntry<K,V>[] table, table中的每一个元素本质上都是一个HashEntry的单向队列。

每一个Segment都拥有一个锁,当进行写操作时,只需要锁定一个Segment,而其它Segment中的数据是可以访问的。本质上Segment类就是一个小的hashmap,里面table数组存储了各个节点的数据

由于Segment继承ReentrantLock,所以在put时通过ReentrantLock的tryLock()方法尝试去获取锁,如果获取成功就直接插入相应的位置,如果已经有线程获取该Segment的锁,那当前线程会以自旋的方式(自旋就是一个循环获取锁的过程)继续调用tryLock()方法去获取锁,超过指定次数就挂起,等待唤醒

CAS+synchonized

JDK1.8版本则做了2点修改

1、将原先table数组+单向链表的数据结构,变更为table数组+单向链表+红黑树的结构.(与HashMap的变化基本一致)

2、取消segments字段,直接采用transient volatile HashEntry<K,V>[] table保存数据,采用table数组元素作为锁,从而实现了对每一行数据进行加锁,并发控制使用synchronized和CAS来操作

synchronized只锁定当前链表或红黑树的首节点,这样只要哈希不冲突(不操作同一位置元素),就不会产生并发,效率又提升很多。

CASCompare And Swap,比较交换)算法,它包含三个参数 CAS(V, E, N): V 表示要更新的变量, E 表示预期值, N 表示新值。基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值(预期值)是否相等,如果相等,则接受你指定的修改的值(新值),否则证明已经有别的线程修改过该变量的值,拒绝你的操作。因为当前线程中的值已经不是最新的值,你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁,SVN的思想是比较类似的。 **

本文基于JDK1.8进行编写

简单使用

package com.java.map;
​
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
​
/**
 * @description
 * @date: 2021-05-29 23:07
 */
public class ConcurrentHashMapCode {
    public static void main(String[] args) {
        Map<String,Object> concurrentHashMap = new ConcurrentHashMap<>();
        concurrentHashMap.put("one",1);
        concurrentHashMap.put("two", 2);
        System.out.println(concurrentHashMap);
        // 如果传入key对应的value已经存在,就返回存在的value,不进行替换
        concurrentHashMap.putIfAbsent("one", 2);
        concurrentHashMap.putIfAbsent("three", 3);
        System.out.println(concurrentHashMap);
    }
}

输出:

{one=1, two=2}
{one=1, two=2, three=3}

思考

ConcurrentHashMap与HashMap的比较

线程安全性

  • HashMap不是线程安全的,多线程并发下扩容可能会导致数据覆盖的情况。
  • ConcurrentHashMap线程安全,在ConcurrentHashMap中,大量使用了U.compareAndSwapXXX的方法,这个方法是利用一个CAS算法实现无锁化的修改值的操作,他可以大大降低锁代理的性能消耗。同时,在ConcurrentHashMap中还定义了三个原子操作,用于对指定位置的节点进行操作。这三种原子操作被广泛的使用在ConcurrentHashMap的get和put等方法中。
  • 我们可以发现JDK8中ConcurrentHashMap的实现使用的是锁分离思想,只是锁住的是一个node,而锁住Node之前的操作是基于在volatile和CAS之上无锁并且线程安全的。

null值

  • HashMap允许key和value为空
  • ConcurrentHashMap不允许

迭代

  • HashMap在用iterator遍历的同时,不允许修改HashMap;
  • ConcurrentHashMap允许该行为,并且更新对后续的遍历是可见的;

扩容机制不同

HashMap的扩容机制

HashMap的扩容,一般都包含两个步骤: ① table数组的扩容 table数组的扩容,一般就是新建一个2倍大小的槽数组,这个过程通过由一个单线程完成,且不允许出现并发。

② 数据迁移 所谓数据迁移,就是把旧table中的各个槽中的结点重新分配到新table中。比如,单线程情况下,可以遍历原来的table,然后put到新table中。

这一过程通常涉及到槽中key的rehash,因为key映射到桶的位置与table的大小有关,新table的大小变了,key映射的位置一般也会变化。

ConcurrentHashMap的扩容机制

ConcurrentHashMap在处理rehash的时候,并不会重新计算每个key的hash值,而是利用了一种很巧妙的方法。 ConcurrentHashMap内部的table数组的大小必须为2的幂次,原因是让key均匀分布,减少冲突,这只是其中一个原因。 另一个原因就是:当table数组的大小为2的幂次时,通过key.hash & table.length-1这种方式计算出的索引i,当table扩容后(2倍),新的索引要么在原来的位置i,要么是i+n

我们来看个例子:

上图中: 扩容前,table数组大小为16,key1和key2映射到同一个索引5; 扩容后,table数组的大小变成 2*16=32 ,key1的索引不变,key2的索引变成 5+16=21

而且还有一个特点,扩容后key对应的索引如果发生了变化,那么其变化后的索引最高位一定是1(见扩容后key2的最高位)。

这种处理方式非常利于扩容时多个线程同时进行的数据迁移操作,因为旧table的各个桶中的结点迁移不会互相影响,所以就可以用“分治”的方式,将整个table数组划分为很多部分,每一部分包含一定区间的桶,每个数据迁移线程处理各自区间中的结点,对多线程同时进行数据迁移非常有利。


看到这里就点个赞吧👇分享更多技术文章,去帮助更多的人,这里有我所有知识库哟~ 🐌 https://www.yuque.com/yingwenerjie

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3秒搞定ArrayList

    底层是一个Object[],添加到ArrayList中的数据保存在了elementData属性中。

    老兵程序员
  • 3秒种搞定HashMap

    老兵程序员
  • Spring Boot 启动,1 秒搞定!

    原文: dev.to 翻译: ImportNew.com - 唐尤华 译文: http://www.importnew.com/30647.html

    Java技术栈
  • 【译文】epoll() 3步搞定

    并不久远之前,设置单个Web服务器以支持10,000个并发连接还是一项伟大的壮举。有许多因素使开发这样的Web服务器成为可能,例如nginx,它比以前的服务器可...

    袁承兴
  • 如何阅读jdk源码?

    这篇文章主要讲述jdk本身的源码该如何阅读,关于各种框架的源码阅读我们后面再一起探讨。

    彤哥
  • 还在为怎么阅读 JDK 源码犯愁吗?

    这篇文章主要讲述jdk本身的源码该如何阅读,关于各种框架的源码阅读我们后面再一起探讨。

    zhisheng
  • java并发编程的艺术笔记第六章——java并发容器和框架

    ConcurrentHashMap由Segment数组结构和HashEntry数组结构组成,Segement是一种可重入锁,在ConcurrentHashMap...

    会跳舞的机器人
  • 046. 使用 Java 实现一个简单的内存缓存

    山海散人
  • 3个案例秒懂,大数据是如何搞定用户交易画像的

    如何构建用户交易画像? 基于交易行为,我们可以依据 3 个关键指标进行用户分群。 1. 流失风险。看每个用户上一次交易距今的时间,上次交易距今时间越远流失风险越...

    BestSDK
  • 微信开发如何保证access_token/jsapi_ticket长期有效

    为了使第三方开发者能够为用户提供更多更有价值的个性化服务,微信公众平台开放了许多接口,包括自定义菜单接口、客服接口、获取用户信息接口、用户分组接口、群发接口等,...

    似水的流年
  • 微信开发如何保证access_token/jsapi_ticket长期有效

    为了使第三方开发者能够为用户提供更多更有价值的个性化服务,微信公众平台开放了许多接口,包括自定义菜单接口、客服接口、获取用户信息接口、用户分组接口、群发接口...

    似水的流年
  • 微信开发如何保证access_token/jsapi_ticket长期有效

    为了使第三方开发者能够为用户提供更多更有价值的个性化服务,微信公众平台开放了许多接口,包括自定义菜单接口、客服接口、获取用户信息接口、用户分组接口、群发接口等,...

    似水的流年
  • Java内存缓存-通过Map定制简单缓存

    在程序中,缓存是一个高速数据存储层,其中存储了数据子集,且通常是短暂性存储,这样日后再次请求此数据时,速度要比访问数据的主存储位置快。通过缓存,可以高效地重用之...

    小码农薛尧
  • 3. 搞定收工,PropertyEditor就到这

    上篇文章介绍了PropertyEditor在类型转换里的作用,以及举例说明了Spring内置实现的PropertyEditor们,它们各司其职完成 String...

    YourBatman
  • 手写动态定时任务

    在开发中我们一般使用quartz来做动态的定时任务,但是这是别人写好的开发框架,要是我们自己想手动实现一个呢。那应该怎么做呢。

    分享干货的你
  • 假如我是面试官,我会这样虐你

    4、你为什么要离开上家公司?你上家公司在xxx,我们公司在xxx,离这么远为什么要选择我们这里?

    zhisheng
  • 分布式改造剧集2---DIY分布式锁

    SecondWorld
  • 图解ConcurrentHashMap

    上篇文章介绍了 HashMap 在多线程并发情况下是不安全的,多线程并发推荐使用 ConcurrentHashMap ,那么 ConcurrentHashMap...

    陈宇明
  • RocketMQ消费--Broker端处理逻辑【源码笔记】

    1.Broker是如何处理消费流程的? 2.消费进度是如何流转的? 说明:本文分析均为PUSH消费模式

    瓜农老梁

扫码关注云+社区

领取腾讯云代金券