ArrayList的实现原理以及实现线程安全

  1. 一、ArrayList概述

    1. ArrayList是基于数组实现的,是一个动态的数字,可以自动扩容。
    2. ArrayList不是线程安全的,效率比较高,只能用于单线程的环境中,在多线程环境中可以使用Collections.synchronizedList(List list)函数返回一个线程安全的ArrayList集合,或者使用concurrent并发包下的CopyOnWriteArrayList的。
    1.  
      //使用Collections.synchronizedList(List list)方法实现线程安全
    2.  
      List<?> list=Collections.synchronizedList(new ArrayList<>());

    二、通过源码解析Collections.synchronizedList(List list)方法如何实现线程安全?

    1.  
      public static List synchronizedList(List list1) {
    2.  
      return ((List) ((list1 instanceof RandomAccess) ? new SynchronizedRandomAccessList(list1)
    3.  
      : new SynchronizedList(list1)));
    4.  
      }

             通过判断传入的list类是否为RandomAccess类,如果是则实例化SynchronizedRandomAccessList,如果不是,则实例化SynchronizedList。如果你传入的list集合是ArrayList或者Vector。那么则是实例化SynchronizedRandomAccessList。我们从源码可以查看原因:

    ArrayList集合源码:

    public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable {

    Vector集合源码:

    public class Vector extends AbstractList implements List, RandomAccess, Cloneable, Serializable {

            我们可以发现ArrayList和Vector集合两者都实现了List和RandomAccess接口。接下来看看SynchronizedRandomAccessList类的实现:

    1.  
      static class SynchronizedRandomAccessList extends SynchronizedList implements RandomAccess {
    2.  
       
    3.  
      public List subList(int i, int j)
    4.  
      {
    5.  
      Object obj = mutex;
    6.  
      return new SynchronizedRandomAccessList(list.subList(i, j), mutex);
    7.  
      }
    8.  
       
    9.  
      private Object writeReplace() {
    10.  
      return new SynchronizedList(list);
    11.  
      }
    12.  
       
    13.  
      private static final long serialVersionUID = 1530674583602358482L;
    14.  
       
    15.  
      SynchronizedRandomAccessList(List list1) {
    16.  
      super(list1);
    17.  
      }
    18.  
       
    19.  
      SynchronizedRandomAccessList(List list1, Object obj) {
    20.  
      super(list1, obj);
    21.  
      }
    22.  
      }

           因为SynchronizedRandomAccessList这个类继承自SynchronizedList,而大部分方法都在SynchronizedList中实现了,所以源码中只包含了很少的方法。我们来看看SynchronizedList的源码:

    1.  
      static class SynchronizedList<E>
    2.  
      extends SynchronizedCollection<E>
    3.  
      implements List<E> {
    4.  
      private static final long serialVersionUID = -7754090372962971524L;
    5.  
       
    6.  
      final List<E> list;
    7.  
       
    8.  
      SynchronizedList(List<E> list) {
    9.  
      super(list);
    10.  
      this.list = list;
    11.  
      }
    12.  
      SynchronizedList(List<E> list, Object mutex) {
    13.  
      super(list, mutex);
    14.  
      this.list = list;
    15.  
      }
    16.  
       
    17.  
      public boolean equals(Object o) {
    18.  
      if (this == o)
    19.  
      return true;
    20.  
      synchronized (mutex) {return list.equals(o);}
    21.  
      }
    22.  
      public int hashCode() {
    23.  
      synchronized (mutex) {return list.hashCode();}
    24.  
      }
    25.  
       
    26.  
      public E get(int index) {
    27.  
      synchronized (mutex) {return list.get(index);}
    28.  
      }
    29.  
      public E set(int index, E element) {
    30.  
      synchronized (mutex) {return list.set(index, element);}
    31.  
      }
    32.  
      public void add(int index, E element) {
    33.  
      synchronized (mutex) {list.add(index, element);}
    34.  
      }
    35.  
      public E remove(int index) {
    36.  
      synchronized (mutex) {return list.remove(index);}
    37.  
      }
    38.  
       
    39.  
      public int indexOf(Object o) {
    40.  
      synchronized (mutex) {return list.indexOf(o);}
    41.  
      }
    42.  
      public int lastIndexOf(Object o) {
    43.  
      synchronized (mutex) {return list.lastIndexOf(o);}
    44.  
      }
    45.  
       
    46.  
      public boolean addAll(int index, Collection<? extends E> c) {
    47.  
      synchronized (mutex) {return list.addAll(index, c);}
    48.  
      }
    49.  
       
    50.  
      public ListIterator<E> listIterator() {
    51.  
      return list.listIterator(); // Must be manually synched by user
    52.  
      }
    53.  
       
    54.  
      public ListIterator<E> listIterator(int index) {
    55.  
      return list.listIterator(index); // Must be manually synched by user
    56.  
      }
    57.  
       
    58.  
      public List<E> subList(int fromIndex, int toIndex) {
    59.  
      synchronized (mutex) {
    60.  
      return new SynchronizedList<>(list.subList(fromIndex, toIndex),
    61.  
      mutex);
    62.  
      }
    63.  
      }
    64.  
       
    65.  
      @Override
    66.  
      public void replaceAll(UnaryOperator<E> operator) {
    67.  
      synchronized (mutex) {list.replaceAll(operator);}
    68.  
      }
    69.  
      @Override
    70.  
      public void sort(Comparator<? super E> c) {
    71.  
      synchronized (mutex) {list.sort(c);}
    72.  
      }
    73.  
      ... ...
    74.  
      }

           可以发现SynchronizedList方法中地方都用到了同步锁,并且参数都是mutex。我们通过点击mutex字段进入到SynchronizedCollection类中,可以得知mutex是在SynchronizedCollection类中定义的。我们继续查看SynchronizedCollection部分源码:

    1.  
      static class SynchronizedCollection<E> implements Collection<E>, Serializable {
    2.  
      private static final long serialVersionUID = 3053995032091335093L;
    3.  
      final Collection<E> c; // Backing Collection
    4.  
      final Object mutex; // Object on which to synchronize
    5.  
       
    6.  
      SynchronizedCollection(Collection<E> c) {
    7.  
      if (c==null)
    8.  
      throw new NullPointerException();
    9.  
      this.c = c;
    10.  
      mutex = this;
    11.  
      }
    12.  
       
    13.  
      SynchronizedCollection(Collection<E> c, Object mutex) {
    14.  
      this.c = c;
    15.  
      this.mutex = mutex;
    16.  
      }
    17.  
      }

            可以发现其实我们调用synchronizedList方法的使用,内部锁都是一样的,所以它可以实现线程的同步。

    三、通过源码解析CopyOnWriteArrayList如何做到线程安全的?

    CopyOnWriteArrayList使用了一种叫写时复制的方法,当有新元素添加到CopyOnWriteArrayList时,先从原有的数组中拷贝一份出来,然后在新的数组做写操作,写完之后,再将原来的数组引用指向到新数组。

    当有新元素加入的时候,如下图,创建新数组,并往新数组中加入一个新元素,这个时候,array这个引用仍然是指向原数组的。

    ArrayList的实现原理以及实现线程安全

    当元素在新数组添加成功后,将array这个引用指向新数组。

    ArrayList的实现原理以及实现线程安全

    CopyOnWriteArrayList的整个add操作都是在锁的保护下进行的。 
    这样做是为了避免在多线程并发add的时候,复制出多个副本出来,把数据搞乱了,导致最终的数组数据不是我们期望的。我们来看看CopyOnWriteArrayList源码:

    1.  
      transient final ReentrantLock lock = new ReentrantLock();
    2.  
       
    3.  
      /** The array, accessed only via getArray/setArray. */
    4.  
      private volatile transient Object[] array;//保证了线程的可见性
    5.  
       
    6.  
      public boolean add(E e) {
    7.  
      final ReentrantLock lock = this.lock;//ReentrantLock 保证了线程的可见性和顺序性,即保证了多线程安全。
    8.  
      //1、先加锁
    9.  
      lock.lock();
    10.  
      try {
    11.  
      Object[] elements = getArray();
    12.  
      int len = elements.length;
    13.  
      Object[] newElements = Arrays.copyOf(elements, len + 1);////2、拷贝数组,在原先数组基础之上新建长度+1的数组,并将原先数组当中的内容拷贝到新数组当中。
    14.  
       
    15.  
      //3、将元素加入到新数组中
    16.  
      newElements[len] = e;
    17.  
      //4、将array引用指向到新数组
    18.  
      setArray(newElements);//对新数组进行赋值
    19.  
      return true;
    20.  
      } finally {
    21.  
      lock.unlock();
    22.  
      }
    23.  
      }

    由于所有的写操作都是在新数组进行的,这个时候如果有线程并发的写,则通过锁来控制,如果有线程并发的读,则分几种情况: 
    1、如果写操作未完成,那么直接读取原数组的数据; 
    2、如果写操作完成,但是引用还未指向新数组,那么也是读取原数组数据; 
    3、如果写操作完成,并且引用已经指向了新的数组,那么直接从新数组中读取数据。

    可见,CopyOnWriteArrayList的读操作是可以不用加锁的。

    四、Collections.synchronizedList & CopyOnWriteArrayList

           CopyOnWriteArrayList和Collections.synchronizedList是实现线程安全的列表的两种方式。两种实现方式分别针对不同情况有不同的性能表现,其中CopyOnWriteArrayList的写操作性能较差,而多线程的读操作性能较好。而Collections.synchronizedList的写操作性能比CopyOnWriteArrayList在多线程操作的情况下要好很多,而读操作因为是采用了synchronized关键字的方式,其读操作性能并不如CopyOnWriteArrayList。因此在不同的应用场景下,应该选择不同的多线程安全实现类。

    转载于:https://my.oschina.net/u/3872757/blog/2989705

相关推荐