Java源码分析系列笔记-10.CopyOnWriteArrayList

目录

• 1. 是什么
  
• 2. 如何使用
  
• 3. 原理
  
  
  
  • 3.1. 构造方法
    
  • 3.2. add方法
    
    
    
    • 3.2.1. 先加锁
      
    • 3.2.2. 复制数组并在这份数组上操作
      
    • 3.2.3. 将复制的数组set回属性
      
    
    
  • 3.3. remove方法
    
    
    
    • 3.3.1. 找到要删除元素的位置
      
    • 3.3.2. 加锁并把除了被删除之外的其他元素复制到新数组中，set回属性中
      
    
    
  • 3.4. get(index)方法
    
    
    
    • 3.4.1. 没加锁，通过数组[index]获取
      
    
    
  • 3.5. contains
    
    
    
    • 3.5.1. 不加锁遍历数据查询
      
    
    
  • 3.6. set
    
    
    
    • 3.6.1. 先加锁
      
    • 3.6.2. 从原数组中获取index位置的值
      
    • 3.6.3. 如果index位置不相等，那么复制新数组、修改并set回属性
      
    • 3.6.4. 即使相等也要set回去保证volatile语义
      
    
    
  
  
• 4. 总结
  
• 5. 参考
  

1. 是什么

这个list借鉴的是读写分离的思想（弱一致性）

• 读的时候可以并发读，不加锁；
  
• 写的时候需要加锁，复制一份原有数据进行修改，改完后写回list
  

2. 如何使用

1. public class CopyOnWriteArrayListTest
2. {
3.     public static void main(String[] args)
4.     {
5.         CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
7.         list.add("a");
8.         list.add("b");
9.         list.add("c");
11.         list.remove("a");
12.         System.out.println(list.contains("a"));//false
14.         System.out.println(list.get(0));//b
16.         list.set(0, "d");
18.         System.out.println(list);//[d, c]
20.         System.out.println(Thread.currentThread().getName() + "读取list:" + list);//[d, c]
22.         new Thread(()->{
23.             System.out.println(Thread.currentThread().getName() + "读取list:" + list);//[d, c]
24.             try
25.             {
26.                 TimeUnit.SECONDS.sleep(2);
27.             }
28.             catch (InterruptedException e)
29.             {
30.                 e.printStackTrace();
31.             }
32.             System.out.println(Thread.currentThread().getName() + "再次读取list:" + list);//[c]
34.         }).start();
35.         new Thread(()->{
36.             System.out.println(Thread.currentThread().getName() + "读取list:" + list);//[d, c]
37.             try
38.             {
39.                 TimeUnit.SECONDS.sleep(2);
40.             }
41.             catch (InterruptedException e)
42.             {
43.                 e.printStackTrace();
44.             }
45.             System.out.println(Thread.currentThread().getName() + "再次读取list:" + list);//[c]
46.         }).start();
49.         try
50.         {
51.             TimeUnit.SECONDS.sleep(1);
52.         }
53.         catch (InterruptedException e)
54.         {
55.             e.printStackTrace();
56.         }
57.         list.remove(0);
59.         System.out.println(Thread.currentThread().getName() + "读取修改后的list:" + list);//[c]
61.     }
62. }

复制代码

3. 原理

3.1. 构造方法

1. public class CopyOnWriteArrayList<E>
2.     implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
4.     //用于写时加锁
5.     final transient ReentrantLock lock = new ReentrantLock();
7.     //底层通过object数组实现, 通过 getArray/setArray访问
8.     //volatile修饰保证多线程能及时看到最新结果
9.     private transient volatile Object[] array;
11.     public CopyOnWriteArrayList() {
12.                 //初始化数组长度为0
13.                 setArray(new Object[0]);
14.         }
16.     //get set都没做什么同步措施
17.         final void setArray(Object[] a) {
18.                 array = a;
19.         }
20.         final Object[] getArray() {
21.         return array;
22.     }
23. }

复制代码

• 可以看到底层是通过object数组实现,
  
  
  
  • 通过 getArray/setArray访问，这两个方法都没做什么同步措施
    
  • 使用volatile修饰保证多线程能及时看到最新结果
    
  
  
• 并且有一个ReentrantLock，保证写时加锁
  

3.2. add方法

1. public boolean add(E e) {
2.         //多个线程同时调用add方法保证只有一个能进入
3.     final ReentrantLock lock = this.lock;
4.     lock.lock();
5.     try {
6.             //获取原数组
7.         Object[] elements = getArray();
8.         int len = elements.length;
9.         //复制并扩容数组
10.         Object[] newElements = Arrays.copyOf(elements, len + 1);
11.         //赋值
12.         newElements[len] = e;
13.         //写回数组
14.         setArray(newElements);
15.         return true;
16.     } finally {
17.         lock.unlock();
18.     }
19. }

复制代码

• 4行：加锁。写的操作必须加锁
  
• 7-12行：copy原数组，扩容并修改
  
• 14行：写回原数组
  

下面具体说明：
3.2.1. 先加锁

1. //多个线程同时调用add方法保证只有一个能进入
2. final ReentrantLock lock = this.lock;
3. lock.lock();
4. //。。。。。
5. } finally {
6.     lock.unlock();
7. }

复制代码

3.2.2. 复制数组并在这份数组上操作

1. //获取原数组
2. Object[] elements = getArray();
3. int len = elements.length;
4. //复制并扩容数组
5. Object[] newElements = Arrays.copyOf(elements, len + 1);
6. //赋值
7. newElements[len] = e;

复制代码

3.2.3. 将复制的数组set回属性

1. //写回数组
2. //array = a;
3. //由于array是volatile修饰的，一旦改变之后其他线程会清空工作内存中的array，这样读取新值
4. setArray(newElements);

复制代码

3.3. remove方法

• remove
  

1. public boolean remove(Object o) {
2.         //获取原数组
3.     Object[] snapshot = getArray();
4.     //从原数组的0-最后一个位置查找o是否存在并获取其下标
5.     int index = indexOf(o, snapshot, 0, snapshot.length);
6.     //存在则删除
7.     return (index < 0) ? false : remove(o, snapshot, index);
8. }

复制代码

• 3-5行：找到数组中值o的位置index
  
• 7行：加锁删除数组中的index位置
  

下面具体说明：
3.3.1. 找到要删除元素的位置

• indexOf
  

1. private static int indexOf(Object o, Object[] elements,
2.                            int index, int fence) {
3.    //要找的值为null
4.     if (o == null) {
5.         for (int i = index; i < fence; i++)
6.             if (elements[i] == null)
7.                 return i;
8.     //不为null
9.     } else {
10.         for (int i = index; i < fence; i++)
11.             if (o.equals(elements[i]))
12.                 return i;
13.     }
14.     return -1;
15. }

复制代码

这个方法没有加锁，只是把判断值是否为null分别进行处理
3.3.2. 加锁并把除了被删除之外的其他元素复制到新数组中，set回属性中

• remove
  

1. //再snapshot数组删除下标为index且值为o的元素
2. private boolean remove(Object o, Object[] snapshot, int index) {
3.     final ReentrantLock lock = this.lock;
4.     lock.lock();
5.     try {
6.             //获取现在的数组（可能已经改变过了）
7.         Object[] current = getArray();
8.         int len = current.length;
9.         //数组改变过了
10.         if (snapshot != current) findIndex: {
11.                 //遍历原数组和改变后的数组0-index位置是否相同，相同则可以删除
12.                 //有一个位置不相同 且 改变后的数组这个位置xx的元素与要删除的元素相同，那么重新从0-xx比较
13.             int prefix = Math.min(index, len);
14.             for (int i = 0; i < prefix; i++) {
15.                 if (current[i] != snapshot[i] && eq(o, current[i])) {
16.                     index = i;
17.                     break findIndex;
18.                 }
19.             }
20.             //改变后的数组长度比index短了，那么不可能删除了，返回false
21.             if (index >= len)
22.                 return false;
23.             //改变后的数组index位置仍然是o
24.             if (current[index] == o)
25.                     //退出findIndex这段代码，即执行34行
26.                 break findIndex;
27.             //在改变后的数组中index-len位置重新寻找值为o的元素
28.             index = indexOf(o, current, index, len);
29.             //没找到，删除不了返回false
30.             if (index < 0)
31.                 return false;
32.         }
33.         //创建原数组长度-1的新数组
34.         Object[] newElements = new Object[len - 1];
35.         //复制index左边的元素到新数组
36.         System.arraycopy(current, 0, newElements, 0, index);
37.         //复制index右边的元素到新数组（等于删除了index位置的元素）
38.         System.arraycopy(current, index + 1,
39.                          newElements, index,
40.                          len - index - 1);
41.          //修改为新数组
42.         setArray(newElements);
43.         return true;
44.     } finally {
45.         lock.unlock();
46.     }
47. }

复制代码

3.4. get(index)方法

1. public E get(int index) {
2.     return get(getArray(), index);
3. }

复制代码

get方法属于读取操作，所以不需要加锁，直接原数组上通过下标获取
3.4.1. 没加锁，通过数组[index]获取

• get
  

1. private E get(Object[] a, int index) {
2.     return (E) a[index];
3. }

复制代码

3.5. contains

1. public boolean contains(Object o) {
2.         //获取原数组
3.     Object[] elements = getArray();
4.     //再查找下标
5.     return indexOf(o, elements, 0, elements.length) >= 0;
6. }

复制代码

• 3行：contains方法属于读方法，所以没加锁
  
• 5行：直接遍历数组查找
  

3.5.1. 不加锁遍历数据查询

• indexOf
  

1. private static int indexOf(Object o, Object[] elements,
2.                            int index, int fence) {
3.     //要找的值为null
4.     if (o == null) {
5.         for (int i = index; i < fence; i++)
6.             if (elements[i] == null)
7.                 return i;
8.     //要找的值不为null
9.     } else {
10.         for (int i = index; i < fence; i++)
11.             if (o.equals(elements[i]))
12.                 return i;
13.     }
14.     return -1;
15. }

复制代码

3.6. set

1. //修改index位置的值为element
2. public E set(int index, E element) {
3.     final ReentrantLock lock = this.lock;
4.     lock.lock();
5.     try {
6.             //获取原数组
7.         Object[] elements = getArray();
8.         //获取原数组index位置的值
9.         E oldValue = get(elements, index);
11.                 //index位置不是element
12.         if (oldValue != element) {
13.                 //复制原数组到新数组，修改index位置的值，set回array
14.             int len = elements.length;
15.             Object[] newElements = Arrays.copyOf(elements, len);
16.             newElements[index] = element;
17.             setArray(newElements);
18.         //index位置已经是element了，那么直接set回array（保证volatile语义）
19.         } else {
20.             // Not quite a no-op; ensures volatile write semantics
21.             setArray(elements);
22.         }
23.         return oldValue;
24.     } finally {
25.         lock.unlock();
26.     }
27. }

复制代码

• 4行：set方法属于写方法，所以需要先加锁
  
• 7-9行：通过下标查找值
  
• 12-18行：第2步查找到的值跟现在数组中的值不同，说明有改变。那么copy原数组、修改、写回原数组
  
• 19-22 行：第2步查找到的值跟现在数组中的值相同，说明没有改变。虽然不做什么处理也行，但为了保证volatile语义，还是set回数组
  

下面详细说明：
3.6.1. 先加锁

1. final ReentrantLock lock = this.lock;
2. lock.lock();
3. try {
4. } finally {
5.     lock.unlock();
6. }

复制代码

3.6.2. 从原数组中获取index位置的值

1. //获取原数组
2. Object[] elements = getArray();
3. //获取原数组index位置的值
4. E oldValue = get(elements, index);

复制代码

3.6.3. 如果index位置不相等，那么复制新数组、修改并set回属性

1. //index位置不是element
2. if (oldValue != element) {
3.         //复制原数组到新数组，修改index位置的值，set回array
4.     int len = elements.length;
5.     Object[] newElements = Arrays.copyOf(elements, len);
6.     newElements[index] = element;
7.     setArray(newElements);
9. }

复制代码

3.6.4. 即使相等也要set回去保证volatile语义

1. //index位置已经是element了，那么直接set回array（保证volatile语义）
2. else {
3.     // Not quite a no-op; ensures volatile write semantics
4.     setArray(elements);
5. }

复制代码

4. 总结

• 适合读多写少的场景
  
• 当调用add方法的时候加锁修改，内存中有两份数组，一份原始的，另一份是当前线程修改的数组
  
• 当调用get方法时不加锁，获取的是原有的数组
  

5. 参考

• Java CopyOnWriteArrayList详解 - 简书
  
• 聊聊并发-Java中的Copy-On-Write容器 | 并发编程网 – ifeve.com
  
• CopyOnWriteArrayList你都不知道，怎么拿offer？_weixin_34034261的博客-CSDN博客
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！