容器一览
- ConcurrentHashMap：这是一个高效的并发HashMap。你可以把它理解为一个线程安全的HashMap。
- CopyOnWriteArrayList：这是一个List，从名字看就知道它和Array List是一族的。在读多写少的场合，这个List的性能非常好，远远优于Vector。
- ConcurrentLinkedQueue：高效的并发队列，使用链表实现。可以看作一个线程安全的LinkedList。
- BlockingQueue：这是一个接口，JDK内部通过链表、数组等方式实现了这个接口。表示阻塞队列，非常适合作为数据共享的通道。
- ConcurrentSkipListMap：跳表的实现。这是一个Map，使用跳表的数据结构进行快速查找
1. 使用synchronized包装类
我们平时使用的容器都是线程不安全的，比如ArrayList，HashMap等，那么，让他们变得线程安全最简单的办法就是添加一个synchronized锁，那么在容器工具类Collections中提供了一些方法。
这里我们拿Collections.synchronizedMap()方法举例，Collections.synchronizedMap()方法会生成一个名为SynchronizedMap的Map。它使用委托，将自己所有Map相关的功能交给传入的HashMap实现，而自己则主要负责保证线程安全。
我们先看看它的内部结构
我们可以看到这是一个私有的内部类，并且内部维护了一个Map，然后定义了一个mutex，备注写着用于同步的对象。那这个mutex到底有什么用呢？我们来看看map.get()方法，看看其实现就明白了
可以看到这个mutex就是一个用于同步的对象实例，它的作用就是让其他线程进不去。那么看了原理以后，我们应该就明白了
2. ConcurrentHashMap
该HashMap是优化锁的一种典型方案：细化锁的粒度达到优化的目的。我们知道传统的HashMap并不是线程安全的，而我们让他变得线程安全最简答的方式就是给这个map加上一把锁，通过锁的方式达到线程安全。但是，这带来一个问题就是让这个结构的速度变得异常缓慢。那么，如何优化呢？
jdk给的方案是通过将map切分成16个小段（segment），这16个小段是有序排列，然后给这16个小段分别加上锁，如果某一段上锁不会影响其他部分的读写操作。
3. 读写队列：ConcurrentLinkedQueue类
JDK提供了该队列，使用链表这种数据结构作为实现方式，性能是在这些并发队列中最好的。这么强大的工具自然离不开内部复杂的实现方式，这次，我们就来了解一下该结构的实现方式
首先是链表，那么链表的组成单元就是Node节点
可以看到这也是一个私有内部类，其中item是用来表示目标元素的。比如，当列表中存放String时，item就是String类型。字段next表示当前Node的下一个元素，这样每个Node就能环环相扣，串在一起了
分析完了结构，那我们再看看如何实现高并发的，要分析这个，我们先看看这个链表的内部操作
看到这里的实现UNSAFE其实是一个本地方法，提供的就是我们耳熟能详的CAS策略。CAS策略就是一种通过不断轮询的方式去操作对象的策略，如果操作成功则返回成功，失败了就返回失败，并不断去尝试修改，所有的线程都这么做以后，总有修改成功的。这样做的话就不会卡住线程，而是会立马返回结果，不至于卡死线程。
了解了CAS策略以后，这里再谈谈这些方法，方法casItem()表示设置当前Node的item值。它需要两个参数，第一个参数为期望值，第二个参数为设置目标值。当当前值等于cmp期望值时，就会将目标设置为val。同样casNext()方法也是类似的，但是它用于设置next字段，而不是item字段。
方法我们知道这是在做什么以后，我们再回到队列这种结构，队列有head和tail表示队列的头和尾，这个标识是服务于队列这种结构的，队列是从尾进从头出的结构。但ConcurrentLinkedQueue类的内部实现非常复杂，它允许在运行时链表处于多个不同的状态。以tail为例，一般来说，我们期望tail总是为链表的末尾，但实际上，tail的更新并不是及时的，可能会产生拖延现象。下图显示了插入时tail的更新情况，可以看到tail的更新会产生滞后，并且每次更新会跳跃两个元素。
我们看看这个offer方法，队列通过offer方法将元素加入队列
public boolean offer(E e) {
checkNotNull(e);
// 创建新节点
final Node<E> newNode = new Node<E>(e);
// 去掉循环条件不断空转
for (Node<E> t = tail, p = t;;) {
Node<E> q = p.next;
if (q == null) {
// p is last node
if (p.casNext(null, newNode)) {
// Successful CAS is the linearization point
// for e to become an element of this queue,
// and for newNode to become "live".
if (p != t) // hop two nodes at a time
casTail(t, newNode); // Failure is OK.
return true;
}
// Lost CAS race to another thread; re-read next
}
else if (p == q)
// We have fallen off list. If tail is unchanged, it
// will also be off-list, in which case we need to
// jump to head, from which all live nodes are always
// reachable. Else the new tail is a better bet.
p = (t != (t = tail)) ? t : head;
else
// Check for tail updates after two hops.
p = (p != t && t != (t = tail)) ? t : q;
}
}
通过这个策略，我们就能够看到offer是如何保证tail在最后一个位置上的。
对于代码中的p == q的操作，这里要解释一下为什么有这种情况，这种情况是由于遇到了哨兵（sentinel）节点导致的。所谓哨兵节点，就是next指向自己的节点。这种节点在队列中的存在价值不大，主要表示要删除的节点，或者空节点。当遇到哨兵节点时，由于无法通过next取得后续的节点，因此很可能直接返回head，期望通过从链表头部开始遍历，进一步找到链表末尾。一旦在执行过程中发生tail被其他线程修改的情况，则进行一次“打赌”，使用新的tail作为链表末尾（这样就避免了重新查找tail的开销）。
再重点看一下这个代码
p = (t != (t = tail)) ? t : head;
这句代码虽然只有短短一行，但是包含的信息比较多。首先“!=”并不是原子操作，它是可以被中断的。也就是说，在执行“!=”时，程序会先取得t的值，再执行t=tail，并取得新的t的值，然后比较这两个值是否相等。在单线程时，t!=t这种语句显然不会成立。但是在并发环境中，有可能在获得左边的t值后，右边的t值被其他线程修改。这样，t!=t就可能成立了，这里就是这种情况。如果在比较过程中，tail被其他线程修改，当它再次赋值给t时，就会导致等式左边的t和右边的t不同。如果两个t不相同，表示tail在中途被其他线程篡改。这时，我们就可以用新的tail作为链表末尾，也就是这里等式右边的t。但如果tail没有被修改，则返回head，要求从头部开始，重新查找尾部。
4. 高效读取：CopyOnWriteArrayList类
在很多应用场景中，读操作可能会远远大于写操作。比如，有些系统级别的信息，往往只需要加载或者修改很少的次数，但是会被系统内所有模块频繁访问。对于这种场景，我们最希望看到的就是读操作可以尽可能地快，而写即使慢一些也没有太大关系
多线程访问一个资源时其实并不总需要锁，比如读操作。我们都知道锁出现的本质是防止多个线程同时写入同一个资源，导致资源更新不过来，最终引发逻辑问题。换句话说，写操作才是锁出现的意义，如果一个线程只是单纯的想读某个资源，那么没必要上锁，多个线程甚至可以同一时间操作一个资源。
根据读写锁（ReadWriteLock）的思想，那这里我们就将这两个操作分别给予两个锁，读锁和写锁。读锁于读锁之间并不冲突，换句话说，两个读操作能够同时进行。读锁于写锁，写锁于写锁是相互冲突的。也就说，当有某个写操作进行时，读操作不能进行，或另一个写操作也不能进行。同理，当某个线程在读时，写操作也不能进行。
为了将读取的性能发挥到极致，JDK中提供了CopyOnWriteArrayList类。对它来说，读取是完全不用加锁的，并且更好的消息是：写入也不会阻塞读取操作。只有写入和写入之间需要进行同步等待。这样，读操作的性能就会大幅度提升。它是怎么做的呢？
翻译一下类名就知道了大概的意思：写时复制。就是在执行写操作的时候通过复制的方式备份一份List用于读操作，将读写分在两个List上面，就解决了写时不能读的问题。
下图是读操作，我们可以看到读操作是没有任何锁的。
public E get(int index) {
return get(getArray(), index);
}
再看看写操作
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();
}
}
5. 数据共享通道：BlockingQueue
之前，我们介绍了ConcurrentLinkedQueue这个高性能的队列，甚至我们也断言这个队列是性能最好的，那么，为什么我们还需要这个队列呢？其实，我们再看看这个队列的命名：阻塞队列，换句话说，该队列是设计时就考虑了阻塞这个特征。
什么时候需要阻塞队列呢？我们应该都听过生产-消费者模式。生产-消费者模式能够用于系统间的消息共享，生产者用于生产消息，消费者用于消费消息。那么这个阻塞队列就起到存放消息的作用。
至于这个模式有什么用，我们可以举个例子，我们小时候应该都订过牛奶，送奶的人会将奶装进一个约定的奶箱里，而我们会在我们有空的时候去奶箱中取走我们的牛奶。这样做的好处就是我们不用直接与送奶者接触，比如送奶者急着送下家，而你这时还没起床，它不可能一直等你起床，这样就是利用中间的层起到两个系统间的解耦。
那说回到这个队列，该队列其实不是一个具体实现，而是一个接口，下图可以看到基于该接口的一些具体实现
以ArrayBolckingQueue队列为例子，该队列内部其实有一个对象数组
向队列中压入元素可以使用offer()方法和put()方法。对于offer()方法，如果当前队列已经满了，它就会立即返回false。如果没有满，则执行正常的入队操作。所以，我们不讨论这个方法。现在，我们需要关注的是put()方法。put()方法也是将元素压入队列末尾。但如果队列满了，它会一直等待，直到队列中有空闲的位置。
从队列中弹出元素可以使用poll()方法和take()方法。它们都从队列的头部获得一个元素。不同之处在于：如果队列为空，那么poll()方法会直接返回null，而take()方法会等待，直到队列内有可用元素。
/**
* Inserts the specified element at the tail of this queue, waiting
* for space to become available if the queue is full.
*
* @throws InterruptedException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public void put(E e) throws InterruptedException {
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
// 可以看到这里当队列满了以后就会一直阻塞，直到能够容纳一个元素
while (count == items.length)
notFull.await();
enqueue(e);
} finally {
lock.unlock();
}
}
private void enqueue(E x) {
// assert lock.getHoldCount() == 1;
// assert items[putIndex] == null;
final Object[] items = this.items;
items[putIndex] = x;
//putIndex表示队头，对头加满了以后重新置为0
if (++putIndex == items.length)
putIndex = 0;
count++;
notEmpty.signal();
}
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
// 这里也设置了阻塞，当为空时也阻塞，直到有内容
while (count == 0)
notEmpty.await();
return dequeue();
} finally {
lock.unlock();
}
}
private E dequeue() {
// assert lock.getHoldCount() == 1;
// assert items[takeIndex] != null;
final Object[] items = this.items;
@SuppressWarnings("unchecked")
E x = (E) items[takeIndex];
items[takeIndex] = null;
// takeIndex表示队尾指针，队尾到数组底了以后就直接置为0
if (++takeIndex == items.length)
takeIndex = 0;
count--;
if (itrs != null)
itrs.elementDequeued();
notFull.signal();
return x;
}
我们看看这个notFull和农田Empty都是什么？
/** Condition for waiting takes */
private final Condition notEmpty;
/** Condition for waiting puts */
private final Condition notFull;
其实这是可重入锁派生的condition。notEmpty表示此时不为空，notFull表示此时不为满。
6. 随机数据结构：跳表——(SkipList)
我们知道二叉查找树这样一种数据结构，跳表的形式和他有点像，跳表也是通过没一层的排序达到快速查找的目的。下图表示的是跳表的结构
那么，二叉查找树与跳表这种结构有什么在性能上的区别呢？主要区别在于：二叉查找树在执行插入或者删除操作的时候要对整个结构进行上锁，而跳表这种数据结构只需要通过局部的调整就能够达到插入或删除的目的，因此，就不需要通过锁住全表的方式进行增删操作，因此能够提高它的性能。
值得注意的是，这样一种快速查询的结构，jdk经常使用这种结构来优化map
6.1 聊聊跳表这种结构
跳表的另外一个特点是随机算法。跳表的本质是同时维护了多个链表，并且链表是分层的。
底层的链表维护了跳表内所有的元素，每上面一层链表都是下面一层链表的子集，一个元素插入哪些层是完全随机的。因此，如果运气不好，你可能会得到一个性能很糟糕的结构。但是在实际工作中，它的表现是非常好的。
