并发容器原理

1. CopyOnWriteArrayList

   • 在更新数据时，会新建一个数组，并将更新后的数组拷贝到新建的数组中，最后再将该数组赋值给 volatile数组，并且在操作数据时使用 互斥锁 保护数据线程的安全。
   • 之所以不直接修改数据，而是采用拷贝修改的方式，是为了在读取数据的时候不加锁

     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();
     }
     }

2. CopyOnWriteArraySet

   • CopyOnWriteArraySet是通过CopyOnWriteArrayList实现的。

3. ConcurrentHashMap

   • 实现⽅式是“数组+链表”，这种⽅式被称为“拉链法”，并且是线程安全的。
   • 如果头节点是Node类型，则尾随它的就是⼀个普通的链表；如果头节点是TreeNode类型，它的后⾯就是⼀颗红⿊树，TreeNode是Node的⼦类。
   • 链表和红⿊树之间可以相互转换：初始的时候是链表，当链表中的元素超过某个阈值时，把链表转换成红⿊树；反之，当红⿊树中的元素个数⼩于某个阈值时，再转换为链表。
   • 使用的分段锁，将容器的数据分段存储。每一段数据分配一个Segment（锁），当线程占用其中一个Segment时，其他线程可正常访问其他段数据。

1. ConcurrentSkipListMap

   • 跳表（Skip List），它是平衡数的一种替代的数据结构，但是和红黑树不同的是，跳表对于数的平衡的实现是基于一种随机化的算法的，这样就是说跳表的插入和删除的工作是比较简单的。

2. ConcurrentSkipListSet

   • ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的

3. ConcurrentLinkedQueue

   • 是一个基于链接节点的无界限安全队列。
   • 队列按照先进先出（FIFO）的原则对元素进行排序。
   • 不可以放置null元素。