Java提供的并发容器基本都在java.util.concurrent包中。比较常用的有ConcurrentHashMap、ConcurrentSkipListMap、CopyOnWriteArrayList、ConcurrentLinkedQueue、BlockingQueue等。
1、线程安全的HashMap
HashMap是非线程安全的，在并发环境中会带来很多诡异的问题。
在多线程中使用线程安全的HashMap方式：
1）使用Collections.synchronizedMap()方法包装HashMap
SynchronizedMap类实现了Map，通过mutex对象实现对m互斥操作。其他所有相关的操作都有用到mutex对象进行同步，从而实现线程安全。这种方式在多线程环境中的性能并不好，所有对Map的操作都需要获取mutex对象锁，导致操作出现等待现象。
2）使用ConcurrentHashMap，性能更高。
2、线程安全的List
Java中ArrayList和Vector都是使用数组作为内部实现的，Vector是线程安全的，ArrayList不是。LinkedList使用链表的数据结构实现了List，但它并非线程安全的，也可以通过Collections.synchronizedList()方式包装List。
3、高效读写队列ConcurrentLinkedQueue
JDK中提供了一个支持高并发的队列ConcurrentLinkedQueue，它使用链表结构实现。item表示目标元素，next表示当前Node的下一个元素。
对Node操作使用了CAS操作，casItem()方法表示设置当前Node的item值，它有2个参数，第一个表示期望值，第二个为设置目标值。若当前值等于期望值cmp时，就会将目标设为val。casNext()也类似，它用来设置next字段。
head表示链表的头部，tail表示链表的尾部。head永远不会为null，通过head和succ()方法能完整遍历整个链表。
offer()方法中无任何锁操作，线程安全由CAS和队列算法来保证。方法的核心是for循环，此循环没有出口，直到尝试成功为止。
当首次加入元素时，由于队列为空，因此p.next=null，然后将p的next节点赋值为newNode，即将新的元素加入到队列中。此时p==t，如果casNext()执行成功，查询直接返回true。如果失败则再进行一次循环，直到成功。因此增加一个元素时，tail并不会被更新。
当第二次增加元素时，由于t还在head的位置上，p.next指向实际的第一个元素，因此q != null，表示q不是最后一个节点。由于往队列中增加元素需要最后一个节点的位置，因此需要循环查找最后一个节点。获得最后一个节点后，p实际上指向链表的第一个元素，而它的next=null，然后p更新自己的next，让它指向新加入的节点。如果成功则p != t，然后更新t所在位置，将t移动到链表最后。
如果p== q，是由于遇到了哨兵（sentinel）节点导致的，哨兵节点就是next指向自己的节点，主要表示要删除的节点或空节点。当遇到哨兵节点时，无法通过next获取后续节点，可能会直接返回head，并期望通过从链表头部开始遍历，再查找到链表末尾。
p = (t != (t =tail)) ? t :head;
在执行 != 时，线程会先取得t的值，再执行t = tail，并取得新t的值，然后比较着两个值是否相等。在单线程下t != t 并不会成立，但在并发下就有可能存在，如在获得左边的t值时，右边的t值已被其他线程修改。如果在比较过程中，tail被其他线程修改，当它再次赋值给t时，会导致等式左右两边的t不同。如果两个t不同，表示tail在中途被其他线程修改。此时就可以用新的tail作为链表末尾，即等式右边的t。如果tail没有被修改，则返回head，要求从头部开始重新查找尾部。
哨兵节点产生：当队列中只有一个节点时。
poll()方法用于弹出队列内的元素。
在updateHead()方法中，将p作为新的链表头部，原有的head被设置为哨兵（通过lazySetNext(h)方法实现）。由于原有的head和tail实际上是同一元素，因此再次用offer()添加元素时，就会遇到这个哨兵tail。
4、高效读取：CopyOnWriteArrayList
在大多数情况下，读操作会远远大于写操作，读并不会修改原数据，因此并没有必要加锁，读是线程安全的。当写操作时读必须等待，否则可能读到不一致的数据，如果正在读时也不能进行写入。
CopyOnWriteArrayList类的读是不加锁的，写入也不会阻塞读操作，只有在写写的时候才进行同步等待。其实现原理是：当List需要修改时并不是修改的原内容，而是对原有的数据进行一份复制，将修改的数据写入副本，写完后再将修改后的副本替换原有的数据。
注意：读操作代码没有任何同步控制和锁操作，原因是内部数组array不会发生修改，只会被另外array替换，可以保证数据安全。
写操作使用了锁，Arrays.copyOf(elements, len +1)对内部元素进行了完整复制，生成一个新的数组newElements，然后将新的元素加入newElements中，setArray(newElements)使用新的数组替换原有数组，修改就完成了。此过程不会影响读操作，修改完成后，读线程可以立刻知道这个修改（因为array是volatile的）。
5、数据共享通道：BlockingQueue
BlockingQueue是一个接口，它适合作为数据共享的通道，它有如下实现类：
ArrayBlockingQueue：
它的内部元素都放在一个对象数组中：final Object[] items;
向队列中压入元素可以使用offer()和put()方法。offer()：如果当前队列已满，会立即返回false。如果未满，则执行入队操作。put()：也是将元素压入到队列末尾，如果队列已满，它会一直等待，直到队列中有空闲的位置。
从队列中弹出元素可以使用poll()和take()方法，它们都是从队列头部获取一个元素。区别是如果队列为空时poll()会直接返回null，take()会等待，直到队列内有可用元素。
当执行put()时，如果队列为空，则让当前线程在notEmpty上等待，新元素入队时，则进行一次notEmpty上的通知。当队列中有新元素时，线程会得到一个通知。当新元素进入队列后，需要通知等待在notEmpty上的线程，让它们继续工作。
对于put()操作也类似，当队列满时需要让压入线程等待，当有元素从队列中移走出现空位时，也需要通知等待入队的线程。
6、随机数据结构：跳表SkipList
跳表是一种可以用来快速查找的数据结构，类似于平衡树。区别是对于平衡树的插入和输出可能导致平衡树进行一次全局的调整，而跳表只需要对整个数据结构的局部进行操作。好处是在高并发情况下，需要一个全局锁来保证整个平衡树的线程安全，对于跳表只需要部分锁即可，性能更好。
跳表的查询时间复杂度为O(log n)。它采用随机算法，本质是同时维护了多个链表，并且链表是分层的。最底层的链表维护了跳表内的所有元素，每上面一层链表都是下面一层的子集，一个元素插入哪些层是完全随机的。
跳表内的所有元素都是排序的，查找时，可以从顶级链表开始，一旦发现被查找的元素大于当前链表中的取值，就会转入下一层的链表继续找，在查找过程中搜索是跳跃式的。跳表是一种使用空间换时间的算法。
使用跳表实现Map和使用哈希算法实现Map的不同之处是：哈希并不会保存元素的顺序，而跳表内所有元素都是排序的，在对跳表进行遍历时，将会得到一个有序的结果。
ConcurrentSkipListMap是使用跳表数据结构实现的。
跳表的内部数据结构组成：Node和Index。
Node：一个Node表示一个节点，里面含有key、value，每个Node还会指向下一个Node，即元素next。
casValue()方法用来设置value的值，casNext()方法用来设置next字段。
Index：表示索引，它内部包装了Node，同时增加了两个向下的引用和向右的引用。整个跳表就是根据Index进行全网组织的。
对于每一层的表头，还需要记录当前处于那一层，因此还需要一个HeadIndex的数据结构，表示链表头部的第一个Index，它继承于Index。
总结：对跳表的所有操作，就是组织好这些Index之间的连接关系。
--参考文献《实战Java高并发程序设计》
