常用集合-List

• 常用集合-List
  • 集合类型分类
    • List
      • 不安全的子类（ArrayList、LinkedList)
      • 线程安全的子类（CopyOnWriteArrayList、Vector，stack）

常用集合-List

介绍常用集合List的特点、线程安全问题、实现线程安全的方式。

集合类型分类

• List 支持null元素和重复元素的动态扩容列表

  • 实现类：ArrayList、LinkedList、Stack、CopyOnWriteArrayList、Vector等

• Set 不支持重复元素的动态扩容列表

  • 实现类：EnumSet、TreeSet、HashSet、LinkedHashSet、NavigableSet、

    ConcurrentSkipListSet、CopyOnWriteArraySet 等

• map 存储Key/Value键值对的映射集。

  • 实现类：HashMap、TreeMap、LinkedHashMap、ConcurrentHashMap、HashTable、

    ConcurrentSkipListMap 等

• queue/deque queue是在集合尾部添加元素，在头部删除元素的队列；deque是可在头部和尾部添加或者删除元素的双端队列。

  • 实现类：ArrayDeque、PriorityQueue、LinkedBlockingDeque、

    LinkedBlockingQueue、PriorityBlockingQueue、ArrayBlockingQueue、ConcurrentLinkedDeque、ConcurrentLinkedQueue、BlockingQueue 等

List

不安全的子类（ArrayList、LinkedList)

• ArrayList （* @since 1.2）

  /**
   * @author  Josh Bloch
   * @author  Neal Gafter
   * @see     Collection
   * @see     List
   * @see     LinkedList
   * @see     Vector
   * @since   1.2
   */
  public class ArrayList<E> extends AbstractList<E>
          implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  {
      private static final int DEFAULT_CAPACITY = 10;
  	...
  }
  

  ​ ArrayList是一个容量动态扩张的集合，实现了RandomAccess接口，支持随机访问，初始容量10，最大容量Integer.MAX_VALUE - 8（2147483640），每次调用ArrayList的新增或者删除等修改方法，继承自AbstactList抽象类的属性modCount都会自增，当通过Interactor遍历集合时，只要modCount被其他线程修改，就会抛出ConcurrentModificationException。

  //add 方法
  public boolean add(E e) {
      //首先进行扩容校验,将插入的值放到尾部，并将 size + 1 。
      ensureCapacityInternal(size + 1);  // Increments modCount!! 
      elementData[size++] = e;
      return true;
  }
  //确保内部空间足够
  private void ensureCapacityInternal(int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      ensureExplicitCapacity(minCapacity);
  }
  private void ensureExplicitCapacity(int minCapacity) {
      modCount++; //操作次数
      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);//扩容  -> 数组复制的过程
  }
  //分析：ArrayList 的主要消耗是数组扩容以及在指定位置添加数据，在日常使用时最好是指定大小，尽量减少扩容。更要减少在指定位置插入数据的操作。
  

  ​ ArrayList是线程不安全的类，因为它的操作自身集合属性的方法没有进行同步也不是原子性操作，所以会出现不一致现象，可以通过List list = Collections.synchronizedList(new ArrayList(...))把它转成线程安全的集合，当然只是封装了对ArrayList的操作，保存同步而已，性能不是很高，所有的修改操作都要一个个同步。 jdk1.8后支持Spliterator迭代器 -> 提高效率。

• LinkedList（* @since 1.2）

  /**
   * @author  Josh Bloch
   * @see     List
   * @see     ArrayList
   * @since 1.2
   * @param <E> the type of elements held in this collection
   */
  public class LinkedList<E>
      extends AbstractSequentialList<E>
      implements List<E>, Deque<E>, Cloneable, java.io.Serializable
  {
      transient int size = 0;
      /**
       * Pointer to first node.
       * Invariant: (first == null && last == null) ||
       *            (first.prev == null && first.item != null)
       */
      transient Node<E> first;
      /**
       * Pointer to last node.
       * Invariant: (first == null && last == null) ||
       *            (last.next == null && last.item != null)
       */
      transient Node<E> last;
      ...
  } 
  

  ​ LinkedList内部是链表结果，非线程安全，修改链表结构的操作需要进行同步，如何有线程在用Interator遍历，而有线程在修改链表，会引发fast-fail，及Iterator会抛出ConcurrentModificationException,可以使用Collections.synchronizedList方法来包装它。

  public void forEachRemaining(Consumer<? super E> action) {
      Node<E> p; int n;
      if (action == null) throw new NullPointerException();
      if ((n = getEst()) > 0 && (p = current) != null) {
          current = null;
          est = 0;
          do {
              E e = p.item;
              p = p.next;
              action.accept(e);
          } while(p != null && --n > 0);
      }
      //如果修改的次数与期望的次数不一致，抛出异常
      if (list.modCount != expectedModCount)
          throw new ConcurrentModificationException();
  }
  

  ​ 添加元素的方法只是新增一个节点然后改变尾部节点和新增节点的引用链接，所以新增和删除操作比较快，但是不支持随机访问，判断某个值是否存在的方法contains(Object o)需要从第一个元素开始遍历到符合条件的元素止，效率不是很高。

  //为什么说新增或移除效率高？
  public boolean add(E e) {
      linkLast(e);
      return true;
  }
  void linkLast(E e) {
      final Node<E> l = last;
      final Node<E> newNode = new Node<>(l, e, null);
      last = newNode;
      if (l == null)
          first = newNode;//只是改变了指向位置
      else
          l.next = newNode;//只是改变了指向位置
      size++;
      modCount++;
  }
    
  //为什么说LinkedList查询效率低？
  public E get(int index) {
      checkElementIndex(index);
      return node(index).item;
  }
  Node<E> node(int index) {
      // assert isElementIndex(index);
      if (index < (size >> 1)) {//采用二分查找算法
          Node<E> x = first;
          for (int i = 0; i < index; i++)
              x = x.next;//需要一个一个的遍历
          return x;
      } else {
          Node<E> x = last;
          for (int i = size - 1; i > index; i--)
              x = x.prev;
          return x;
      }
  }
  

  ​ 由此可以看出是使用二分查找来看 index 离 size 中间距离来判断是从头结点正序查还是从尾节点倒序查。

• node()方法会以O(n/2)的性能去获取一个结点

  • 如果索引值大于链表大小的一半，那么将从尾结点开始遍历

    这样的效率是非常低的，特别是当 index 越接近 size 的中间值时。

  参考文档/图解

  ​ LinkedList同时实现List和Deque接口，所以即可以当一个双端队列使用，也可以当List使用。

  jdk1.8后支持Spliterator迭代器。

线程安全的子类（CopyOnWriteArrayList、Vector，stack）

• CopyOnWriteArrayList (@since 1.5 Doug Lea) –> JMM

  /**
   * @since 1.5
   * @author Doug Lea
   * @param <E> the type of elements held in this collection
   */
  public class CopyOnWriteArrayList<E>
      implements List<E>, RandomAccess, Cloneable, java.io.Serializable {     
        final transient ReentrantLock lock = new ReentrantLock();//采用锁
        private transient volatile Object[] array;//不参与序列化的可见数组
        //其他线程对集合元素数组的修改，能够在其他线程的每次访问都是最新值
        public CopyOnWriteArrayList() {
            setArray(new Object[0]);
        }
        ...
  }
  

  ​ 俗称读写ArrayList，线程安全的ArrayList版本，其所有写操作都是基于底层数组的副本操作，成功后再替换底层数组，可以理解为基于”snapshot” array的并发，适用于读多写少的并发环境。

  1）采用”snapshot” iterator，在遍历过程中，底层数组是不会修改的，不存在并发干扰，不会抛出ConcurrentModificationException异常；

  2）遵守内存一致性：一个线程中先于“某元素添加到CopyOnWriteArrayList”的操作happen-before另一个线程中后于“从中获取或删除该元素”的操作。

  • 主要通过3点保证线程安全：
    • 修改方法（add、set、remove等）都通过集合属性一个ReentrantLock进行同步，先获取锁，才能执行变更操作。但是通过ReentrantLock进行同步只是能保证线程的安全，并不能保持时间上的有序和正确，因为先申请锁然后进入休眠等待的线程，并不一定是最先获取锁的线程，所以，会在时间顺序看，对集合的修改是无序的。
    • 对象数组用volatile修饰，其他线程对集合元素数组的修改，能够在其他线程的每次访问都是最新值。
    • 在对集合元素数组进行修改时，是先拷贝之前的元素数组出一个新元素数组，在新的元素数组上进行修改，修改完毕后在用元素数组替换旧的元素

  这样的数组，对内存消耗很大。

  ​ 第一个点已经说了修改集合元素的方法都加了锁，为什么这里获取锁后对集合元素的修改，还要通过拷贝数组的方式？

  ​ 因为拷贝出来的新数据修改完毕后赋予CopyOnwriteArrayList,数据存储的对象数组地址就更改了，已经创建的Iterator对对象的数组的引用因为是final修饰的，所以还用的是旧的对象数组地址，所以这样就可以保证已经创建的Iterator不受其他线程修改操作的影响。

  jdk1.8后支持Spliterator迭代器。

• Vector (@sinc 1.0)

  List接口和RandomAccess接口的集合类，通过方法上添加synchronized 同步标识，来保证线程安全。

  /**
   * @author  Lee Boynton
   * @author  Jonathan Payne
   * @see Collection
   * @see LinkedList
   * @since   JDK1.0
   */
  public class Vector<E>
      extends AbstractList<E>
      implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  {
  	//无参构造函数，默认大小为10
      public Vector() {
          this(10);
      }      
      /**
       * The maximum size of array to allocate.
       * Some VMs reserve some header words in an array.
       * Attempts to allocate larger arrays may result in
       * OutOfMemoryError: Requested array size exceeds VM limit
       */
      private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//最大的容量空间      
      private void grow(int minCapacity) {
          // overflow-conscious code
          int oldCapacity = elementData.length;
          int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                           capacityIncrement : oldCapacity);//不指定扩容大小，默认是当前容量的两倍
          if (newCapacity - minCapacity < 0)
              newCapacity = minCapacity;
          if (newCapacity - MAX_ARRAY_SIZE > 0)
              newCapacity = hugeCapacity(minCapacity);
          elementData = Arrays.copyOf(elementData, newCapacity);
      }
  	...
  }
  

  ​ 如果一个线程创建了Iterator，并进行遍历，那么另一个线程对Vector数据存储的修改都会让Iterator抛出 ConcurrentModificationException异常。如果创建Vector实例时不指定每次扩容大小，默认为当下容量的两倍。

• Stack

  ​ 一个先进后出的集合，继承自Vecoter类，所以包含不属于栈操作insert和remove，它是线程安全的，因为stack自身的pop、peek、search是用synchronized修饰的同步方法，而push是自己调用线程安全的vector的addElement方法。

  /**
   * @author  Jonathan Payne
   * @since   JDK1.0
   */
  public class Stack<E> extends Vector<E> {
      ...
  }
  

  ​ 如果在想使用先进后出这种数据集合的话，建议使用ConcurrentLinkedDeque，在一端插入和删除元素，性能会比Stack好，因为它的同步策略是通过CAS和多重检查机制的无锁策略，比Stack这种在方法前加synchronized进行同步的要高效。

参考文档：

https://blog.csdn.net/pml18710973036/article/details/78452717

https://github.com/crossoverJie/Java-Interview/blob/master/MD/ArrayList.md

https://github.com/crossoverJie/JCSprout/blob/master/MD/LinkedList.md