ArrayList源码解析&ConcurrentModificationException

「爱情、让人受尽委屈。」 2022-05-15 01:11 219阅读 0赞

最近在写一个sdk的时候，没有考虑到多线程环境下，忽略了对同一个list存在同时进行排序的case，造成线上会出现ConcurrentModificationException的错误，因此抽个时间看了一下ArrayList的源码，总结了几个比较有意思的地方。

## ArrayList实现了几个接口？ ##

List<E>, RandomAccess, Cloneable, java.io.Serializable 4个接口

我看到RandomAccess比较好奇，打开它里面是空的，什么方法都没有，为什么需要一个这样的接口呢，后来找找资料发现 RandomAccess只是一个标记接口，用于标明实现该接口的List支持快速随机访问，主要目的是使排序算法能够选择更加 合适的算法，LinkedList就没有这个接口，因此排序算法在对ArrayList和LinkedList排序时使用的是不同的算法

## ArrayList包含了几个属性？ ##

private static final long serialVersionUID = 8683452581122892189L; // 这就是序列化的版本号
    
    private static final int DEFAULT_CAPACITY = 10; // 默认的大小
    
    private static final Object[] EMPTY_ELEMENTDATA = {}; // 长度为0的空数组 
    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空数组
    
    transient Object[] elementData; // 我们都知道ArrayList是用数组实现的，这就是本源
    
    private int size; // list的大小

这里比较有意思的是EMPTY\_ELEMENTDATA和DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA两个的空数组，都是空数组，为什么要定义2个，这不是多余吗？其实不是，EMPTY\_ELEMENTDATA可以理解为你新建ArrayList的时候指定了初始大小就是0，DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA则是新建的时候没有指定初始大小，这2个数组会影响动态扩展的逻辑，下面一个点会介绍到。

ArrayList<Integer> t = new ArrayList(0); //EMPTY_ELEMENTDATA
    ArrayList<Integer> t = new ArrayList(); //DEFAULTCAPACITY_EMPTY_ELEMENTDATA

## ArrayList怎么动态扩展的？ ##

就如上所说，你可能开始就定义了一个空list, 这个时候你向list中新增一个元素，看看添加元素的源码：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 扩展数组大小确保足够大
        elementData[size++] = e; // 放元素
        return true;
    }

这个函数看起来很简单，核心其实是扩展容量的函数ensureCapacityInternal，看看他是怎么做的

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
        }
    
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

这个时候你就能看出DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA和EMPTY\_ELEMENTDATA的区别了

EMPTY\_ELEMENTDATA：list的变化就会是0，1，2，3，4，5，6.....

DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA: list的变化就是：0，10，11，12....

这个只是决定数组的大小minCapacity，真正扩容的逻辑是在grow方法中

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 每次都扩展1.5倍，就是它
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0) // 当然还有最大的限制
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

## ArrayList什么时候会出现ConcurrentModificationException？ ##

说起ConcurrentModificationException，就不得不说modCount, 它是存在AbstractList中的一个属性，它记录了list被修改的次数，因此你会发现添加、删除、排序等操作的地方都会有modCount++的代码。

假如你在ArrayList的源码中搜ConcurrentModificationException，就会发现很多方法开始先用一个变量expectedModCount保留modCount的值，然后做一些操作，最后再对比expectedModCount和modCount的值，如果不一致就会抛ConcurrentModificationException，因此这个逻辑其实在检查函数的运行的过程中是否有其他的线程修改了list。

顺着这个思路，我就写了2个线程，一个线程在遍历list, 一个线程在添加元素到list，最后遍历的线程会发现在它遍历的过程中有一个线程修改了list, 马上就抛出ConcurrentModificationException。

public static void main(String[] args) throws InterruptedException {
        ArrayList<Integer> t = new ArrayList();
        List<Thread> group = new ArrayList<>();
        Thread addThread = new Thread(() -> addItem(t));
        addThread.start();
        Thread sortThread = new Thread(() -> Collections.sort(t));
        sortThread.start();
        addThread.join();
        sortThread.join();
        t.sort(null);
    }
    
    private static void addItem(List t) {
        for (int i = 0; i < 100000; i++) {
            t.add(i);
        }
    }

## 使用Vector就能避免ConcurrentModificationException？ ##

有人会说ArrayList是线程非安全的，因此才会有ConcurrentModificationException， Vector是线程安全的，每个方法都是加锁的，因此就不会有ConcurrentModificationException，是这样吗？

不完全是！！ 如果你是通过iterator遍历的话就不一定了

public synchronized Iterator<E> iterator() {
        return new Itr();
    }
    
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
        public boolean hasNext() {
            // Racy but within spec, since modifications are checked
            // within or after synchronization in next/previous
            return cursor != elementCount;
        }
        // 省略后面的代码
    }

可以看到每次遍历的返回的iterator都是new出来的，每new出来后，expectedModCount是new的那个时刻的modCount，意思是expectedModCount是私有的变量，这个时候另外一个线程随便一修改，就会报错了。

## 如何解决ConcurrentModificationException ##

ConcurrentModificationException出现的根本原因是2个线程同时改了同一个list，因此如果没有特殊需求可以使用CopyOnWriteArrayList代替List， 或者直接拷贝一个统一的list：

List<XXX> copyRules = new ArrayList<>(list);

欢迎关注我的个人的博客[www.zhijianliu.cn][], 虚心求教，有错误还请指正轻拍，谢谢

[www.zhijianliu.cn]: http://www.zhijianliu.cn/