【Java并发编程 十一】JUC并发包下并发容器类(上)

简介: 【Java并发编程 十一】JUC并发包下并发容器类(上)

JUC包下的容器类分为两部分,一部分是并发集合类,一部分是并发队列类,其中并发集合类可以解决我们集合使用过程中的多线程并发问题,而并发队列类则主要被当做阻塞队列使用,是线程池中的关键参数之一。接下来我们分两部分来详细介绍下这部分内容。

普通集合类

Java集合框架主体内容包括Collection集合和Map类;而Collection集合又可以划分为List(队列)、Set(集合)以及队列(Queue)Map类也有自己的不同实现类。依据用途,我们可以把List、Set和Map理解为集合类,Queue当做队列类。

普通集合类概述

List的实现类主要有: LinkedList、ArrayList、Vector、Stack。

  • LinkedList是双向链表实现的双端队列;它不是线程安全的,只适用于单线程。
  • ArrayList是数组实现的队列,它是一个动态数组;它也不是线程安全的,只适用于单线程。
  • Vector是数组实现的矢量队列,它也一个动态数组;不过和ArrayList不同的是,Vector是线程安全的的,它支持并发。
  • Stack是Vector实现的栈,和Vector一样,它也是线程安全的

综上,Vector和Stack线程安全,LinkedList和ArrayList只适合单线程使用。

Set的实现类主要有: HastSet、LinkedHashSet、TreeSet

  • HashSet 是一个没有重复元素的集合,它通过HashMap实现的;HashSet不是线程安全的,只适用于单线程。
  • LinkedHashSet继承自HashSet,唯一的区别是LinkedHashSet内部使用的是LinkHashMap。这样做的意义或者好处就是LinkedHashSet中的元素顺序是可以保证的,也就是说遍历序和插入序是一致的
  • TreeSet也是一个没有重复元素的集合,不过和HashSet不同的是,TreeSet中的元素是有序的;它是通过TreeMap实现的;TreeSet也不是线程安全的,只适用于单线程。

综上, HastSet、TreeSet、LinkedHashSet都只适合单线程使用。

Map的实现类主要有: HashMap、LinkedHashMap、TreeMap、Hashtable、WeakHashMap,。

  • HashMap是存储键-值对的哈希表;它不是线程安全的,只适用于单线程。
  • LinkedHashMap 是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的
  • TreeMap也是哈希表,不过TreeMap中的“键-值对”是有序的,它是通过R-B Tree(红黑树)实现的;TreeMap不是线程安全的,只适用于单线程
  • WeakHashMap是也是哈希表;和HashMap不同的是,HashMap的“键”是强引用类型,而WeakHashMap的“键”是弱引用类型,也就是说当WeakHashMap 中的某个键不再正常使用时,会被从WeakHashMap中被自动移除,WeakHashMap也不是线程安全的,只适用于单线程。
  • Hashtable也是哈希表;和HashMap不同的是,Hashtable是线程安全的,支持并发。

综上, Map里只有Hashtable是线程安全的,支持并发。

线程不安全的问题

如果使用线程不安全的集合极容易出现问题,例如两个线程同时往一个list里添加元素,他们同时判断一个索引上没有值,同时添加,那么实际上只添加了一次,我们举个例子看看:

public class ThreadTest {
    public static void main(String[] args) throws InterruptedException {
        List<String> list=new ArrayList<>();
        for (int i=0;i<500;i++) {
            Thread thread=new Thread(()->{
                try {
                    Thread.sleep(50);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                list.add(Thread.currentThread().getName()+"线程添加的一个元素");
            });
            thread.start();
        }
        Thread.sleep(2000);
        System.out.println("tml说在线程不安全条件下,500个线程并发后list只增加了"+list.size()+"个元素");
    }
}

打印结果为:

tml说在线程不安全条件下,500个线程并发后list只增加了493个元素

如果我们换成线程安全的Vector:

public class ThreadTest {
    public static void main(String[] args) throws InterruptedException {
        Vector<String> vector=new Vector<>();
        for (int i=0;i<500;i++) {
            Thread thread=new Thread(()->{
                try {
                    Thread.sleep(50);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                vector.add(Thread.currentThread().getName()+"线程添加的一个元素");
            });
            thread.start();
        }
        Thread.sleep(2000);
        System.out.println("tml说在线程安全条件下,500个线程并发后vector也增加了"+vector.size()+"个元素");
    }
}

返回结果为:

tml说在线程安全条件下,500个线程并发后vector也增加了500个元素

其实不光写会造成问题,在同一时间多个线程无法对同一个List进行读取和增删,否则就会抛出并发异常,因为在读的时候被别人改了

Exception in thread "Thread-403" java.lang.ArrayIndexOutOfBoundsException: 366
  at java.util.ArrayList.add(ArrayList.java:463)
  at com.company.ThreadTest.lambda$main$0(ThreadTest.java:18)
  at java.lang.Thread.run(Thread.java:748)
tml说在线程不安全条件下,500个线程并发后list只增加了491个元素

如何线程安全

综合以上考虑,线程安全的实现类有vector,stack,hashtable 为了方便,我们将前面介绍集合类统称为java集合包。java集合包大多是非线程安全的,虽然可以通过Collections工具类中的方法获取java集合包对应的同步类,但是这些同步类的并发效率并不是很高。为了更好的支持高并发任务,Java在JUC包中添加了java集合包中单线程类的对应的支持高并发的类。例如,ArrayList对应的高并发类是CopyOnWriteArrayListHashMap对应的高并发类是ConcurrentHashMap,等等。

并发集合类

考虑到普通集合类的问题,我们来看看并发集合类如何解决这样的问题。对应于普通集合类的List、Set以及Map,JUC包中都一一提供了对应的实现方式。在并发编程中使用HashMap可能导致程序死循环。而使用线程安全的HashTable效率又非常低下,基于以上两个原因,便有了ConcurrentHashMap的登场机会

ConcurrentHashMap

ConcurrentHashMap是线程安全且高效的HashMap。一起了解下该容器是如何在保证线程安全的同时又能保证高效的操作。

  • 线程不安全的HashMap,在多线程环境下,使用HashMap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap,因为多线程会导致HashMap的Entry链表形成环形数据结构,一旦形成环形数据结构,Entry的next节点永远不为空,就会产生死循环获取Entry
  • 效率低下的HashTable,HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法,其他线程也访问HashTable的同步方法时,会进入阻塞或轮询状态。如线程1使用put进行元素添加,线程2不但不能使用put方法添加元素,也不能使用get方法来获取元素,所以竞争越激烈效率越低

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

ConcurrentHashMap结构

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。

  • Segment,一个ConcurrentHashMap里包含一个Segment数组。Segment的结构和HashMap类似,是一种数组和链表结构,【JDK1.7】Segment是一种可重入锁(ReentrantLock),在ConcurrentHashMap里扮演锁的角色
  • HashEntry,则用于存储键值对数据。一个Segment里包含一个HashEntry数组,每个HashEntry是一个链表结构的元素,每个Segment守护着一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时,必须首先获得与它对应的Segment锁

整体结构如下,数据结构为:Segment+HashEntry数组+链表

JDK 1.8中ConcurrentHashMap的实现已经摒弃了Segment的概念,而是直接使用Node数组+链表+红黑树(与HashMap的底层实现相同)的数据结构实现,并发控制使用了synchronized和CAS操作。整体就像是优化过且线程安全的HashMap,虽然在JDK 1.8中还能看到Segment的数据结构,但已经简化了其属性,只是为了兼容旧版本

ConcurrentHashMap初始化

ConcurrentHashMap初始化方法是通过initialCapacity、loadFactor和concurrencyLevel等几个参数来初始化segment数组、段偏移量segmentShift、段掩码segmentMask和每个segment里的HashEntry数组来实现的

  • initialCapacity,ConcurrentHashMap的初始容量,初始默认为16
  • concurrencyLevel/ssize,segments数组的大小,默认为16,最大为65536,concurrencyLevel 表示并发度,默认16。并发度可以理解为程序运行时能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数,实际上就是ConcurrentHashMap中的分段锁个数,即segments数组的长度
  • loadFactor, 扩容因子,默认0.75,当一个Segment存储的元素数量大于threshold时,该Segment会进行一次扩容
  • cap,segment里HashEntry数组的长度,为initialCapacity除以ssize的倍数,如果c大于1,就会取大于等于c的2的N次方值,所以cap不是1就是2的N次方
  • threshold,单个segment的容量,值为threshold = (int)cap*loadFactor

那么我们计算的时候可以依据初始值来进行一系列计算。例如initialCapacity为16个元素,负载因子设置为0.75,ssize为16,则c=16/16等于1,则cap为1,也就是每个segment数组长度为1,threshold 容量为(int)1*0.75=0

初始化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);

由上面代码可知,ssize用位运算来计算(ssize <<= 1),所以segments数组的大小取值为2的N次方,即为大于或等于concurrencyLevel的最低的N次方值来作为segment数组的长度。假如concurrencyLevel等于14、15或16,ssize都会等于16,即容器里锁的个数也是16

当然concurrencyLevel最大只能用16位的二进制来表示,即65535,这意味着segments数组的长度最大为65536,对应的二进制为16位

初始化segmentShift和segmentMask

这两个全局变量需要在定位segment的时的散列算法里使用,由初始化segments数组的代码中可知,

  • sshift等于ssize从1向左移位的次数,在默认情况下concurrencyLevel等于16,则1需要向左移位移动4次,所以sshift等于4
  • 段偏移量segmentShift用于定位参与散列预算的位数,segmentShift = 32 - sshift,所以默认为28.
  • segmentMask是散列运算的掩码,segmentMask = ssize -1,即默认为15,掩码的二进制各个位的值都是1。

因为ssize的最大长度为65536,所以segmentShift最大值为16,segmentMask最大值为65535,对应的二进制为16位,每个位都是1。

相关文章
|
3天前
|
安全 Java 程序员
Java多线程基础-17:简单介绍一下JUC中的 ReentrantLock
ReentrantLock是Java并发包中的可重入互斥锁,与`synchronized`类似但更灵活。
25 0
|
3天前
|
Java 程序员
Java多线程基础-16:简述Java并发编程JUC中的Callable接口
Callable接口是Java中用于描述带有返回值任务的接口,与Runnable相对,后者无返回值。Callable的call()方法用于执行具体任务并返回结果。
14 0
|
3天前
|
小程序 前端开发 定位技术
微信小程序-常用的视图容器类组件
该内容是关于微信小程序组件的分类和部分具体组件的介绍。主要分为9大类:视图容器、基础内容、表单组件、导航组件、媒体组件、地图组件、画布组件、开放能力和无障碍访问。其中详细讲解了`view`、`scroll-view`、`swiper`及`swiper-item`等组件的用途和示例。`view`用于构建页面布局,`scroll-view`支持滚动效果,`swiper`则用于创建轮播图。此外,还提到了`root-portal`、`page-container`等其他特殊用途的组件。
7 0
|
4天前
|
安全 Java 开发者
探索Java中的多线程编程与并发控制
多线程编程是Java编程中不可或缺的一部分,它允许程序同时执行多个任务,从而显著提高程序的整体性能。然而,多线程编程也带来了诸如数据不一致、死锁等并发问题。本文将深入探讨Java中的多线程编程技术,包括线程的创建、同步与通信,并介绍几种常用的并发控制策略,旨在帮助读者更好地理解并发编程的复杂性和挑战,并学会如何编写高效、安全的并发程序。
|
6天前
|
缓存 安全 Java
JAVA多线程编程与并发控制
```markdown Java多线程编程与并发控制关键点:1) 通过Thread或Runnable创建线程,管理线程状态;2) 使用synchronized关键字和ReentrantLock实现线程同步,防止数据竞争;3) 利用线程池(如Executors)优化资源管理,提高系统效率。并发控制需注意线程安全,避免死锁,确保程序正确稳定。 ```
|
12天前
|
安全 Java 容器
Java一分钟之-并发编程:并发容器(ConcurrentHashMap, CopyOnWriteArrayList)
【5月更文挑战第18天】本文探讨了Java并发编程中的`ConcurrentHashMap`和`CopyOnWriteArrayList`,两者为多线程数据共享提供高效、线程安全的解决方案。`ConcurrentHashMap`采用分段锁策略,而`CopyOnWriteArrayList`适合读多写少的场景。注意,`ConcurrentHashMap`的`forEach`需避免手动同步,且并发修改时可能导致`ConcurrentModificationException`。`CopyOnWriteArrayList`在写操作时会复制数组。理解和正确使用这些特性是优化并发性能的关键。
21 1
|
15天前
|
存储 安全 Java
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
11 0
|
15天前
|
存储 算法 Java
12张图一次性搞懂高性能并发容器ConcurrentLinkedQueue
12张图一次性搞懂高性能并发容器ConcurrentLinkedQueue
|
15天前
|
Java
【Java多线程】面试常考 —— JUC(java.util.concurrent) 的常见类
【Java多线程】面试常考 —— JUC(java.util.concurrent) 的常见类
30 0
|
15天前
|
Kubernetes Java 调度
Java容器技术:Docker与Kubernetes
Java容器技术:Docker与Kubernetes
82 0