如何解决ArrayList线程不安全

  • 方法1：使用Vector
  • 方法2：使用Collections工具类中的Collections.synchronizedList(new ArrayList) 方法
  • 方法3：JUC下的CopyOnWriteArrayList类，写时复制

    1. 类图

截屏2021-07-09 下午4.36.48.png
写时复制、读写分离

  1. public class CopyOnWriteArrayList<E>
  2.     implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

2. 成员变量

  1.      /** The lock protecting all mutators */
  2.     // 可重入锁，执行数组的变换操作时加锁，get操作不用加锁（读共享、写独享）
  3.     final transient ReentrantLock lock = new ReentrantLock();
  5.     /** The array, accessed only via getArray/setArray. */
  6.     // 可见性、有序性，存放元素的数组
  7.     private transient volatile Object[] array;
  9.     // get、set方法
  10.     final Object[] getArray() {
  11.         return array;
  12.     }
  14.     /**
  15.      * Sets the array.
  16.      */
  17.     final void setArray(Object[] a) {
  18.         array = a;
  19.     }

3.构造方法

  1.     public CopyOnWriteArrayList() {
  2.         setArray(new Object[0]);
  3.     }
  5.     /**
  6.      * Creates a list containing the elements of the specified
  7.      * collection, in the order they are returned by the collection's
  8.      * iterator.
  9.      *
  10.      * @param c the collection of initially held elements
  11.      * @throws NullPointerException if the specified collection is null
  12.      */
  13.     public CopyOnWriteArrayList(Collection<? extends E> c) {
  14.         Object[] elements;
  15.         if (c.getClass() == CopyOnWriteArrayList.class)
  16.             elements = ((CopyOnWriteArrayList<?>)c).getArray();
  17.         else {
  18.             elements = c.toArray();
  19.             // c.toArray might (incorrectly) not return Object[] (see 6260652)
  20.             if (elements.getClass() != Object[].class)
  21.                 elements = Arrays.copyOf(elements, elements.length, Object[].class);
  22.         }
  23.         setArray(elements);
  24.     }
  26.     /**
  27.      * Creates a list holding a copy of the given array.
  28.      *
  29.      * @param toCopyIn the array (a copy of this array is used as the
  30.      *        internal array)
  31.      * @throws NullPointerException if the specified array is null
  32.      */
  33.     public CopyOnWriteArrayList(E[] toCopyIn) {
  34.         setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
  35.     }

4.方法

4.1 add方法

  • _public boolean _add(E e)：末尾添加元素
  • _public void _add(_int _index, E element) ：指定位置添加元素
  • _public boolean _addIfAbsent(E e)：如果不存在加入元素
  • _public boolean _addAll(Collection<? _extends _E> c)
  • _public boolean _addAll(_int _index, Collection<? _extends _E> c)

    _public boolean _add(E e)

  2.     public boolean add(E e) {
  3.         final ReentrantLock lock = this.lock;
  4.         // 获取独占锁
  5.         lock.lock();
  6.         try {
  7.             // 获取数组内容
  8.             Object[] elements = getArray();
  9.             // 长度
  10.             int len = elements.length;
  11.             // 复制一份新的，长度为原长度+1 
  12.             Object[] newElements = Arrays.copyOf(elements, len + 1);
  13.             // 放入结尾新增的元素e
  14.             newElements[len] = e;
  15.             // 重新赋值原数组
  16.             setArray(newElements);
  17.             return true;
  18.         } finally {
  19.             // 释放独占锁
  20.             lock.unlock();
  21.         }
  22.     }
  • CopyOnWriteArrayList是如何保证【写】时线程安全的？因为用了ReentrantLock独占锁，保证同时只有一个线程对集合进行修改操作。
  • 数据是存储在CopyOnWriteArrayList中的array数组中的。
  • 在添加元素的时候，并不是直接往array里面add元素，而是复制出来了一个新的数组，并且复制出来的数组的长度是 【旧数组的长度+1】，再把旧的数组替换成新的数组，这是尤其需要注意的。

    _public void _add(_int _index, E element)

  1.     public void add(int index, E element) {
  2.         final ReentrantLock lock = this.lock;
  3.         lock.lock();
  4.         try {
  5.             Object[] elements = getArray();
  6.             int len = elements.length;
  7.             // index合法性检查
  8.             if (index > len || index < 0)
  9.                 throw new IndexOutOfBoundsException("Index: "+index+
  10.                                                     ", Size: "+len);
  11.             // 以下添加元素的思想同ArrayList
  12.             Object[] newElements;
  13.             // 获取移动的元素个数
  14.             int numMoved = len - index;
  15.             if (numMoved == 0)
  16.                 // 复制新的，在末尾添加就可以了
  17.                 newElements = Arrays.copyOf(elements, len + 1);
  18.             else {
  19.                 // 在index前后分段复制
  20.                 newElements = new Object[len + 1];
  21.                 System.arraycopy(elements, 0, newElements, 0, index);
  22.                 System.arraycopy(elements, index, newElements, index + 1,
  23.                                  numMoved);
  24.             }
  25.             newElements[index] = element;
  26.             // 重新赋值原数组
  27.             setArray(newElements);
  28.         } finally {
  29.             lock.unlock();
  30.         }
  31.     }

_public boolean _addIfAbsent(E e)

  1.     public boolean addIfAbsent(E e) {
  2.         Object[] snapshot = getArray();
  3.         // 先判断当前快照的数组有没有这个元素，没有就进入addIfAbsent方法添加
  4.         return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
  5.             addIfAbsent(e, snapshot);
  6.     }
  8.     /**
  9.      * A version of addIfAbsent using the strong hint that given
  10.      * recent snapshot does not contain e.
  11.      */
  12.     // 快照加
  13.     private boolean addIfAbsent(E e, Object[] snapshot) {
  14.         final ReentrantLock lock = this.lock;
  15.         lock.lock();
  16.         try {
  17.             Object[] current = getArray();
  18.             int len = current.length;
  19.             // 如果快照和当前最新的数组地址不一致，说明被别的线程动了
  20.             if (snapshot != current) {
  21.                 // Optimize for lost race to another addXXX operation
  22.                 // 计算较小的长度
  23.                 int common = Math.min(snapshot.length, len);
  24.                 // 遍历，
  25.                 for (int i = 0; i < common; i++)
  26.                     // 如果当前数组和快照数组中i对应的位置的值不相等，且
  27.                     if (current[i] != snapshot[i] && eq(e, current[i]))
  28.                         return false;
  29.                 if (indexOf(e, current, common, len) >= 0)
  30.                         return false;
  31.             }
  32.              // 否则，没有别人动，可以添加
  33.             Object[] newElements = Arrays.copyOf(current, len + 1);
  34.             newElements[len] = e;
  35.             setArray(newElements);
  36.             return true;
  37.         } finally {
  38.             lock.unlock();
  39.         }
  40.     }

存快照

4.2 查找方法

  • _public boolean _contains(Object o)
  • _public _E get(_int _index) ：共享的不加锁。存在弱一致性问题，别人修改的时候该线程不知道
  1.     public E get(int index) {
  2.         return get(getArray(), index);
  3.     }
  5.     private E get(Object[] a, int index) {
  6.         return (E) a[index];
  7.     }
  1.     // 取当前的array查询
  2.     public boolean contains(Object o) {
  3.         Object[] elements = getArray();
  4.         return indexOf(o, elements, 0, elements.length) >= 0;
  5.     }
  7.     private static int indexOf(Object o, Object[] elements,
  8.                                int index, int fence) {
  9.         if (o == null) {
  10.             for (int i = index; i < fence; i++)
  11.                 if (elements[i] == null)
  12.                     return i;
  13.         } else {
  14.             for (int i = index; i < fence; i++)
  15.                 if (o.equals(elements[i]))
  16.                     return i;
  17.         }
  18.         return -1;
  19.     }

4.3 修改方法

  1.     public E set(int index, E element) {
  2.         final ReentrantLock lock = this.lock;
  3.         lock.lock();
  4.         try {
  5.             // 拿到当前的array数组
  6.             Object[] elements = getArray();
  7.             E oldValue = get(elements, index);
  8.             如果oldValue和新值不相等
  9.             if (oldValue != element) {
  10.                 int len = elements.length;
  11.                 // 先复制一份，在新数组中修改，在重新赋值回去
  12.                 Object[] newElements = Arrays.copyOf(elements, len);
  13.                 newElements[index] = element;
  14.                 setArray(newElements);
  15.             } else {
  16.                 // 为了保证volatile 语义，即使没有修改，也要替换成新的数组
  17.                 // Not quite a no-op; ensures volatile write semantics
  18.                 setArray(elements);
  19.             }
  20.             return oldValue;
  21.         } finally {
  22.             lock.unlock();
  23.         }
  24.     }

4.4 删除方法

根据值删除

  1.     // 如果存在，删除第一个出现的o元素；否则不变
  2.     public boolean remove(Object o) {
  3.         Object[] snapshot = getArray();
  4.         int index = indexOf(o, snapshot, 0, snapshot.length);
  5.         return (index < 0) ? false : remove(o, snapshot, index);
  6.     }
  8.     // 找它所在的位置，返回坐标
  9.     private static int indexOf(Object o, Object[] elements,
  10.                                int index, int fence) {
  11.         if (o == null) {
  12.             for (int i = index; i < fence; i++)
  13.                 if (elements[i] == null)
  14.                     return i;
  15.         } else {
  16.             for (int i = index; i < fence; i++)
  17.                 if (o.equals(elements[i]))
  18.                     return i;
  19.         }
  20.         return -1;
  21.     }
  23.     // 快照删
  24.     private boolean remove(Object o, Object[] snapshot, int index) {
  25.         final ReentrantLock lock = this.lock;
  26.         lock.lock();
  27.         try {
  28.             Object[] current = getArray();
  29.             int len = current.length;
  30.             if (snapshot != current) findIndex: {
  31.                 int prefix = Math.min(index, len);
  32.                 for (int i = 0; i < prefix; i++) {
  33.                     if (current[i] != snapshot[i] && eq(o, current[i])) {
  34.                         index = i;
  35.                         break findIndex;
  36.                     }
  37.                 }
  38.                 if (index >= len)
  39.                     return false;
  40.                 if (current[index] == o)
  41.                     break findIndex;
  42.                 index = indexOf(o, current, index, len);
  43.                 if (index < 0)
  44.                     return false;
  45.             }
  46.             Object[] newElements = new Object[len - 1];
  47.             System.arraycopy(current, 0, newElements, 0, index);
  48.             System.arraycopy(current, index + 1,
  49.                              newElements, index,
  50.                              len - index - 1);
  51.             setArray(newElements);
  52.             return true;
  53.         } finally {
  54.             lock.unlock();
  55.         }
  56.     }

根据下标删除

  1.      public E remove(int index) {
  2.         final ReentrantLock lock = this.lock;
  3.         lock.lock();
  4.         try {
  5.             Object[] elements = getArray();
  6.             int len = elements.length;
  7.             // 获取该位置的元素oldValue
  8.             E oldValue = get(elements, index);
  9.             // 计算移动的个数
  10.             int numMoved = len - index - 1;
  11.             // 如果移动个数为0
  12.             if (numMoved == 0)
  13.                 //  为了保证volatile 语义，即使没有修改，也要替换成新的数组
  14.                 setArray(Arrays.copyOf(elements, len - 1));
  15.             else {
  16.                 // 否则，需要删除，同样new一个新数组进行操作，最后再重新赋值
  17.                 Object[] newElements = new Object[len - 1];
  18.                 // 在index前后分两段复制
  19.                 System.arraycopy(elements, 0, newElements, 0, index);
  20.                 System.arraycopy(elements, index + 1, newElements, index,
  21.                                  numMoved);
  22.                 setArray(newElements);
  23.             }
  24.             return oldValue;
  25.         } finally {
  26.             lock.unlock();
  27.         }
  28.     }