Java并发容器

标签: java并发  java  

​ 在多线程环境中,使用HashMap可能会导致程序死循环,使用线程安全的HashTable效率低效,所以便有了ConcurrentHashMap

ConcurrentHashMap利用锁的分断技术可有效提升并发访问率,在容器里有多把锁,每一把锁用于锁容器其中一部分数据,当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效提升并发访问效率。

ConcurrentHashMap的结构

ConcurrentHashMap由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁;HashEntry用于存储键值对数据,一个ConcurrentHashMap包含一个Segment数组。Segment数组的结构和HashMap类似,是一种数组和链表结构,一个Segment里包含一个HashEntry数组,每个HashEntry是一个链表结构的元素,每个Segment守护一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时,必须先获得与它对应的Segment锁。

ConcurrentHashMap初始化

初始化Segment数组

segments数组的长度ssize是通过ConcurrencyLevel计算得出,为了可以通过按位与的散列算法定位Segments数组的索引,必须保证segments数组的长度是2的N次方,所以必须计算出一个大于或等于concurrencyLevel的最小的2的N次方值来作为segments数组的长度。下面是segments数组的源代码

if(concurrencyLevel > MAX_SEGMENTS){
    concurrencyLevel = MAX_SEGMENTS;
    int sshift = 0;
    int ssize = 1;
    while(ssize < concurrencyLevel){
        ++sshift;
        ssize <<= 1;
    }
    segmentShift = 32 - sshift;
    segmentMask = ssize -1;
    this.segments = Segment.newArray(ssize);
}

concurrencyLevel的最大值是65535,Segments数组的长度最大为65536对应的二进制数组

初始化segmentShift和segmentMask

这两个全局变量需要定位segments的散列算法里使用,sshift等于ssize从1向左移位的次数,在默认情况下concurrencyLevel等于161需要向左移位移动4次,所以sshift等于4segmentShift用于定位参与散列运算的位数,segmentShift等于32减sshift,所以等于28。

初始化每个segment

输入参数initialCapacity是ConcurrentHashMap的初始化容量,loadfactor是每个segment的负载因子,在构造方法中需要通过这两个参数来初始化数组中的每个segment。

if(initialCapacity >MAXIMUM_CAPACITY){
    initialCapacity = MAXIMUM_CAPACITY;
    int c = initialCapacity/ssize;
    if(c * ssize < initialCapacity){
        ++c;
    }
    int cap = 1;
    while(cap < c){
        cap <<= 1;
    }
    for(int i = 0;i<this.segments.length;i++){
        this.segments[i] = new Segment<K,V>(cap,loadFactor);
    }
}

ConcurrentHashMap的操作

get操作

get操作先经过一次再散列,然后使用这个散列值通过散列运算定位到Segment,在通过散列算法定位到元素。

public V get(Object key){
    int hash = hash(key.hashCode());
    return segmentFor(hash).get(key,hash);
}

get操作之所以高效是因为整个get过程不需要加锁,除非读到的值是空才会加锁重读。get方法里面将要使用的共享变量都定义为volatile,定义成volatile的变量,能够在线程之间保持可见性,能够被多线程同时读,并且保证不会读到过期的值,在get操作里只需要读不需要写共享变量count和value,所以不需要加锁。不会读到过期的值,是因为根据Java内存模型Happen-before原则,对volatile字段的写入优先于读操作,即使两个线程同时修改和获取volatile变量,get操作也能够拿到最新的值。

  • put操作

    由于put操作需要对共享变量进行写入操作,为了线程安全,在操作共享变量是必须加锁。插入操作需经历两步:(1)判断是否需要对Segment数组里的HashEntry数组进行扩容;(2)定位添加元素的为位置,然后将其放在HashEntry数组中。根据上面的两个步骤这里又抛出两个问题:是否需要扩容、如何扩容。

    是否需要扩容:在插入元素前会先判断Segment里的HashEntry数组是否超过容量,如果超过阈值,则对数组进行扩容(Segment的扩容判断比HashMap更恰当,因为HashMap是在插入元素后判断元素是否已经达到容量,如果达到了就进行扩容),

    如果扩容:在扩容的时候,为了高效ConcurrentHashMap不会对整个容器进行扩容,而只是对某个Segment数组进行扩容

  • size操作

    在统计size的时候会把所有Segment的put、remove、clean方法全部加锁,这种做法会变得非常低效,ConcurrentHashMap先尝试通过两次不加锁Segment的方式来统计各个Segment大小,通过过程中容器的count发生了变化,则再采用加锁的方式来统计所有Segment的大小,那么ConcurrentHashMap如何判断容器是否发生变化?使用modCount变量,在put、remove、clean方法里操作元素前都会将变量modCount进行加一操作,那么在统计size前后比较modCount是否发生变化,从而知道容器大小是否发生变化。

ConcurrentLinkedQueue

ConcurrentLinkedQueue是个基于链表节点的无界线程安全队列,采用先进先出的规则对节点进行排序,当添加一个元素时,会添加到队列的尾部;当获取一个元素时会返回队列的头元素。采用CAS算法实现。

ConcurrentLinkedQueue的入队列

入队列过程

入队列就是将入队节点添加到队列的尾部,在单线程下入队列比较简单,但在多线程同时进行入对的时候就复杂了许多,这个过程可能会有其他线程入队的情况,如果有个线程正在入队,那么这个线程就必须获取尾节点,然后设置尾结点的下一个节点为入队节点,要是这时有另一个线程插队,那么队列的尾节点就会发生变化,当前线程停止入队操作。这里就需要用到CAS算法

出队列过程

出队列就是从队列里返回一个节点元素,并清空该节点对元素的引用。首先获取头节点的元素,然后判断头节点元素是否为空,如果为空,表示另外一个线程已经进行了一次出队操作将该节点的元素取走,如果不为空,则使用CAS的方式将头节点的引用设置为null,如果CAS成功,则直接返回头节点的元素,如果不为空表示另外一个线程已经进行了一次出队操作更新过了head头节点,导致元素发生变化,需要重新获取头节点。

Java中的阻塞队列

什么是阻塞队列:阻塞队列是个支持阻塞的插入方法和阻塞的移除方法的队列;

  • 支持阻塞的插入方法:当队列满时,队列会阻塞插入元素的线程直到队列不满。
  • 支持阻塞的移除方法:当队列空时,获取元素的线程会等待队列变为非空
版权声明:本文为qq_41343202原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41343202/article/details/106009309

智能推荐

idea基础–(7)–jsp页面Controller路径自动识别的问题“Cannot resolve controller URL ...”,Cannot resolve variable

idea之所以强大,就是强大的代码提示和联想功能,写起代码来简直不要太爽。但是这几天我发现在我的jsp页面中访问controller路径的时候不会自动提示了,对于这么严谨的我肯定要找出原因啊,哈哈。 最终效果:按住ctrl,同时点击左键会自动跳转到对应的controller代码块,爽。 需要同时满足的条件 JSP页面顶部包含如下代码: 在idea的项目设置中显示如下:  若显示的是spring a...

26_Python基础_继承

面向对象三大特性: 封装 根据 职责 将 属性 和 方法 封装 到一个抽象的 类 中 继承 实现代码的重用, 相同的代码不需要重复的编写 多态 不同的对象调用相同的方法,  产生不同的执行结果,  增加代码的灵活度 1.  单继承 1.1 概念 继承的概念:&...

循环

与任何程序设计语言一样Java利用条件语句与循环结构确定流程控制,一下总结一下Java中的循环语句: while do while for switch 对于golang来说: switch非常灵活。从第一个expr为true的case开始执行,如果case带有fallthrough,程序会继续执行下一条case,不会再判断下一条case的expr,如果之后的case都有fallthrough,d...

1638 统计只差一个字符的子串数目(动态规划)

1. 问题描述: 给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation"...

websocket基本原理

HTTP中一个request只能有一个response。而且这个response也是被动的,不能主动发起 因此过去的服务端推送信息是通过客户端不停的轮询实现的 websocket是双向通信协议,提供了服务端主动推送信息的能力 需要客户端(浏览器)和服务端同时支持 如果经过代理的话,还需要代理支持,否则有些代理在长时间无通信时会自动切断连接 因此WS为了保证连接不被断掉,会发心跳 WebSocket...

猜你喜欢

mybatis+ehcache二级缓存

导入jar包 mapper.xml文件开启二级缓存 pojo类实现序列化接口 配置ehcache.xml 测试...

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...