Java并发20-并发容器中的坑

后端

发布日期: 2020-04-16

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

Java并发20-并发容器中的坑

Java中的容器主要可分为四个大类，分别是List、Map、Set 和Queue。

如何将非线程安全容器变成线程安全—Java并发12：把非线程安全容器封装在对象内部，然后控制好访问路径。

SafeArrayList<T>{
  //封装ArrayList
  List<T> c = new ArrayList<>();
  //控制访问路径
  synchronized T get(int idx){
    return c.get(idx);
  }

  synchronized void add(int idx, T t) {
    c.add(idx, t);
  }

  synchronized boolean addIfNotExist(T t){
    if(!c.contains(t)) {
      c.add(t);
      return true;
    }
    return false;
  }
}

JDK做了类似的包装：

List list = Collections.synchronizedList(new ArrayList());
Set set = Collections.synchronizedSet(new HashSet());
Map map = Collections.synchronizedMap(new HashMap());

注意竞态条件

切记：组合操作需要注意竞态条件问题

List list = Collections.synchronizedList(new ArrayList());
Iterator i = list.iterator(); 
//这里就产生了竞态条件 执行5行的时候 可能已经无next()了。
while (i.hasNext())
  foo(i.next());

正确做法：

List list = Collections.synchronizedList(new ArrayList());
synchronized (list) {  
  Iterator i = list.iterator(); 
  while (i.hasNext())
    foo(i.next());
}

SychronizedList、SychronizedMap、SychronizedSet、Vector、Stack、HashTable都是sychronized关键字实现的，称为同步容器。

Vector、Stack和Hashtable这三个容器不是基于包装类实现的，对这三个容器的遍历，同样要加锁保证互斥。

并发容器

JDK1.5之前主要指同步容器线程安全，但性能差。1.5之后提供了性能更好的并发容器，并发容器遍历线程安全。

List

List 里面只有一个实现类就是CopyOnWriteArrayList。

CopyOnWriteArrayList内部维护了一个数组，成员变量array就指向这个内部数组，所有的读操作都是基于 array进行的，如下图所示，迭代器Iterator遍历的就是array数组。

执行迭代的内部数组

如果遍历array时，还有一个写操作，例如增加元素，CopyOnWriteArrayList会将array复制一份，然后在新复制处理的数组上执行增加元素的操作，执行完之后再将array指向新的数组。

Map

Map接口的两个实现是ConcurrentHashMap和ConcurrentSkipListMap。

ConcurrentHashMap的key无序，ConcurrentSkipListMap的key有序。

它们的key和value都不能为空。

各Map对Key&Value的要求

ConcurrentSkipListMap里面的SkipList本身就是一种数据结构。

跳表插入、删除、查询操作平均的时间复杂度是O(log n)，理论上和并发线程数没有关系，所以在并发度非常高的情况下，若ConcurrentHashMap的性能还不够满意，可以尝试ConcurrentSkipListMap。

Set

Set接口的两个实现是CopyOnWriteArraySet和ConcurrentSkipListSet，使用场景可以参考前面讲述的 CopyOnWriteArrayList和ConcurrentSkipListMap，它们的原理都是一样的。

Queue

阻塞与非阻塞：当队列已满，入队操作阻塞；当队列已空时，出队操作阻塞。

单端与双端：单端即队尾入队，队首出队；双端即队首队尾皆可入队出队。

Java并发包里阻塞队列都用Blocking关键字标识，单端队列使用Queue标识，双端队列使用Deque标识。

单端阻塞队列

ArrayBlockingQueue

内部持有一个数组队列。

LinkedBlockingQueue

内部持有一个链表队列。

SynchronousQueue

内部不持有队列，生产者-消费者模式下，生产者线程的入对操作必须等待消费者线程的出队操作。

LinkedTransferQueue（大佬工作中没用过）

结合了LinkedBlockingQueue&SynchronousQueue功能，性能比LinkedBlockingQueue好。

PriorityBlockingQueue

支持按照优先级出队。

DelayQueue

支持延时出队。
双端阻塞队列

LinkedBlockingDeque
单端非阻塞队列

ConcurrentLinkedQueue
双端非阻塞队列

ConcurrentLinkedDeque