CopyOnWriteArrayList是如何保证线程安全的

　　本文已收录到AndroidFamily，技术和职场问题，请关注公众号〔彭旭锐〕提问。前言
　　大家好，我是小彭。
　　在上一篇文章里，我们聊到了ArrayList的线程安全问题，其中提到了CopyOnWriteArrayList的解决方法。那么CopyOnWriteArrayList是如何解决线程安全问题的，背后的设计思想是什么，今天我们就围绕这些问题展开。
　　本文源码基于Java8CopyOnWriteArrayList。
　　小彭的Android交流群02群已经建立啦，欢迎加入
　　思维导图：
　　1。回顾ArrayList
　　ArrayList是基于数组实现的动态数据，是线程不安全的。例如，我们在遍历ArrayList的时候，如果其他线程并发修改数组（当然也不一定是被其他线程修改），在迭代器中就会触发failfast机制，抛出ConcurrentModificationException异常。
　　示例程序ListStringlistnewArrayList（）；list。add（xiao）；list。add（peng）；list。add（。）；Iteratoriteratorlist。iterator（）；while（iterator。hasNext（））｛可能抛出ConcurrentModificationException异常iterator。next（）；｝
　　要实现线程安全有3种方式：方法1使用Vector容器：Vector是线程安全版本的数组容器，它会在所有方法上增加synchronized关键字（过时，了解即可）；方法2使用Collections。synchronizedList包装类方法3使用CopyOnWriteArrayList容器
　　Collections。synchronizedList包装类的原理很简单，就是使用synchronized加锁，源码摘要如下：
　　Collections。javapublicstaticTListTsynchronizedList（ListTlist）｛return（listinstanceofRandomAccess？newSynchronizedRandomAccessList（list）：newSynchronizedList（list））；｝使用synchronized实现线程安全staticclassSynchronizedListEextendsSynchronizedCollectionEimplementsListE｛finalListElist；publicbooleanequals（Objecto）｛if（thiso）returntrue；synchronized（mutex）｛returnlist。equals（o）；｝｝publicinthashCode（）｛synchronized（mutex）｛returnlist。hashCode（）；｝｝publicEget（intindex）｛synchronized（mutex）｛returnlist。get（index）；｝｝publicEset（intindex，Eelement）｛synchronized（mutex）｛returnlist。set（index，element）；｝｝publicvoidadd（intindex，Eelement）｛synchronized（mutex）｛list。add（index，element）；｝｝publicEremove（intindex）｛synchronized（mutex）｛returnlist。remove（index）；｝｝。。。｝
　　如果我们将ArrayList替换为CopyOnWriteArrayList，即使其他线程并发修改数组，也不会抛出ConcurrentModificationException异常，这是为什么呢？2。CopyOnWriteArrayList的特点
　　CopyOnWriteArrayList和ArrayList都是基于数组的动态数组，封装了操作数组时的搬运和扩容等逻辑。除此之外，CopyOnWriteArrayList还是用了基于加锁的读写分离和写时复制的方案解决线程安全问题：思想1读写分离（ReadWriteSplitting）：将对资源的读取和写入操作分离，使得读取和写入没有依赖，在读多写少的场景中能有效减少资源竞争；思想2写时复制（CopyOnWrite，COW）：在写入数据时，不直接在原数据上修改，而是复制一份新数据后写入到新数据，最后再替换到原数据的引用上。这个特性各有优缺点：优点1延迟处理：在没有写入操作时不会复制分配资源，能够避免瞬时的资源消耗。例如操作系统的fork操作也是一种写时复制的思想；优点2降低锁颗粒度：在写的过程中，读操作不会被影响，读操作也不需要加锁，锁的颗粒度从整个列表降低为写操作；缺点1弱数据一致性：在读的过程中，如果数据被其他线程修改，是无法实时感知到最新的数据变化的；缺点2有内存压力：在写操作中需要复制原数组，在复制的过程中内存会同时存在两个数组对象（只是引用，数组元素的对象还是只有一份），会带来内存占用和垃圾回收的压力。如果是写多读少的场景，就不适合。
　　所以，使用CopyOnWriteArrayList的场景一定要保证是读多写少且数据量不大的场景，而且在写入数据的时候，要做到批量操作。否则每个写入操作都会触发一次复制，想想就可怕。举2个例子：例如批量写入一组数据，要使用addAll方法批量写入；例如在做排序时，要先输出为ArrayList，在ArrayList上完成排序后再写回CopyOnWriteArrayList。3。CopyOnWriteArrayList源码分析
　　这一节，我们来分析CopyOnWriteArrayList中主要流程的源码。3。1CopyOnWriteArrayList的属性
　　ArrayList的属性很好理解，底层是一个Object数组，我要举手提问：疑问1：为什么array字段要使用volatile关键字？锁finaltransientReentrantLocklocknewReentrantLock（）；在Java11中，ReentrantLock被替换为synchronized锁Thelockprotectingallmutators。（WehaveamildpreferenceforbuiltinmonitorsoverReentrantLockwheneitherwilldo。）finaltransientObjectlocknewObject（）；底层数组疑问1：为什么array要使用volatile关键字？privatetransientvolatileObject〔〕array；
　　这个问题我们在分析源码的过程中回答。有了ArrayList的分析基础，疑问也变少了，CopyOnWriteArrayList真香。3。2CopyOnWriteArrayList的构造方法
　　构造器的源码不难，但小朋友总有太多的问号，举手提问：疑问2：为什么CopyOnWriteArrayList不提供初始化容量的构造器？
　　这是因为CopyOnWriteArrayList建议我们使用批量操作写入数据。如果提供了带初始化容量的构造器，意味着开发者预期会一个个地写入数据，这不符合CopyOnWriteArrayList的正确使用方法。所以，不提供这个构造器才是合理的。疑问3：为什么要把E〔〕类型的入参转化为Object〔〕类型？
　　如果不转化数组类型，那么在toArray（）方法返回的数组中插入Object类型对象时，会抛出ArrayStoreException。
　　提示：这个问题与奇怪分支的原因相同，具体分析可以看讲《Java面试题：ArrayList可以完全替代数组吗？》的文章中，这里不重复讲了。疑问2：为什么CopyOnWriteArrayList不提供预初始化容量的构造器？无参构造方法publicCopyOnWriteArrayList（）｛创建空数组setArray（newObject〔0〕）；｝带集合的构造方法publicCopyOnWriteArrayList（Collectionlt；？extendsEc）｛Object〔〕elements；if（c。getClass（）CopyOnWriteArrayList。class）elements（（CopyOnWriteArrayListlt；？）c）。getArray（）；else｛elementsc。toArray（）；这个奇怪的分支在ArrayList文章中分析过，去看看if（elements。getClass（）！Object〔〕。class）elementsArrays。copyOf（elements，elements。length，Object〔〕。class）；｝setArray（elements）；｝带数组的构造方法publicCopyOnWriteArrayList（E〔〕toCopyIn）｛疑问3：为什么要把E〔〕类型的入参转化为Object〔〕类型setArray（Arrays。copyOf（toCopyIn，toCopyIn。length，Object〔〕。class））；｝finalObject〔〕getArray（）｛returnarray；｝finalvoidsetArray（Object〔〕a）｛arraya；｝publicObject〔〕toArray（）｛Object〔〕elementsgetArray（）；returnArrays。copyOf（elements，elements。length）；｝3。3CopyOnWriteArrayList的写方法
　　我们将CopyOnWriteArrayList的添加、删除和修改方法统一为写方法，三种写方法的模板其实是一样的：1、在写入之前先获取对象的锁；2、复制新数组；3、在新数组上完成写入操作；4、将新数组设置为底层数组；5、释放对象的锁。
　　小朋友总是有太多问号，举手提问：疑问4：在添加方法中，为什么扩容只增大1容量，而ArrayList会增大1。5倍？
　　这还是因为CopyOnWriteArrayList建议我们使用批量操作写入数据。ArrayList额外扩容1。5倍是为了避免每次add都扩容，而CopyOnWriteArrayList并不建议一个个地添加数据，而是建议批量操作写入数据，例如addAll方法。所以，CopyOnWriteArrayList不额外扩容才是合理的。
　　另外，网上有观点看到CopyOnWriteArrayList没有限制数组最大容量，就说CopyOnWriteArrayList是无界的，没有容量限制。这显然太表面了。数组的长度限制是被虚拟机固化的，CopyOnWriteArrayList没有限制的原因是：它没有做额外扩容，而且不适合大数据的场景，所以没有限制的必要。
　　最后还剩下1个问题：疑问1：为什么array字段要使用volatile关键字？
　　volatile变量是Java轻量级的线程同步原语，volatile变量的读取和写入操作中会加入内存屏障，能够保证变量写入的内存可见性，保证一个线程的写入能够被另一个线程观察到。
　　添加方法在数组尾部添加元素publicbooleanadd（Ee）｛finalReentrantLocklockthis。lock；获取锁lock。lock（）；复制新数组Object〔〕elementsgetArray（）；intlenelements。length；疑问4：在添加方法中，为什么扩容只增大1容量，而ArrayList会增大1。5倍？Object〔〕newElementsArrays。copyOf（elements，len1容量1）；在新数组上添加元素newElements〔len〕e；设置新数组setArray（newElements）；释放锁lock。unlock（）；returntrue；｝在数组尾部添加元素publicvoidadd（intindex，Eelement）｛原理相同，省略。。。｝批量在数组尾部添加元素publicbooleanaddAll（Collectionlt；？extendsEc）｛原理相同，省略。。。｝
　　修改方法修改数组元素publicEset（intindex，Eelement）｛finalReentrantLocklockthis。lock；获取锁lock。lock（）；旧元素Object〔〕elementsgetArray（）；EoldValueget（elements，index）；if（oldValue！element）｛复制新数组intlenelements。length；Object〔〕newElementsArrays。copyOf（elements，len）；在新数组上添加元素newElements〔index〕element；设置新数组setArray（newElements）；｝else｛Notquiteanoop；ensuresvolatilewritesemanticssetArray（elements）；｝释放锁lock。unlock（）；返回旧数据returnoldValue；｝
　　删除方法删除数组元素publicEremove（intindex）｛finalReentrantLocklockthis。lock；获取锁lock。lock（）；Object〔〕elementsgetArray（）；intlenelements。length；旧元素EoldValueget（elements，index）；intnumMovedlenindex1；if（numMoved0）删除首位元素setArray（Arrays。copyOf（elements，len1））；else｛删除中间元素复制新数组Object〔〕newElementsnewObject〔len1〕；System。arraycopy（elements，0，newElements，0，index）；System。arraycopy（elements，index1，newElements，index，numMoved）；设置新数组setArray（newElements）；｝释放锁lock。unlock（）；返回旧数据returnoldValue；｝3。4CopyOnWriteArrayList的读取方法
　　可以看到读取方法并没有加锁。privateEget（Object〔〕a，intindex）｛return（E）a〔index〕；｝publicEget（intindex）｛returnget（getArray（），index）；｝publicbooleancontains（Objecto）｛Object〔〕elementsgetArray（）；returnindexOf（o，elements，0，elements。length）0；｝3。5CopyOnWriteArrayList的迭代器
　　CopyOnWriteArrayList的迭代器COWIterator是弱数据一致性的，所谓数据一致性问题讨论的是同一份数据在多个副本之间的一致性问题，你也可以理解为多个副本的状态一致性问题。例如内存与多核心Cache副本之间的一致性，或者数据在主从数据库之间的一致性。
　　提示：关于数据一致性和顺序一致性的区别，在小彭的计算机组成原理专栏讨论过《已经有MESI协议，为什么还需要volatile关键字？》，去看看。
　　为什么是弱的呢？这是因为COWIterator迭代器会持有CopyOnWriteArrayList底层数组的引用，而CopyOnWriteArrayList的写入操作是写入到新数组，因此COWIterator是无法感知到的，除非重新创建迭代器。
　　相较之下，ArrayList的迭代器是通过持有外部类引用的方式访问ArrayList的底层数组，因此在ArrayList上的写入操作会实时被迭代器观察到。
　　CopyOnWriteArrayList。java注意看：有static关键字，直接引用底层数组staticfinalclassCOWIteratorEimplementsListIteratorE｛底层数组privatefinalObject〔〕snapshot；privateintcursor；privateCOWIterator（Object〔〕elements，intinitialCursor）｛cursorinitialCursor；snapshotelements；｝｝
　　ArrayList。java注意看：没有static关键字，通过外部类引用来访问底层数组privateclassItrimplementsIteratorE｛intcursor；indexofnextelementtoreturnintlastRet1；indexoflastelementreturned；1ifnosuchintexpectedModCountmodCount；Itr（）｛｝。。。｝3。6CopyOnWriteArraySet的序列化过程
　　与ArrayList类似，CopyOnWriteArraySet也重写了JDK序列化的逻辑，只把elements数组中有效元素的部分序列化，而不会序列化整个数组。
　　同时，ReentrantLock对象是锁对象，序列化没有意义。在反序列化时，会通过resetLock（）设置一个新的ReentrantLock对象。序列化过程privatevoidwriteObject（java。io。ObjectOutputStreams）throwsjava。io。IOException｛s。defaultWriteObject（）；Object〔〕elementsgetArray（）；写入数组长度s。writeInt（elements。length）；写入有效元素for（Objectelement：elements）s。writeObject（element）；｝反序列化过程privatevoidreadObject（java。io。ObjectInputStreams）throwsjava。io。IOException，ClassNotFoundException｛s。defaultReadObject（）；设置ReentrantLock对象resetLock（）；读取数组长度intlens。readInt（）；SharedSecrets。getJavaOISAccess（）。checkArray（s，Object〔〕。class，len）；创建底层数组Object〔〕elementsnewObject〔len〕；读取数组对象for（inti0；ilen；i）elements〔i〕s。readObject（）；设置新数组setArray（elements）；｝疑问5：resetLock（）方法不好理解，解释一下？privatevoidresetLock（）｛等价于带Volatile语义的this。locknewReentrantLock（）UNSAFE。putObjectVolatile（this，lockOffset，newReentrantLock（））；｝UnsafeAPIprivatestaticfinalsun。misc。UnsafeUNSAFE；lock字段在对象实例数据中的偏移量privatestaticfinallonglockOffset；static｛这三行的作用：lock字段在对象实例数据中的偏移量UNSAFEsun。misc。Unsafe。getUnsafe（）；Classlt；？kCopyOnWriteArrayList。class；lockOffsetUNSAFE。objectFieldOffset（k。getDeclaredField（lock））；｝
　　小朋友又是有太多问号，举手提问：疑问5：resetLock（）方法不好理解，解释一下？
　　在static代码块中，会使用UnsafeAPI获取CopyOnWriteArrayList的lock字段在对象实例数据中的偏移量。由于字段的偏移是全局固定的，所以这个偏移量可以记录在static字段lockOffset中。
　　在resetLock（）中，通过UnSafeAPIputObjectVolatile将新建的ReentrantLock对象设置到CopyOnWriteArrayList的lock字段中，等价于带volatile语义的this。locknewReentrantLock（），保证这个字段的写入具备内存可见性。
　　字段的偏移量是什么意思呢？简单来说，普通对象和Class对象的实例数据区域是不同的：1、普通对象：包括当前类声明的实例字段以及父类声明的实例字段，不包括类的静态字段。UnSafeAPIobjectFieldOffset（Filed）就是获取了参数Filed在实例数据中的偏移量，后续就可以通过这个偏移量为字段赋值；2、Class对象：包括当前类声明的静态字段和方法表等。
　　对象内存布局
　　提示：关于字段的偏移量，我们在《对象的内存分为哪几个部分？》这篇文章里讨论过，去看看。3。7CopyOnWriteArraySet的clone（）过程
　　CopyOnWriteArraySet的clone（）很巧妙。按照正常的思维，CopyOnWriteArraySet中的array数组是引用类型，因此在clone（）中需要实现深拷贝，否则原对象与克隆对象就会相互影响。但事实上，array数组并没有被深拷贝，哇点解啊？疑问6：为什么array数组没有深拷贝？
　　这就是因为CopyOnWrite啊！没有Write为什么要Copy呢？（我觉得已经提醒到位了，只要你仔细阅读前文对CopyOnWrite的论证，你一定会懂的。要是是在不懂，私信我吧）publicObjectclone（）｛try｛SuppressWarnings（unchecked）疑问6：为什么array数组没有深拷贝？CopyOnWriteArrayListEclone（CopyOnWriteArrayListE）super。clone（）；设置ReentrantLock对象（相当于lock字段的深拷贝）clone。resetLock（）；returnclone；｝catch（CloneNotSupportedExceptione）｛thisshouldnthappen，sinceweareCloneablethrownewInternalError（）；｝｝4。CopyOnWriteArraySet源码分析
　　在Java标准库中，还提供了一个使用COW思想的Set集合CopyOnWriteArraySet。
　　CopyOnWriteArraySet和HashSet都是继承于AbstractSet的，但CopyOnWriteArraySet是基于CopyOnWriteArrayList动态数组的，并没有使用哈希思想。而HashSet是基于HashMap散列表的，能够实现O（1）查询。4。1CopyOnWriteArraySet的构造方法
　　看一下CopyOnWriteArraySet的构造方法，底层就是有一个CopyOnWriteArrayList动态数组。
　　CopyOnWriteArraySet。javapublicclassCopyOnWriteArraySetEextendsAbstractSetEimplementsjava。io。Serializable｛底层就是OnWriteArrayListprivatefinalCopyOnWriteArrayListEal；无参构造方法publicCopyOnWriteArraySet（）｛alnewCopyOnWriteArrayListE（）；｝带集合的构造方法publicCopyOnWriteArraySet（Collectionlt；？extendsEc）｛if（c。getClass（）CopyOnWriteArraySet。class）｛入参是CopyOnWriteArraySet，说明是不重复的，直接添加CopyOnWriteArraySetEcc（CopyOnWriteArraySetE）c；alnewCopyOnWriteArrayListE（cc。al）；｝else｛使用addAllAbsent添加不重复的元素alnewCopyOnWriteArrayListE（）；al。addAllAbsent（c）；｝｝publicintsize（）｛returnal。size（）；｝｝4。2CopyOnWriteArraySet的操作方法
　　CopyOnWriteArraySet的方法基本上都是交给CopyOnWriteArraySet代理的，由于没有使用哈希思想，所以操作的时间复杂度是O（n）。
　　CopyOnWriteArraySet。javapublicbooleanadd（Ee）｛returnal。addIfAbsent（e）；｝publicbooleancontains（Objecto）｛returnal。contains（o）；｝
　　CopyOnWriteArrayList。javapublicbooleanaddIfAbsent（Ee）｛Object〔〕snapshotgetArray（）；returnindexOf（e，snapshot，0，snapshot。length）0？false：addIfAbsent（e，snapshot）；｝publicbooleancontains（Objecto）｛Object〔〕elementsgetArray（）；returnindexOf（o，elements，0，elements。length）0；｝通过线性扫描匹配元素位置，而不是计算哈希匹配，时间复杂度是O（n）privatestaticintindexOf（Objecto，Object〔〕elements，intindex，intfence）｛if（onull）｛for（intiindex；ifence；i）if（elements〔i〕null）returni；｝else｛for（intiindex；ifence；i）if（o。equals（elements〔i〕））returni；｝return1；｝5。总结1、CopyOnWriteArrayList和ArrayList都是基于数组的动态数组，封装了操作数组时的搬运和扩容等逻辑；2、CopyOnWriteArrayList还是读写分离和写时复制的方案解决线程安全问题；3、使用CopyOnWriteArrayList的场景一定要保证是读多写少且数据量不大的场景，而且在写入数据的时候，要做到批量操作；4、CopyOnWriteArrayList的迭代器是弱数据一致性的的，迭代器会持有底层数组的引用，而CopyOnWriteArrayList的写入操作是写入到新数组，因此迭代器是无法感知到的；5、CopyOnWriteArraySet是基于CopyOnWriteArrayList动态数组的，并没有使用哈希思想。