Java之juc旅途-collection(七)

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

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

下面逐一解析。

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

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

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

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

在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 是基于链表的无限双端队列，线程安全，不允许 null 元素。
ConcurrentLinkedDeque 内部通过 CAS 来实现线程同步，一般来说，如果需要使用线程安全的双端队列，那么推荐使用该类。
由于双端队列的特性，该类同样可以当做栈来使用，所以如果需要在并发环境下使用栈，也可以使用该类。


在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 newNode = newNode(Objects.requireNonNull(e));

        restartFromTail:
        for (;;)
            for (Node 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
                }
            }
    }

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

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

跳表（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，因此找到了目标节点，结束查询。

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

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

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

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

如图所示，Node节点将真实的数据按顺序链接起来，Index节点组成了跳表中多层次的索引结构。

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

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

核心成员lock跟array：

public class CopyOnWriteArrayList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    
    final transient Object lock = new Object();

    
    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的时候就永远是线程安全了。根据这种性质，用于读多写少的场景。

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