TUNANのBlogHomeArchivesTagsCategories
多线程下的ArrayList
|Java
Word count: 2.6k|Reading time: 10 min

该篇博客不适合小白，只做针对性的api源码解析，以及适合我自身的案例研究

  1. 使用多个线程往ArrayList中添加元素

    //创建资源集合
    List<String> list = new ArrayList<String>();

    //创建30个线程添加元素
    for (int i = 0; i < 30; i++) {
        new Thread(()->{
            list.add(UUID.randomUUID().toString().substring(0,8));
            System.out.println(list);
        }).start();
    }

  2. 故障现象

    Exception in thread "2" java.util.ConcurrentModificationException

    我们知道ArrayList是线程不安全的，当多线程操作时，线程操作迭代器的同时其他线程改变了元素的值就会产生ConcurrentModificationException异常，ConcurrentModificationException是在操作Iterator时抛出的异常

  3. 故障原因

    java中的java.util包下的类全部都是快速失败的，那么为什么在多线程操作ArrayList的时候会出现ConcurrentModificationException异常呢？

    在我们的案例中，每个线程添加一次元素我们就打印一次集合中的元素，通过源码追踪，得出下面的内容

    1. 打印内容，经过第二行代码，String调用了valueOf(x)方法

      public void println(Object x) {
          String s = String.valueOf(x);
          synchronized (this) {
              print(s);
              newLine();
          }
      }

    2. ValueOf(Object x)方法是把Object类型的对象x转换成String类型，判断不为null，进入obj也就是我们的集合

      public static String valueOf(Object obj) {
          return (obj == null) ? "null" : obj.toString();
      }

    3. 集合中的toString方法定义在了AbstractCollection类中，我们的错误出现在了 E e = it.next();获取元素这里，继续追踪错误。

      public String toString() {
          Iterator<E> it = iterator();	//创建迭代器对象
          if (! it.hasNext())		//判断集合是否为空
              return "[]";
            
          StringBuilder sb = new StringBuilder();	//创建StringBuilder动态构造字符串
          sb.append('[');	
          for (;;) {		//死循环
              E e = it.next();	//获取元素 E ==> String 是传进来的泛型
              sb.append(e == this ? "(this Collection)" : e);	//添加元素
              if (! it.hasNext())	//循环换了就返回集合的字符串类型
                  return sb.append(']').toString();
              sb.append(',').append(' '); //这里是没有return之前会进来，添加分隔符
          }
      }

    4. 下面是迭代器中的next()方法

          	// 用来记录List修改的次数：每修改一次(添加/删除等操作)，将modCount+1
          	protected transient int modCount = 0;
            
      int cursor;       // 下一个要返回的元素的索引
            int lastRet = -1; // 最后一个返回元素的索引;-1:没有
            int expectedModCount = modCount;	//这是非常关键的一步，把modCount赋值给expectedModCount，用来在迭代器遍历时next()和remove()方法中做校验
            
      public E next() {
                checkForComodification();	//每次添加元素前，都检查一次modCount和expectedModCount是否相等，如果不相等就直接返回ConcurrentModificationException异常，产生快速失败,多线程环境下这里通不过
                int i = cursor;	
                if (i >= size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }
      final void checkForComodification() {
          if (modCount != expectedModCount)	//多线程环境下，modCount和expectedModCount不相等
              throw new ConcurrentModificationException();
      }

    5. 那么在多线程环境下是如何让modCount != expectedModCount的呢？

      我们先看源码中是如何修改modCount 的值的(开始怼源码)

         // list中容量变化时，对应的同步函数
      transient Object[] elementData; // 保存了添加到ArrayList中的元素
      private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};	//默认是空元素
      private static final int DEFAULT_CAPACITY = 10;	//初始容量
      public void ensureCapacity(int minCapacity) {
             int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                 //元素列表不等于默认列表
                 ? 0
                 //元素列表等于默认列表，返回默认初始值10
                 : DEFAULT_CAPACITY;
      	
             if (minCapacity > minExpand) {	//传入的容量大于最小扩展容量(minExpand)，则调用ensureExplicitCapacity()方法传入minCapacity
                 ensureExplicitCapacity(minCapacity);
             }
         }
            
      //判断元素列表是否为初始的元素列表，返回默认容量10和传入的容量中较大的值
         private static int calculateCapacity(Object[] elementData, int minCapacity) {
             if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                 return Math.max(DEFAULT_CAPACITY, minCapacity);
             }
             return minCapacity;
         }
            
      //JDK1.8 中，add、addAll方法会先调用者方法判断是否需要扩容
         private void ensureCapacityInternal(int minCapacity) {
             //把元素列表和扩展的容量传入到calculateCapacity方法，做一个判断
             ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
         }
            
      //list中容量变化时，modCount+1
         private void ensureExplicitCapacity(int minCapacity) {
             //修改modCount
             modCount++;
            
             // 如果minCapacity大于elementData的长度，则进行扩容
             if (minCapacity - elementData.length > 0)
                 //调用grow扩容
                 grow(minCapacity);
         }
            
         private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
         private void grow(int minCapacity) {
             //旧容量
             int oldCapacity = elementData.length;
             //新容量=旧容量+旧容量的1/2 ==>扩容1.5倍
             int newCapacity = oldCapacity + (oldCapacity >> 1);
             //如果计算出来的新容量比传进来的容量小，则以传入的容量为准
             if (newCapacity - minCapacity < 0)
                 newCapacity = minCapacity;
             //如果新容量大于MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)，则把新容量交给hugeCapacity方法
             if (newCapacity - MAX_ARRAY_SIZE > 0)
                 newCapacity = hugeCapacity(minCapacity);	//hugeCapacity实际上是做了一次内存溢出的判断，因为MAX_ARRAY_SIZE的容量已经接近溢出的边缘
             //Arrays.copyOf()方法放入elementData的元素，并把容量扩容为newCapacity
             elementData = Arrays.copyOf(elementData, newCapacity);
         }
            
      //主要检查内存是否溢出
         private static int hugeCapacity(int minCapacity) {
             // 内存溢出
             if (minCapacity < 0) 
                 throw new OutOfMemoryError();
             return (minCapacity > MAX_ARRAY_SIZE) ?
                 Integer.MAX_VALUE :
                 MAX_ARRAY_SIZE;
         }
            
         // 添加元素到队列最后
         public boolean add(E e) {
             //判断是否需要扩容和modCount+1,以及判断内存溢出
             ensureCapacityInternal(size + 1);  
             //将元素添加到数组末尾
             elementData[size++] = e;	
             return true;
         }
            
            
         // 添加元素到指定的位置
         public void add(int index, E element) {
             //检查index的范围
             rangeCheckForAdd(index);	
      	//判断是否需要扩容和modCount+1,以及判断内存溢出
             ensureCapacityInternal(size + 1);  
             //把原数组的index位置移动到目标数组的index+1的位置,长度=数组长度-插入位置，这样就把index位置空出来了，涉及到内存操作，贼慢
             System.arraycopy(elementData, index, elementData, index + 1,
                              size - index);
             //把元素插入到数组中的index位置
             elementData[index] = element;
             size++;
         }
      //指定位置的范围检查，适用于add和addAll.
         private void rangeCheckForAdd(int index) {
             if (index > size || index < 0)
                 //throw new 下标越界异常
                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
         }
            
         // 添加集合
         public boolean addAll(Collection<? extends E> c) {
             //把集合转换成一个Object类型的数组
             Object[] a = c.toArray();	
             //获集合的长度，用作扩容和复制
             int numNew = a.length;	
             //判断是否需要扩容和modCount+1,以及判断内存溢出
             ensureCapacityInternal(size + numNew);
             //把集合从0位置开始移动到目标数组的size位置,长度就等于集合的长度
             System.arraycopy(a, 0, elementData, size, numNew);
             //计算size
             size += numNew;
             return numNew != 0;
         }
      //类似于addAll，插入的位置变了而已
      public boolean addAll(int index, Collection<? extends E> c) {}
        
            
         // 删除指定位置的元素 
          public E remove(int index) {
             //检查范围
             rangeCheck(index);
      	//修改modCount
             modCount++;
             //找出index位置的元素
             E oldValue = elementData(index);
      	//计算数组从index到size的长度，-1是为了减去index的位置
             int numMoved = size - index - 1;
             //如果计算后的长度大于0，则使用System.arraycopy复制index后的元素向前移动一位，内存操作，贼慢
             if (numMoved > 0)
                 System.arraycopy(elementData, index+1, elementData, index,numMoved);
              //size--,并赋值为null
             elementData[--size] = null; // clear to let GC do its work
      	//返回删除元素后的数组
             return oldValue;
         }
      //检查索引的范围
         private void rangeCheck(int index) {
             if (index >= size)
                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
         }
            
            
         // 快速删除指定位置的元素,和remove(int index)类似，省去了范围校验
         private void fastRemove(int index) {
             //修改modCount
             modCount++;
             int numMoved = size - index - 1;
             if (numMoved > 0)
                 System.arraycopy(elementData, index+1, elementData, index,numMoved);
             //原来这里也会有GC回收
             elementData[--size] = null;
         }
            
         // 清空集合
         public void clear() {
             //修改modCount
             modCount++;
            
             for (int i = 0; i < size; i++)
                 //这里也会有GC回收
                 elementData[i] = null;
            
             size = 0;
         }
         ...

      一遍源码读下来，发现无论是add()、remove()，还是clear()，只要涉及到修改集合中的元素个数时，都会改变modCount(全局)的值。

      由此回到next()方法中我们发现当 ‘A’ 线程正在做迭代器遍历操作时，modCount赋值给了expectedModCount，每次调用next()方法都会做一次modCount != expectedModCount的校验，此时线程 ’B‘ 进来了调用了add方法修改了modCount的值，此时modCount变成了N+1，判断为false，抛出ConcurrentModificationException异常，产生fail-fast事件 。

  4. fail-fast事件

    当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)；这时，就会抛出ConcurrentModificationException异常。与此对应的安全失败，在后面再解析。

  5. 解决方法

    经过源码解析ConcurrentModificationException异常是因为多个线程同时调用add()方法导致的，解决的办法有一下三种:

    1. 使用Vector()替代ArrayList()，但是这种方法效率低下，因为Vector()的几乎所有方法都加上了synchronized修饰符，synchronized保证了在同一时刻最多只有一个线程访问该段代码，虽然jdk1.5引入了自旋锁、锁粗化、轻量级锁和偏向锁，但还是太重，效率很低。

      List<String> list = new Vector<String>());

    2. 使用Collections.synchronizedList()包装ArrayList，但是这种方法实际上只是将原来非线程安全的ArrayList中的方法加上一个synchronized同步代码块 (哭了。。。)

      List<String> list = Collections.synchronizedList(new ArrayList<String>());
      final Object mutex;     // 对象锁
      public E get(int index) {
      	synchronized (mutex) {	//同步代码块
              return list.get(index);
          }
      }
      public E set(int index, E element) {
      	synchronized (mutex) {	//同步代码块
              return list.set(index, element);
          }
      }
      ...

    3. 第三种也是推介的一种方法就是使用java.util.concurrent包下的CopyOnWriteArrayList解决，俗称写时复制机制，是读写分离的一种实现，这种方法在后面将详细源码解析。

      List<String> list = new CopyOnWriteArrayList<String>();

  6. 优化建议

    在多线程下如果有按数据索引访问元素的情形，采用CopyOnWriteArrayList()方法

  7. ArrayList的常用API

    方法 描述
    add(E e) 将指定的元素列表的结束。
    addAll(Collection c) 追加指定集合的所有元素到这个列表的末尾，按他们的指定集合的迭代器返回。
    clear() 从这个列表中移除所有的元素。
    contains(Object o) 返回 true如果这个列表包含指定元素。
    get(int index) 返回此列表中指定位置的元素。
    iterator() 在这个列表中的元素上返回一个正确的顺序。
    remove(int index) 移除此列表中指定位置的元素。
    set(int index, E element) 用指定元素替换此列表中指定位置的元素。
    size() 返回此列表中元素的数目
    toArray() 返回一个数组，包含在这个列表中的所有元素在适当的顺序
Author: Tunan
Link: http://yerias.github.io/2019/01/02/java/2/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Java