Java之juc旅途-collection(七)

不念不忘少年蓝@ 2023-09-28 17:12 3阅读 0赞

### 概述 ###

juc包还提供了n个线程安全的集合：

*  ConcurrentHashMap：线程安全的Map
 *  ConcurrentLinkedDeque：线程安全的先入后出的栈
 *  ConcurrentLinkedQueue：线程安全的先入先出的队列
 *  ConcurrentSkipListMap: 线程安全的跳表Map
 *  ConcurrentSkipListSet：线程安全的跳表Set
 *  CopyOnWriteArrayList：线程安全的快照写List
 *  CopyOnWriteArraySet：线程安全的快照写Set

下面逐一解析。

### ConcurrentHashMap ###

在JDK1.7版本中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成, 采用了 CAS + ReentrantLock 来保证并发安全性。  
在JDK1.8版本中，它是由数据，单项链表，红黑树来构成，采用了 CAS + synchronized 来保证并发安全性。

#### get ####

在JDK1.7版本中，经过一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表进行对比，成功就返回，不成功就返回null。

在JDK1.8版本中可以分为三个步骤来描述：

1.  计算hash值，定位到该table索引位置，如果是首节点符合就返回
2.  如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回
3.  以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null

#### put ####

在JDK1.7版本中，当执行put操作时，会进行第一次key的hash来定位Segment的位置，如果该Segment还没有初始化，即通过CAS操作进行赋值，然后进行第二次hash操作，找到相应的HashEntry的位置，这里会利用继承过来的锁的特性，在将数据插入指定的HashEntry位置时（链表的尾端），会通过继承ReentrantLock的tryLock（）方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用tryLock（）方法去获取锁，超过指定次数就挂起，等待唤醒。

在JDK1.8版本中，分成以下六步流程来概述。

1.  如果没有初始化就先调用initTable（）方法来进行初始化过程
2.  如果没有hash冲突就直接CAS插入
3.  如果还在进行扩容操作就先进行扩容
4.  如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，
5.  最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环
6.  如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容

#### 扩容 ####

在JDK1.7版本中，Segment\[\]数组大小是不可变的，扩容操作是将Segment类中HashEntry\[\]扩容到原来的两倍。

在JDK1.8版本中，当往hashMap中成功插入一个key/value节点时，有可能触发扩容动作：  
1、如果新增节点之后，所在链表的元素个数达到了阈值 8，则会调用treeifyBin方法把链表转换成红黑树，不过在结构转换之前，会对数组长度进行判断，实现如下：

*  如果数组长度n小于阈值MIN\_TREEIFY\_CAPACITY，默认是64，则会调用tryPresize方法把数组长度扩大到原来的两倍，并触发transfer方法，重新调整节点的位置。

2、新增节点之后，会调用addCount方法记录元素个数，并检查是否需要进行扩容，当64元素个数达到阈值时，会触发transfer方法，重新调整节点的位置。  
3、当前线程发现此时map正在扩容，则通过helpTransfer方法协助扩容

### ConcurrentLinkedDeque ###

ConcurrentLinkedDeque 是基于链表的无限双端队列，线程安全，不允许 null 元素。  
ConcurrentLinkedDeque 内部通过 CAS 来实现线程同步，一般来说，如果需要使用线程安全的双端队列，那么推荐使用该类。  
由于双端队列的特性，该类同样可以当做栈来使用，所以如果需要在并发环境下使用栈，也可以使用该类。  
[  
][Link 1]  
在JDK1.9后，引入了VarHandle，JUC包中对于变量的访问基本上都使用VarHandle，看下保证线程安全的核心成员：

private static final VarHandle HEAD;
        private static final VarHandle TAIL;
        private static final VarHandle PREV;
        private static final VarHandle NEXT;
        private static final VarHandle ITEM;

在进行元素修改时，都是通过这些成员的CAS来保证线程安全的，比如添加元素时最终调用的方法：

private void linkLast(E e) {
        
            final Node<E> newNode = newNode(Objects.requireNonNull(e));
    
            restartFromTail:
            for (;;)
                for (Node<E> t = tail, p = t, q;;) {
        
                    if ((q = p.next) != null &&
                        (q = (p = q).next) != null)
                        // Check for tail updates every other hop.
                        // If p == q, we are sure to follow tail instead.
                        p = (t != (t = tail)) ? t : q;
                    else if (p.prev == p) // NEXT_TERMINATOR
                        continue restartFromTail;
                    else {
        
                        // p is last node
                        PREV.set(newNode, p); // CAS piggyback
                        if (NEXT.compareAndSet(p, null, newNode)) {
        
                            // Successful CAS is the linearization point
                            // for e to become an element of this deque,
                            // and for newNode to become "live".
                            if (p != t) // hop two nodes at a time; failure is OK
                                TAIL.weakCompareAndSet(this, t, newNode);
                            return;
                        }
                        // Lost CAS race to another thread; re-read next
                    }
                }
        }

### ConcurrentLinkedQueue ###

它其实跟ConcurrentLinkedDueue的运作模式基本一样。所以只给了特性总结：

1.  重要特性：链表结构，自旋非阻塞，容量无界。
2.  入队列：入队列自旋直到成功，不允许插入null对象。
3.  出入队列顺序：先进先出。
4.  非原子、非安全：size方法，迭代器等方法不保证原子和安全。
5.  节省CAS开销：头尾节点指针不一定指向真正的头尾节点。

### ConcurrentSkipListMap ###

跳表（Skip List）是一种类似于链表的数据结构，其查询、插入、删除的时间复杂度都是 O(logn)。特性如下：

1.  跳表由很多层组成；
2.  每一层都是一个有序的链表；
3.  最底层的链表包含所有元素；
4.  对于每一层的任意一个节点，不仅有指向其下一个节点的指针，也有指向其下一层的指针；
5.  如果一个元素出现在N层的链表中，则它在N层以下的链表也都会出现。

举个例子：  
如图，\[1\]和\[40\]节点有3层，\[8\]和\[18\]节点有2层。每一层都是有序的链表。如果要查找目标节点\[15\]，大致过程如下：

1.  首先查看\[1\]节点的第1层，发现\[1\]节点的下一个节点为\[40\]，大于15，那么查找\[1\]节点的下一层；
2.  查找\[1\]节点的第2层，发现\[1\]节点的下一个节点为\[8\]，小于15，接着查看下一个节点，发现下一个节点是\[18\]，大于15，因此查找\[8\]节点的下一层；
3.  查找\[8\]节点的第2层，发现\[8\]节点的下一个节点是\[10\]，小于15，接着查看下一个节点\[13\]，小于15，接着查看下一个节点\[15\]，发现其值等于15，因此找到了目标节点，结束查询。

[  
][Link 2]

![在这里插入图片描述][5c3a52d363d4429faeb8622e2cc17ca3.png]

ConcurrentSkipListMap用到了两种结构的节点**Node跟Index**。  
**Node**节点代表了真正存储数据的节点，包含了key、value、指向下一个节点的指针next：

static final class Node<K,V> {
        
            final K key;     // 键
            V val;           // 值
            Node<K,V> next;  // 指向下一个节点的指针
            Node(K key, V value, Node<K,V> next) {
        
                this.key = key;
                this.val = value;
                this.next = next;
            }
        }

**Index**节点代表了跳表的层级，包含了当前节点node、下一层down、当前层的下一个节点right：

static final class Index<K,V> {
        
            final Node<K,V> node;   // 当前节点
            final Index<K,V> down;  // 下一层
            Index<K,V> right;       // 当前层的下一个节点
            Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
        
                this.node = node;
                this.down = down;
                this.right = right;
            }
        }

如图所示，Node节点将真实的数据按顺序链接起来，Index节点组成了跳表中多层次的索引结构。  
![在这里插入图片描述][b8a15d378cdf43afbb540a81c556ff7a.png]

讲完基础，来扯为啥它能保证线程安全。基本上都是通过自旋(for死循环)+CAS来保证我能修改到这个节点的值。

### ConcurrentSkipListSet ###

它就是维护一个ConcurrentSkipListMap，然后保证唯一key实现的。。。

### CopyOnWriteArrayList ###

核心成员lock跟array：

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        
        private static final long serialVersionUID = 8673264195747942595L;
    
        /**
         * The lock protecting all mutators.  (We have a mild preference
         * for builtin monitors over ReentrantLock when either will do.)
         */
        final transient Object lock = new Object();
    
        /** The array, accessed only via getArray/setArray. */
        private transient volatile Object[] array;
     }

保证线程安全就是在修改元素时，用 synchronized(lock)来锁住，然后替换新的array。比如添加元素：

public boolean add(E e) {
        
            synchronized (lock) {
        
                Object[] es = getArray();
                int len = es.length;
                es = Arrays.copyOf(es, len + 1);
                es[len] = e;
                setArray(es);
                return true;
            }
        }

这样的话在get的时候就永远是线程安全了。根据这种性质，用于读多写少的场景。

### CopyOnWriteArraySet ###

跟ConcurrentSkipListSet一个尿性，维护CopyOnWriteArrayList，保证添加的元素唯一性即可，比如addIfAbsent。

[Link 1]: https://blog.csdn.net/u013872857/article/details/108762345
[Link 2]: https://blog.csdn.net/hbtj_1216/article/details/114228578
[5c3a52d363d4429faeb8622e2cc17ca3.png]: https://img-blog.csdnimg.cn/5c3a52d363d4429faeb8622e2cc17ca3.png
[b8a15d378cdf43afbb540a81c556ff7a.png]: https://img-blog.csdnimg.cn/b8a15d378cdf43afbb540a81c556ff7a.png