• CopyOnWriteArrayList源码分析

    目录

     

    一、概述

    二、源码分析

     retainAll():

    addAll()：

    removeRange():

    remove():

    add():

    add():

    set():

    三、总结

     

    一、概述

        Copy-On-Write是一种用于集合的并发访问的优化策略。

      基本思想：

            当我们往集合容器中写入元素的时候（添加、修改、删除），并不会直接在容器中写入，而是先将当前集合进行Copy，复制出一个新的容器，然后新容器里写入元素，写入操作完成后，再将原容器的引用指向新的容器。

      好处：

             实现对CopyOnWrite集合容器写入操作时的线程安全，但同时并不影响进行并发的读取操作。所以CopyOnWrite容器也是一种读写分离的思想。从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发集合容器，它们是CopyOnWriteArrayList和CopyOnWriteArraySet。

            CopyOnWriteArrayList相当于线程安全的ArrayList，内壁存储结构采用Object[]数组，线程安全ReentrantLock实现，允许多个线程并发读取，但只有一个线程写入。

    二、源码分析

     retainAll():

    1.  //修改当前集合与当前集合的交集，如果集合内部改变返回true，否则返回false；
    2. 	    public boolean retainAll(Collection c) {
    3. 	    	//如果集合为空，抛出异常NullPointerException
    4. 	        if (c == null) throw new NullPointerException();
    5. 	        //加锁
    6. 	        final ReentrantLock lock = this.lock;
    7. 	        lock.lock();
    8. 	        try {
    9. 	        	//获取数组
    10. 	            Object[] elements = getArray();
    11. 	            //获取数组的长度
    12. 	            int len = elements.length;
    13. 	            //判断数组是否为空
    14. 	            if (len != 0) {
    15. 	                // temp array holds those elements we know we want to keep
    16. 	                int newlen = 0;
    17. 	                //如果不为空，创建一个新数组
    18. 	                Object[] temp = new Object[len];
    19. 	                for (int i = 0; i < len; ++i) {
    20. 	                	//循环取出数组元素
    21. 	                    Object element = elements[i];
    22. 	                    //判断传入集合中是否含有此元素
    23. 	                    if (c.contains(element))
    24. 	                    	//如果有，加入新数组
    25. 	                        temp[newlen++] = element;
    26. 	                }
    27. 	                //判断新数组长度是否与原数组长度相同
    28. 	                if (newlen != len) {
    29. 	                	//如果不相同，复制新数组，存入定义数组
    30. 	                    setArray(Arrays.copyOf(temp, newlen));
    31. 	                    //返回true
    32. 	                    return true;
    33. 	                }
    34. 	            }
    35. 	            //返回false
    36. 	            return false;
    37. 	        } finally {
    38. 	        	//释放锁
    39. 	            lock.unlock();
    40. 	        }
    41. 	    }

    addAll()：

    1.  //将集合全部加入指定下标
    2. 	    public boolean addAll(int index, Collection c) {
    3. 	    	//将集合转入数组
    4. 	        Object[] cs = c.toArray();
    5. 	        //加锁
    6. 	        final ReentrantLock lock = this.lock;
    7. 	        lock.lock();
    8. 	        try {
    9. 	        	//获取数组及其长度
    10. 	            Object[] elements = getArray();
    11. 	            int len = elements.length;
    12. 	            //判断传入下标是否越界，越界则抛出异常
    13. 	            if (index > len || index < 0)
    14. 	                throw new IndexOutOfBoundsException("Index: "+index+
    15. 	                                                    ", Size: "+len);
    16. 	            //如果传入集合长度为0，则返回false
    17. 	            if (cs.length == 0)
    18. 	                return false;
    19. 	            int numMoved = len - index;
    20. 	            Object[] newElements;
    21. 	            //判断是否添加在数组尾部
    22. 	            if (numMoved == 0)
    23. 	            	//复制数组，长度为len + cs.length
    24. 	                newElements = Arrays.copyOf(elements, len + cs.length);
    25. 	            else {
    26. 	            	//否则，创建新数组，长度为数组长度+集合长度
    27. 	                newElements = new Object[len + cs.length];
    28. 	                System.arraycopy(elements, 0, newElements, 0, index);
    29. 	                System.arraycopy(elements, index,
    30. 	                                 newElements, index + cs.length,
    31. 	                                 numMoved);
    32. 	            }
    33. 	            //复制集合数组元素至新数组
    34. 	            System.arraycopy(cs, 0, newElements, index, cs.length);
    35. 	            //调用setArray()方法
    36. 	            setArray(newElements);
    37. 	            //返回true
    38. 	            return true;
    39. 	        } finally {
    40. 	        	//释放锁
    41. 	            lock.unlock();
    42. 	        }
    43. 	    }

    removeRange():

    1.     //删除区间范围数据
    2.     void removeRange(int fromIndex, int toIndex) {
    3. 	  //加锁
    4.         final ReentrantLock lock = this.lock;
    5.         lock.lock();
    6.         try {
    7.             //获取数组
    8.             Object[] elements = getArray();
    9. 		    //获取数组长度
    10.             int len = elements.length;
    11.             if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
    12.                 throw new IndexOutOfBoundsException();
    13. 		    //计算删除后的新数组长度
    14.             int newlen = len - (toIndex - fromIndex);
    15.             
    16.             int numMoved = len - toIndex;
    17. 		//判断是否删除至最后一个元素
    18.             if (numMoved == 0)
    19. 		   //如果是，则直接复制开始下标之前的元素
    20.                 setArray(Arrays.copyOf(elements, newlen));
    21.             else {
    22. 		   //如果删除的是中间内容，则创建一个新数组长度的数组
    23.                 Object[] newElements = new Object[newlen];
    24. 		       //复制除删除区间元素外其他元素
    25.                 System.arraycopy(elements, 0, newElements, 0, fromIndex);
    26.                 System.arraycopy(elements, toIndex, newElements,
    27.                                  fromIndex, numMoved);
    28. 		    //更新数组
    29.                 setArray(newElements);
    30.             }
    31.         } finally {
    32. 		//释放锁
    33.             lock.unlock();
    34.         }
    35.     }

    remove():

    1. //删除
    2.     public E remove(int index) {
    3. 	  //加锁
    4.         final ReentrantLock lock = this.lock;
    5.         lock.lock();
    6.         try {
    7.             Object[] elements = getArray();
    8. 		//获取数组长度
    9.             int len = elements.length;
    10. 		//获取指定下标元素
    11.             E oldValue = get(elements, index);
    12. 		
    13.             int numMoved = len - index - 1;
    14. 		//判断删除的是否是最后一个元素
    15.             if (numMoved == 0)
    16. 		        //如果是,复制原数组,长度为len-1
    17.                 setArray(Arrays.copyOf(elements, len - 1));
    18.             else {
    19. 		       //创建一个新数组，长度为len-1
    20.                 Object[] newElements = new Object[len - 1];
    21. 		        //复制原数组除指定删除外其他元素
    22.                 System.arraycopy(elements, 0, newElements, 0, index);
    23.                 System.arraycopy(elements, index + 1, newElements, index,
    24.                                  numMoved);
    25. 		    //更新数组
    26.                 setArray(newElements);
    27.             }
    28. 		//返回原值
    29.             return oldValue;
    30.         } finally {
    31. 		//释放锁
    32.             lock.unlock();
    33.         }
    34.     }

    add():

    1. //在指定数组的指定位置添加
    2.     public void add(int index, E element) {
    3. 	  //加锁
    4.         final ReentrantLock lock = this.lock;
    5.         lock.lock();
    6.         try {
    7.             Object[] elements = getArray();
    8. 		//获取数组长度
    9.             int len = elements.length;
    10. 		//判断传入下标是否越界
    11.             if (index > len || index < 0)
    12.                 throw new IndexOutOfBoundsException("Index: "+index+
    13.                                                     ", Size: "+len);
    14.             Object[] newElements;
    15.             int numMoved = len - index;
    16. 		//判断是否在末尾添加
    17.             if (numMoved == 0)
    18. 		   //复制传入数组，长度为len+1
    19.                 newElements = Arrays.copyOf(elements, len + 1);
    20.             else {
    21.  		   //如果不是最后一个则创建一个新数组，长度比原来多一个
    22.                 newElements = new Object[len + 1];
    23. 		   //越过传入下标，复制原数组中的数据
    24.                 System.arraycopy(elements, 0, newElements, 0, index);
    25.                 System.arraycopy(elements, index, newElements, index + 1,
    26.                                  numMoved);
    27.             }
    28. 		//将传入值添加至传入下标位置
    29.             newElements[index] = element;
    30. 		//调用setArray()方法：将新数组赋值给定义数组
    31.             setArray(newElements);
    32.         } finally {
    33. 		//释放锁
    34.             lock.unlock();
    35.         }
    36.     }

    add():

    1. //添加元素至末尾
    2. public boolean add(E e) {
    3. 	  //加锁
    4.         final ReentrantLock lock = this.lock;
    5.         lock.lock();
    6.         try {
    7.             Object[] elements = getArray();
    8. 		//获取数组长度
    9.             int len = elements.length;
    10. 		//复制原数组,长度为len+1
    11.             Object[] newElements = Arrays.copyOf(elements, len + 1);
    12. 		//将要新元素添加至末尾
    13.             newElements[len] = e;
    14. 		//更新数组
    15.             setArray(newElements);
    16. 		//添加成功，返回true
    17.             return true;
    18.         } finally {
    19. 		//释放锁
    20.             lock.unlock();
    21.         }
    22.     }

    set():

    1.    public E set(int index, E element) {
    2. 	  //加锁
    3.         final ReentrantLock lock = this.lock;
    4.         lock.lock();
    5.         try {
    6. 		//获取数组
    7.             Object[] elements = getArray();
    8.  
    9. 		    //获取指定修改下标元素
    10.             E oldValue = get(elements, index);
    11.  
    12. 		    //判断修改后元素是否等于原值
    13.             if (oldValue != element) {
    14. 		    //如果不是，则得到数组长度
    15.                 int len = elements.length;
    16. 			
    17. 		    //复制数组
    18.                 Object[] newElements = Arrays.copyOf(elements, len);
    19.  
    20. 		    //在复制后的数组中修改指定位置元素
    21.                 newElements[index] = element;
    22.  
    23. 		   //更新数组
    24.                 setArray(newElements);
    25.             } else {
    26.                 // Not quite a no-op; ensures volatile write semantics
    27. 		   //如果与修改前的值相同，之间赋值给定义数组
    28.                 setArray(elements);
    29.             }
    30. 		//返回修改前元素
    31.             return oldValue;
    32.         } finally {
    33. 		//释放锁
    34.             lock.unlock();
    35.         }
    36.     }

    三、总结

    1.在保证并发读取的前提下，确保了写入时的线程安全；

    2.由于每次写入操作时，进行了Copy复制原数组，所以无需扩容；

    3.适合读多写少的应用场景。由于add()   set()  remove()等修改操作需要复制整个数组，所以会有内存开销大的问题；

    4.CopyOnWriteArrayList由于只在写入时加锁，所以只能保证数据的一致性，不能保证数据的实时一致性。

  • 相关阅读:
    软考141-上午题-【软件工程】-杂题+小结
    pyenv安装python，Makefile报错
    【Kotlin】‘name‘ hides member of supertype ‘Enum‘ and needs ‘override‘ modifier
    Oracle/PLSQL: Cos Function
    2. redis常见数据类型
    Elasticsearch：使用向量化和 FFI/madvise 加速 Lucene
    Raft协议浅析
    工业级Netty网关，京东是如何架构的？
    指针（5）
    深度学习-RNN
  • 原文地址：https://blog.csdn.net/qq_49194786/article/details/126922904