yangl的博客

积少成多

0%

并发容器

发表于 更新于 分类于 Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

JDK提供的

  • ConcurrentHashMap: 线程安全的 HashMap
  • CopyOnWriteArrayList: 线程安全的 List，在读多写少的场合性能非常好，远远好于 Vector.
  • ConcurrentLinkedQueue: 高效的并发队列，使用链表实现。可以看做一个线程安全的 LinkedList，这是一个非阻塞队列。
  • BlockingQueue: 这是一个接口，JDK 内部通过链表、数组等方式实现了这个接口。表示阻塞队列，非常适合用于作为数据共享的通道。
  • ConcurrentSkipListMap: 跳表的实现。这是一个 Map，使用跳表的数据结构进行快速查找。

ConcurrentHashMap

  • HashMap的线程安全版
  • 无论是读操作还是写操作都能保证很高的性能：在进行读操作时(几乎)不需要加锁，而在写操作时通过锁分段技术只对所操作的段加锁而不影响客户端对其它段的访问。

CopyOnWriteArrayList

  • 在很多应用场景中，读操作可能会远远大于写操作。由于读操作根本不会修改原有的数据，因此对于每次读取都进行加锁其实是一种资源浪费。
  • CopyOnWriteArrayList 读取是完全不用加锁的，并且更厉害的是：写入也不会阻塞读取操作。只有写入和写入之间需要进行同步等待。
  • 怎么操作
    • 在写操作的时候，先将原来的数组复制一份，在副本上进行写操作，写完后将副本替换原来的数据，保证了写操作不会影响多操作
  • CopyOnWriteArrayList 写操作源码
    • CopyOnWriteArrayList 写入操作 add() 方法在添加集合的时候加了锁，保证了同步，避免了多线程写的时候会 copy 出多个副本出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean add(E e) {
       final ReentrantLock lock = this.lock;
       lock.lock();//加锁
       try {
           Object[] elements = getArray();
           int len = elements.length;
           Object[] newElements = Arrays.copyOf(elements, len + 1);//拷贝新数组
           newElements[len] = e;
           setArray(newElements);
           return true;
       } finally {
           lock.unlock();//释放锁
       }
   }

ConcurrentLinkedQueue

  • 非阻塞队列
  • 使用链表作为数据结构
  • 使用CAS非阻塞算法实现线程安全

BlockingQueue

  • 阻塞队列

  • 广泛使用在“生产者-消费者”问题中

  • 当队列容器已满，生产者线程会被阻塞，直到队列未满；当队列容器为空时，消费者线程会被阻塞，直至队列非空时为止。

  • 实现类

    img

ArrayBlockingQueue

  • ArrayBlockingQueue 是 BlockingQueue 接口的有界队列实现类，底层采用数组来实现。
  • ArrayBlockingQueue 一旦创建，容量不能改变。
  • 并发控制采用可重入锁来控制，不管是插入操作还是读取操作，都需要获取到锁才能进行操作。

LinkedBlockingQueue

  • LinkedBlockingQueue 底层基于单向链表实现的阻塞队列，可以当做无界队列也可以当做有界队列来使用，同样满足 FIFO 的特性，与 ArrayBlockingQueue 相比起来具有更高的吞吐量，为了防止 LinkedBlockingQueue 容量迅速增，损耗大量内存。通常在创建 LinkedBlockingQueue 对象时，会指定其大小，如果未指定，容量等于 Integer.MAX_VALUE。

PriorityBlockingQueue

  • PriorityBlockingQueue 是一个支持优先级的无界阻塞队列。默认情况下元素采用自然顺序进行排序，也可以通过自定义类实现 compareTo() 方法来指定元素排序规则，或者初始化时通过构造器参数 Comparator 来指定排序规则。
  • 并发控制采用的是 ReentrantLock

ConcurrentSkipListMap

  • 使用跳表实现 Map 和使用哈希算法实现 Map 的另外一个不同之处是：哈希并不会保存元素的顺序，而跳表内所有的元素都是排序的。因此在对跳表进行遍历时，你会得到一个有序的结果。所以，如果你的应用需要有序性，那么跳表就是你不二的选择。JDK 中实现这一数据结构的类是 ConcurrentSkipListMap。

跳表

  • 对于一个单链表，即使链表是有序的，如果我们想要在其中查找某个数据，也只能从头到尾遍历链表，这样效率自然就会很低，跳表就不一样了。跳表是一种可以用来快速查找的数据结构，有点类似于平衡树。它们都可以对元素进行快速的查找。但一个重要的区别是：对平衡树的插入和删除往往很可能导致平衡树进行一次全局的调整。而对跳表的插入和删除只需要对整个数据结构的局部进行操作即可。这样带来的好处是：在高并发的情况下，你会需要一个全局锁来保证整个平衡树的线程安全。而对于跳表，你只需要部分锁即可。这样，在高并发环境下，你就可以拥有更好的性能。而就查询的性能而言，跳表的时间复杂度也是 O(logn) 所以在并发数据结构中，JDK 使用跳表来实现一个 Map。

![img](java-juc-并发容器/Image [1].png)

  • 跳表的本质是同时维护了多个链表，并且链表是分层的，最低层的链表维护了跳表内所有的元素，每上面一层链表都是下面一层的子集。
  • 跳表内的所有链表的元素都是排序的。查找时，可以从顶级链表开始找。一旦发现被查找的元素大于当前链表中的取值，就会转入下一层链表继续找。这也就是说在查找过程中，搜索是跳跃式的。

![img](java-juc-并发容器/Image [2].png)

  • 查找 18 的时候原来需要遍历 18 次，现在只需要 7 次即可。针对链表长度比较大的时候，构建索引查找效率的提升就会非常明显。
  • 跳表是一种利用空间换时间的算法。

----------- 本文结束啦感谢您阅读 -----------