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 和同步容器的性能:
下面这篇文章简单描述了 CopyOnWriteArrayList 的使用:
因为 网友总结的优缺点是:
缺点:
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://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 帝乡, 在没有额外同步的情况下, 可以被多个线程并发访问, 但是任何线程都不能修改它
线程安全对象: 一个线程安全的对象或者容器, 在内部通过同步机制来保障线程安全, 多以其他线程无需额外的同步就可以通过公共接口随意访问他
被守护对象: 被守护对象只能通过获取特定的锁来访问.
不好意思 虎头蛇尾了. 实在扛不住了
来源: https://www.cnblogs.com/aihuxi/p/9683805.html