Java 并发集合类

集合

?1 ConcurrentHashMap

??基于散列链表+红黑树实现，类似于 HashMap，JDK 8 进行了优化，利用 volatile + CAS 实现无锁化操作，保证线程安全的同时，提高性能。默认容量16，默认加载因子0.75；
??散列链表和红黑树的内部类定义如下：

// 基本结构
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}
// 红黑树结构，链表长度大于8时转换
static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}

??和 HashMap 比较，多了内部类 TreeBin，它不存储键值，而是指向 TreeNode 列表和它们的根节点，而 ConcurrentHashMap 也是操作 TreeBin。此外，TreeBin 还维护了读写锁状态，这会使得在树重组之前，持有锁的写操作会等待未持锁的读操作完成。

// 指向TreeNode列表和它们的根节点，
static final class TreeBin<K,V> extends Node<K,V> {
    TreeNode<K,V> root;
    volatile TreeNode<K,V> first;
    volatile Thread waiter;
    volatile int lockState;
    static final int WRITER = 1; // 持有写锁时
    static final int WAITER = 2; // 等待写锁时
    static final int READER = 4; // 用来设置读锁的增量值
}

??如何做到线程安全的呢？
??1. sizeCtl：控制表的初始化和重建。负数表示表正在初始化或者重建：
????-1表示在初始化；
????-(1+N)表示有N个正在进行重建的线程；
??2. 节点哈希值表示的状态
????MOVED=-1 表示 forward 节点；
????TREEBIN=-2 表示 treeBin 的根节点；
??3. V put(K key, V value) 操作
????如果表为空，则初始化表；
????如果hash位置为空，则通过CAS设置值；
????如果hash=-1，则帮组扩容；
????如果节点既不为空，也不等于-1，那么锁住该节点，在链表或者红黑树上添加值；
??4. void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) 扩容
????初始化新表，容量是原表的2倍；
????复制元素到新表，处理一个节点就把节点设置为forward；
????当这个节点为空时，通过CAS来设置forward；
????当节点值为-1时，表示forward已经处理过了；
????当节点不为空且不为-1时，锁住节点进行处理；
????其他线程看到节点为forward时，向后遍历来完成；
??5. V get(Object key) 操作
????如果hash值匹配，则直接获取；
????如果hash值小于0，则从树上查找；
????否则，遍历链表寻找；
??6. mappingCount()（推荐，因为其返回值时long） 和 size()，都是调用 sumCount() 来计算
????定义了内部类 CounterCell 来计数，计算总数时，就是把 CounterCell[] 数组的值累加起来即可；

// put 源码
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
    tab = initTable(); // 表长度为空时，初始化表
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
        break;                   // hash的位置为空时，通过CAS设置值
}
else if ((fh = f.hash) == MOVED)
    tab = helpTransfer(tab, f); // 如果节点是 forward 节点，帮助扩容
else {
    synchronized (f) { // 不为空，不是 forward 节点时，synchronized 锁住节点
        if (tabAt(tab, i) == f) { // 锁住后再次判断节点有没有变化
            if (fh >= 0) { 
                ... // 表示要操作链表节点
            }
            else if (f instanceof TreeBin) {
                ... // 表示操作的是TreeBin节点
            }
        }
    }
    if (binCount != 0) {
        if (binCount >= TREEIFY_THRESHOLD)
            treeifyBin(tab, i); // 链表长度大于8，转成红黑树
    }
}

// 并发扩容的方法
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    if (nextTab == null) {            // 初始化新的表，容量是原表的2倍
        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
        nextTab = nt;
        nextTable = nextTab; // nextTable 是定义的临时表，仅在表重建时不为空
        transferIndex = n; // 表重建时的下一个表的索引
    }
    int nextn = nextTab.length; // 扩容后的表长度
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true; // true 表示该节点已处理
    boolean finishing = false; // 确保已经完成了
    for (int i = 0, bound = 0;;) {
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {
                ... // 完成了
                return;
            }
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { // sizeCtl-1,表示多了一个线程来扩容
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd); // 节点位置是空的，通过CAS设置值为forward
        else if ((fh = f.hash) == MOVED)
            advance = true; // 这个位置是forward节点，表示已经处理了
        else {
            synchronized (f) { // 节点不为空，且不是forward节点，锁住该节点再处理
                ... // 类似put的操作
            }
        }
    }
}

// get 源码
if ((eh = e.hash) == h) {
    if ((ek = e.key) == key || (ek != null && key.equals(ek)))
        return e.val; // 直接获得值
}
else if (eh < 0)
    return (p = e.find(h, key)) != null ? p.val : null; // 在树上查找
while ((e = e.next) != null) {
    if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
        return e.val; // 遍历链表查找
}

// 计数方法
private transient volatile CounterCell[] counterCells; // 数组，存储统计值
@sun.misc.Contended static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}
final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value; // 统计值累加
        }
    }
    return sum;
}

?2 ConcurrentSkipListMap

??基于跳表实现，按照 key 自然排序，key 不能为 null，类似 TreeMap。
??利用 volatile+CAS 来保证线程安全。

static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
}
boolean casValue(Object cmp, Object val) {
    return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
}

?3 ConcurrentSkipListSet

??使用 ConcurrentSkipListMap 实现。

?4 CopyOnWriteArrayList

??基于数组实现，相当于支持并发的 ArrayList，刚创建时初始化为长度0的数组。
??利用写时复制来保证线程安全。
??写时复制：数组是 volatile 类型的，修改数组时，首先 ReentrantLock 加锁，然后复制一个副本数组，对副本进行修改完成后，把原来的数组指向这个新的数组完成赋值。读时不用加锁。

private transient volatile Object[] array;
public boolean add(E e) {
// 加锁进行写时复制
final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        // 拷贝新数组，长度+1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e; 
        // set给volatile的array
        setArray(newElements);
        return true;
  } finally {
        lock.unlock();
    }
}

?5 CopyOnWriteArraySet

??使用 CopyOnWriteArrayList 实现。去重的，但是按照插入顺序排序的。

非阻塞队列

?1 ConcurrentLinkedQueue

??基于链表实现的无界的线程安全的非阻塞队列，遵循 FIFO，利用 volatile+CAS 来保证线程安全。

private static class Node<E> {
    volatile E item;
    volatile Node<E> next;
}
// 初始化 head 和 tail
private transient volatile Node<E> head;
private transient volatile Node<E> tail;
public ConcurrentLinkedQueue() {
    head = tail = new Node<E>(null);
}
// 利用 CAS 修改链表
private boolean casTail(Node<E> cmp, Node<E> val) {
    return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
}

?2 ConcurrentLinkedDeque

??基于双向链表实现的无界的线程安全的非阻塞队列，实现方式类似 ConcurrentLinkedQueue。

// 双向链表
static final class Node<E> {
    volatile Node<E> prev;
    volatile E item;
    volatile Node<E> next;
}

阻塞队列

??实现：通过 ReentrantLock 和 Condition 实现的等待通知模型来实现阻塞队列。

?1 ArrayBlockingQueue

??基于数组实现的阻塞队列，需要指定容量。

// poll 类似
public boolean offer(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 加锁
    try {
        if (count == items.length)
            return false; // 超过长度，返回false，数据丢失
        final Object[] items = this.items;
        items[putIndex] = x; // putIndex表示下一次加元素的索引
        if (++putIndex == items.length)
            putIndex = 0; // 达到长度后，索引位归零
        count++; // 计数+1
        notEmpty.signal(); // 通知可以取值了
        return true;
    } finally {
        lock.unlock(); // 解锁
    }
}

?2 LinkedBlockingQueue

??基于链表实现的阻塞队列，默认容量为 Integer.MAX_VALUE。
??实现类似 ArrayBlockingQueue，计数用的原子类 AtomicInteger。

?3 PriorityBlockingQueue

??基于二叉小顶堆实现的阻塞队列，保证取出的元素是最小的，默认初始化容量11。

?4 DelayQueue

??基于数组实现的延迟阻塞队列。使用时必须实现 Delayed。

原子操作类

??以 AtomicInteger 为例，利用 volatile+CAS 来保证原子操作，直接看源码注释

private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;

private volatile int value;

// 直接获取 volatile 变量
public final int get() {
    return value;
}
// 通过 Unsafe 的 CAS 原子操作 volatile 变量
public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
// 通过 Unsafe 的 CAS 原子操作 + 1
public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

并发工具类

?1 CountDownLatch

??功能：指定 N 个线程等待全部完成后，继续执行。
??实现：内部类 Sync 实现了 AQS 同步器，初始化时设置 AQS 的同步状态来表示 countDown 的数量，await() 方法把当前线程加入到 AQS 等待队列，让当前线程阻塞住，执行 countDown() 方法会把同步状态减1，当减到0时，唤醒等待队列中的线程。

?2 CyclicBarrier

??功能：类似 CountDownLatch，但是支持 reset() 重置状态，能指定到达数量时执行的动作。
??实现：基于 ReentrantLock 和 Condition 实现，核心源码如下

private int dowait(boolean timed, long nanos) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 加锁，保护 count
    try {
        
        if (Thread.interrupted()) {
            breakBarrier(); // 使用 signalAll 唤醒所有线程
            throw new InterruptedException();
        }

        int index = --count; // 线程数量递减
        if (index == 0) {  // 如果线程数量到达 0
            final Runnable command = barrierCommand;
            if (command != null)
                command.run(); // 执行 barrierAction
            return 0;
        }

        // 此时线程数量还没到 0
        for (;;) {
            try {
                if (!timed)
                    trip.await(); // 调用 Condition 的 await 进行等待
                else if (nanos > 0L)
                    nanos = trip.awaitNanos(nanos); // 待超时的等待
            }
        }
    } finally {
        lock.unlock(); // 释放锁
    }
}

线程池

?ThreadPoolExecutor 参数说明：
??1. 核心线程池
??2. 最大线程池
??3. 线程空闲时间
??4. 线程空闲时间单位
??5. 阻塞队列
??6. 线程工厂：创建具有相同特性的一组线程。
??7. 拒绝策略
???CallerRunsPolicy：重试添加当前的任务，会自动重复调用 execute() 方法，直到成功。
???AbortPolicy：对拒绝任务抛弃处理，并且抛出异常。
???DiscardPolicy：对拒绝任务直接无声抛弃，没有异常信息。
???DiscardOldestPolicy：对拒绝任务不抛弃，而是抛弃队列里面等待最久的一个线程，然后把拒绝任务加到队列。

???线程池数量理论值 -> CPU 密集型：N+1；IO 密集型：2N+1

???线程的提交方式：
???1. execute()：用于提交不需要返回值的任务
???2. submit()：用于提交需要返回值的任务，返回future对象。

???线程池线程的执行流程：核心 -> 队列 -> 最大 -> 拒绝策略
???1. 如果当前运行的线程少于核心线程池时，则创建新的线程执行任务；
???2. 如果当前运行的线程大于等于核心线程池时，则把任务加入阻塞队列；
???3. 如果阻塞队列已经满了，则创建新的线程执行任务；
???4. 如果线程数超过了最大线程数，则调用拒绝策略；

原文链接:https://www.cnblogs.com/bigshark/p/11180277.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有