高并发第八弹:J.U.C起航(java.util.concurrent)
java.util.concurrent是JDK自带的一个并发的包主要分为以下5部分：
- 并发工具类(tools)
- 显示锁(locks)
- 原子变量类(aotmic)
- 并发集合(collections)
- Executor线程执行器
我们今天就说说 并发集合,除开 Queue,放在线程池的时候讲
先介绍以下 CopyOnWrite:
Copy-On-Write简称COW，是一种用于程序设计中的优化策略。其基本思路是，从一开始大家都在共享同一个内容，当某个人想要修改这个内容的时候，才会真正把内容Copy出去形成一个新的内容然后再改，这是一种延时懒惰策略。从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用，可以在非常多的并发场景中使用到 .
CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8673264195747942595L; /** The lock protecting all mutators */ final transient ReentrantLock lock = new ReentrantLock(); /** The array, accessed only via getArray/setArray. */ private transient volatile Object[] array; ............................
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); //复制当前数组并且扩容+1 newElements[len] = e; setArray(newElements);//将原来的数组指向新的数组 return true; } finally { lock.unlock(); } }
下面这篇文章验证了CopyOnWriteArrayList和同步容器的性能：
http://blog.csdn.net/wind5shy/article/details/5396887
下面这篇文章简单描述了CopyOnWriteArrayList的使用：
http://blog.csdn.net/imzoer/article/details/9751591
因为 网友总结的优缺点是:
-
缺点：
1.写操作时复制消耗内存，如果元素比较多时候，容易导致young gc 和full gc。
2.不能用于实时读的场景.由于复制和add操作等需要时间，故读取时可能读到旧值。
能做到最终一致性，但无法满足实时性的要求，更适合读多写少的场景。
如果无法知道数组有多大，或者add,set操作有多少，慎用此类,在大量的复制副本的过程中很容易出错。 -
设计思想：
1.读写分离
2.最终一致性
3.使用时另外开辟空间，防止并发冲突
这个还真是主要是针对 读多的条件.毕竟写一个就要开辟一个空间.太耗资源了.其实还是建议用手动的方式来控制集合的并发.
1. ArrayList –> CopyOnWriteArrayList
它相当于线程安全的ArrayList。和ArrayList一样，它是个可变数组；但是和ArrayList不同的时，它具有以下特性：
1. 它最适合于具有以下特征的应用程序：List 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
2. 它是线程安全的。
3. 因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大。
4. 迭代器支持hasNext(), next()等不可变操作，但不支持可变 remove()等操作。
5. 使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。
2. HashSet –> CopyOnWriteArraySet
它是线程安全的无序的集合，可以将它理解成线程安全的HashSet。有意思的是，CopyOnWriteArraySet和HashSet虽然都继承于共同的父类AbstractSet；但是，HashSet是通过“散列表(HashMap)”实现的，而CopyOnWriteArraySet则是通过“动态数组(CopyOnWriteArrayList)”实现的，并不是散列表。
和CopyOnWriteArrayList类似，CopyOnWriteArraySet具有以下特性：
1. 它最适合于具有以下特征的应用程序：Set 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
2. 它是线程安全的。
3. 因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大。
4. 迭代器支持hasNext(), next()等不可变操作，但不支持可变 remove()等 操作。
5. 使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。
SkipList 跳表:先介绍这个吧
介绍的很详细 https://blog.csdn.net/sunxianghuang/article/details/52221913
更优秀的 :https://www.cnblogs.com/skywang12345/p/3498556.html
总结起来就是:
传统意义的单链表是一个线性结构，向有序的链表中插入一个节点需要O(n)的时间，查找操作需要O(n)的时间
跳表查找的复杂度为O(n/2)。跳跃表其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。
先以数据“7,14,21,32,37,71,85”序列为例，来对跳表进行简单说明。
跳表分为许多层(level)，每一层都可以看作是数据的索引，这些索引的意义就是加快跳表查找数据速度。每一层的数据都是有序的，上一层数据是下一层数据的子集，并且第一层(level 1)包含了全部的数据；层次越高，跳跃性越大，包含的数据越少。
跳表包含一个表头，它查找数据时，是从上往下，从左往右进行查找。现在“需要找出值为32的节点”为例，来对比说明跳表和普遍的链表。
情况1：链表中查找“32”节点
路径如下图1-02所示：
需要4步(红色部分表示路径)。
情况2：跳表中查找“32”节点
路径如下图1-03所示：
忽略索引垂直线路上路径的情况下，只需要2步(红色部分表示路径)。
先以数据“7,14,21,32,37,71,85”序列为例，来对跳表进行简单说明。
跳表分为许多层(level)，每一层都可以看作是数据的索引，这些索引的意义就是加快跳表查找数据速度。每一层的数据都是有序的，上一层数据是下一层数据的子集，并且第一层(level 1)包含了全部的数据；层次越高，跳跃性越大，包含的数据越少。
跳表包含一个表头，它查找数据时，是从上往下，从左往右进行查找。现在“需要找出值为32的节点”为例，来对比说明跳表和普遍的链表。
情况1：链表中查找“32”节点
路径如下图1-02所示：
需要4步(红色部分表示路径)。
情况2：跳表中查找“32”节点
路径如下图1-03所示：
忽略索引垂直线路上路径的情况下，只需要2步(红色部分表示路径)。
3. TreeMap –> ConcurrentSkipListMap
下面说说Java中ConcurrentSkipListMap的数据结构。
(01) ConcurrentSkipListMap继承于AbstractMap类，也就意味着它是一个哈希表。
(02) Index是ConcurrentSkipListMap的内部类，它与“跳表中的索引相对应”。HeadIndex继承于Index，ConcurrentSkipListMap中含有一个HeadIndex的对象head，head是“跳表的表头”。
(03) Index是跳表中的索引，它包含“右索引的指针(right)”，“下索引的指针(down)”和“哈希表节点node”。node是Node的对象，Node也是ConcurrentSkipListMap中的内部类。
/** * Special value used to identify base-level header */ private static final Object BASE_HEADER = new Object(); /** * 跳表的最顶层索引 */ private transient volatile HeadIndex<K,V> head; /** * * 比较器用于维护此映射中的顺序，或者如果使用自然排序，则为空。（非私有的，以 * 简化嵌套类中的访问）。 * */ final Comparator<? super K> comparator; /** Lazily initialized key set */ //懒惰初始化密钥集 private transient KeySet<K> keySet; /** Lazily initialized entry set */ private transient EntrySet<K,V> entrySet; /** Lazily initialized values collection */ private transient Values<V> values; /** Lazily initialized descending key set */
源码我也没精力去详勘了.就总结一下
4. TreeSet –> ConcurrentSkipListSet
(01) ConcurrentSkipListSet继承于AbstractSet。因此，它本质上是一个集合。
(02) ConcurrentSkipListSet实现了NavigableSet接口。因此，ConcurrentSkipListSet是一个有序的集合。
(03) ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的。它包含一个ConcurrentNavigableMap对象m，而m对象实际上是ConcurrentNavigableMap的实现类ConcurrentSkipListMap的实例。ConcurrentSkipListMap中的元素是key-value键值对；而ConcurrentSkipListSet是集合，它只用到了ConcurrentSkipListMap中的key！
(4)同其他set集合，是基于map集合的（基于ConcurrentSkipListMap），在多线程环境下，里面的contains、add、remove操作都是线程安全的。
(5)多个线程可以安全的并发的执行插入、移除、和访问操作。但是对于批量操作addAll、removeAll、retainAll和containsAll并不能保证以原子方式执行，原因是addAll、removeAll、retainAll底层调用的还是 contains、add、remove方法，只能保证每一次的执行是原子性的，代表在单一执行操纵时不会被打断，但是不能保证每一次批量操作都不会被打断。在使用批量操作时，还是需要手动加上同步操作的。
(6)不允许使用null元素的，它无法可靠的将参数及返回值与不存在的元素区分开来。
5. HashMap –> ConcurrentHashMap
- 不允许空值，在实际的应用中除了少数的插入操作和删除操作外，绝大多数我们使用map都是读取操作。而且读操作大多数都是成功的。基于这个前提，它针对读操作做了大量的优化。因此这个类在高并发环境下有特别好的表现。
- ConcurrentHashMap作为Concurrent一族，其有着高效地并发操作，相比Hashtable的笨重，ConcurrentHashMap则更胜一筹了。
- 在1.8版本以前，ConcurrentHashMap采用分段锁的概念，使锁更加细化，但是1.8已经改变了这种思路，而是利用CAS+Synchronized来保证并发更新的安全，当然底层采用数组+链表+红黑树的存储结构。
- 源码分析：推荐参考chenssy的博文：J.U.C之Java并发容器：ConcurrentHashMap
安全共享对象策略
- 线程限制：一个被线程限制的对象，由线程独占，并且只能被占有它的线程修改
- 共享只读：一个共享只读的U帝乡，在没有额外同步的情况下，可以被多个线程并发访问，但是任何线程都不能修改它
- 线程安全对象：一个线程安全的对象或者容器，在内部通过同步机制来保障线程安全，多以其他线程无需额外的同步就可以通过公共接口随意访问他
- 被守护对象：被守护对象只能通过获取特定的锁来访问。
不好意思 虎头蛇尾了.实在扛不住了