Java 集合之 ArrayList 源码解读

    /**
    * 序列化版本标识，序列化和反序列化时使用
    */
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认的数据容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于ArrayList空实例的共享空数组实例
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
      * 用于默认大小空实例的共享空数组实例。
      * 我们将DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA区别开来
      * 以便在添加第一个元素时知道要膨胀多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存放元素的数组
     * 备注：字段不设置为私有，是为了方便内部类的访问
     * 思考：为什么不是E[]呢？
     */
    transient Object[] elementData; 

    /**
     * 数组元素个数
     */
    private int size;

    /**
    * 1、创建ArrayList强制使用范型，避免使用原生类型引起类型不安全的问题
    * 2、java7之后的jdk增强了类型推导，建议使用new ArrayList<>()，最好不使用new ArrayList<E>
    */
   // 创建一个特定长度的ArrayList
   // 如果可以预估容量，请使用本方法构建实例，避免扩容时数组拷贝带来的性能消耗
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
             // 如果容量为0，则都指向同一个共享的空数组
             // 减少内存的占用
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

     // 创建一个容量为10的ArrayList
     public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    } 

     // 使用Collection的实现比如Set,List创建一个ArrayList
     // 通常是Collection的实现进行相互转换
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray返回类型不一定Object[],具体见https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-6260652
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 使用空数组替换
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

添加可以分为两种：单个添加（添加特定元素）、批量添加（添加集合）。

单个添加

流程

    /**
      * 在ArrayList结尾添加元素
      */
    public boolean add(E e) {
        // 根据size处理容量
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        // 如果使用ArrayList()创建，默认容量=DEFAULT_CAPACITY=10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // minCapacity为此时elementData必须的最小长度
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        // 修改次数+1，用于fail-fast处理
        modCount++;
        // 如果minCapacity大于elementData的长度，则进行扩容处理
        if (minCapacity - elementData.length > 0)
            // 扩容，可能会引起溢出问题
            grow(minCapacity);
    }
    // ArrayList动态扩容机制的核心
    private void grow(int minCapacity) {
        // 可能存在整型溢出
        int oldCapacity = elementData.length;
        // 容量默认扩大1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            // 可能1：newCapacity<0整型溢出
            // 可能2：newCapacity<minCapacity
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 数组深拷贝
        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;
    }

    /**
      * 在ArrayList特定位置添加单个元素
      * 思考：add(E e)没有调用add(int index, E element)，个人猜测是出于性能的考虑
      * 毕竟基于数组进行插入操作可能存在性能问题
      */
    public void add(int index, E element) {
        // 检查位置是否合法
        rangeCheckForAdd(index);

        // 跟add(E e)中处理方式类似
        ensureCapacityInternal(size + 1); 
        // 将elementData中位置为index位置及其后面的元素都向后移动一个下标（底层是native方法，使用cpp直接操作内存。）
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

批量添加

    //
    public boolean addAll(Collection<? extends E> c) {
        // 集合转化成数组
        Object[] a = c.toArray();
        int numNew = a.length;
        // 跟add(E e)中处理方式类似
        ensureCapacityInternal(size + numNew); 
        // 将集合内的元素复制到elementData中，覆盖[size, size+numNew)的元素
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        // 检查位置是否合法
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew); 

        int numMoved = size - index;
        if (numMoved > 0)
            // 将elementData中位置为index及其以后的元素都向后移动numNew个位置
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);

        // 将集合内的元素复制到elementData中，覆盖[index, index+numNew)的元素 
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

删除可以分为两种：单个删除（删除特定元素、特定下标）、批量删除（删除集合中的元素）、批量保留（批量删除除集合外的元素）、清空。

单个删除

    // 删除ArrayList中第一次出现的特定元素
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                // 比较对象时依赖equals方法
                // 因此类型变量E对应的类注意重写equlas方法
                // 重写时注意遵守规范，具体参考effective java第三版的第10、11两条规则
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    // 根据下标删除元素
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将elemenData中index+1及其后面的元素都向前移动一个下标
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 根据上一步的操作, size-1位置的对象向前移动了一个下标
        // 如果没有elementData[--size]==null，可能会导致内存泄漏
        // 试想，ArrayList被add了100个对象，然后被remove了100次。按照GC的机制来说，100个对象应该可以被GC掉（假设没有对象对象），但是由于还存在ArrayList的实例引用，对应的100个对象就无法删除
        elementData[--size] = null; 
    }

    // 根据下标删除元素
    // 注意：java5后引入自动装箱、拆箱的机制，因此产生了一个有趣的问题：
    // 当类型变量为Integer的ArrayList调用remove时，可能调用remove(Object)，也可能调用remove(Index)
    // 一定要注意测试是否符合自己的预期
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        // 如果被删除元素不是ArrayList的最后一个元素
        if (numMoved > 0)
             // 对应下标之后的元素向前移动一个下标
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 最后一个元素只为null，方便GC
        elementData[--size] = null; 

        return oldValue;
    }

批量删除

    // 批量删除ArrayList和集合c都存在的元素
    public boolean removeAll(Collection<?> c) {
        // 非空校验
        Objects.requireNonNull(c);
        // 批量删除
        return batchRemove(c, false);
    }

    private boolean batchRemove(Collection<?> c, boolean complement){
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    // 把需要保留的元素前置
                    elementData[w++] = elementData[r];
        } finally {
            // 即使c.contains抛异常，也要保持跟AbstractCollection行为的兼容性
            // 备注：ArrayList重写了AbstractCollection中的removeAll方法，removeAll调用了batchRemove
            if (r != size) {
                // 备注1：可能是上面的for循环出现了异常
                // 备注2：可能是其它线程添加了元素。
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                for (int i = w; i < size; i++)
                    // 跟fastRemove(int index)里面的操作类似，防止内存泄漏
                    elementData[i] = null;
                // 思考：为什么addAll的modCount+1，而removeAll的modCoun+size-w
                // 个人以为modCount只是做标记做了结构的修改并且用来做校验。
                // 因此+1，+2 +size-w并没有本质区别
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

 // 思考：上面是按照元素进行批量删除，如何按照下标区间进行批量删除呢？

批量保留

    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        // 批量保留
        return batchRemove(c, true);
    }

清空

    public void clear() {
        modCount++;
        // 清空ArrayList里面所有的元素
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

更改

    // 修改特定下标的值
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

查找

    // 返回元素第一次出现的下标
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    // 返回最后一次出现的位置
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

遍历方式

ArrayList可以通过for、foreach、foreach-lambda、iterator进行遍历，iterator又可以分为Iterator（只能按照index从0到size进行遍历）、ListIterator（可以按照index从小到大进行遍历，也可以从大到小进行遍历）、Spliterator（并行遍历，充份发挥多核优势），下面依次进行演示。

        List<String> strList = new ArrayList<String>(4);
                   strList.add("1");
                   strList.add("2");
                   strList.add("3");

        // for遍历
        for (int i = 0; i < strList.size(); i++) {
            System.out.println(strList.get(i));
        }

        // foreach
        // 备注：只要实现Iterable接口，就能使用foreach
       for (String s : strList) {
            System.out.println(s);
       }

       // foreach-lambda遍历
       strList.forEach(System.out::println);

       // iterator遍历
       Iterator<String> iterator = strList.iterator();
       while (iterator.hasNext()){
            String str = iterator.next();
            System.out.println(str);
            // 下一次出现ConcurrentModificationException
            // 问题是因为list的iterator方法返回的是ArrayList的内部类Itr
            // Itr里面的expectedModCount会与ArrayList的modCount进行比较
            // 剩下的就不言而喻
            strList.remove(str);
            // 进行iterator遍历时，如果进行remove等操作，调用iterator的方法
            // 而不是ArrayList的方法
           //  iterator.remove();
      }

      // ListIterator可以进行顺序、逆序遍历，可以指定index位置开始遍历
      ListIterator<String> iterator = strList.listIterator();
      while (iterator.hasNext()){
          System.out.println(iterator.next());
      }
      iterator = strList.listIterator(strList.size());
      while (iterator.hasPrevious()){
          System.out.println(iterator.previous());
          iterator.remove();
      }

      // 使用并行遍历，可以将元素放在不同的迭代器进行并行遍历
      Spliterator<String> spliterator = strList.spliterator();
      // split，分而治之，类似算法里面的分治
      Spliterator<String> otherSpliterator = spliterator.trySplit();
      spliterator.forEachRemaining(System.out::println);
      otherSpliterator.forEachRemaining(System.out::println);

序列化

ArrayList的序列化没有直接序列化elementData，而是根据size序列化包含的元素，忽略数组中的其它位置，提高效率并节省空间 。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // fail-fast，后续判断是否有并发处理
        int expectedModCount = modCount;
        // 序列化没有标记为static、transient的字段，包括size等。
        s.defaultWriteObject();

        // 没有意义，可以忽略
        s.writeInt(size);

        // 序列化元素
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            // ArrayList被并发处理，发生结构性修改
            throw new ConcurrentModificationException();
        }
    }
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // 反序列化没有标记为static、transient的字段，包括size等
        s.defaultReadObject();

        // 可以忽略，跟writeObject里面的方法对应
        s.readInt(); 

        if (size > 0) {
            // 数组扩容
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // 反序列化元素并填充到数组中
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

排序

        List<String> strList = new ArrayList<String>(4);
                   strList.add("1");
                   strList.add("2");
                   strList.add("3");

     // 可以使用以下三种排序方式
     Collections.sort(strList);
     Collections.sort(strList, String::compareTo);
     strList.sort(String::compareTo);

     //java8 新增的排序方法
     public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        // 底层使用合并排序算法进行排序
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

转化数组

    public Object[] toArray() {
        // 直接复制ArrayList的elementData
        return Arrays.copyOf(elementData, size);
    }

    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // 利用反射生成特定类型的数组并复制
            // 备注：但是不知道为什么toArray的类型变量T跟ArrayList的不一致
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
   }
   // 另外，除了根据ArrayList转化成数组，同样可以根据Arrays的asList将数组转换成List
   // 备注：Arrays是数组操作的util类，可以进行排序、查找、复制、遍历等
   // 注意：asList方法返回的私有静态内部类ArrayList，静态内部类ArrayList跟java.util.ArrayList不同
   // 注意：静态内部类ArrayList没有重写java.util.AbstractList的remove、add等方法，默认实现是直接抛UnsupportedOperationException，因此调用会报错
   List<String> strList = Arrays.asList("1", "2", "3");

线程安全

开头说过，ArrayList并不是线程安全的集合，源码剖析也展示了ArrayList通过modCount以及fali-fast机制去避免一定程度的线程安全问题，那么我们如何保证ArrayList的线程安全呢？其实，我们可以通过以下方案实现：

• 使用Vector代替ArrayList。

• 使用 Collections.synchronizedList包装ArrayList，然后操作包装后的list即可。

• 使用CopyOnWriteArrayList代替ArrayList。

• 在使用ArrayList时，应用程序通过同步机制去控制ArrayList的读写，不建议。

前面提过，ArrayList是一个查询为主的数据结构，本身不适合修改频繁以及并发修改的场景。如果需要并发操作，可以使用上面的方案，但是它们都会有一定的瓶颈，或许我们更换其它的集合类更合适，比如线程安全的队列。

三、 总结

前面通过注释剖析了ArrayList的源码实现，但是能力有限，不能保证分毫不错，面面俱到。因此，希望本文能够抛砖引玉，给大家更多的启发，引导大家多到底层看看。

四、 彩蛋

其实这不是一个彩蛋，而是自己在阅读集合类源码经常碰到的一个问题。ArrayList继承了AbstractList并实现了List接口，但是AbstractList也实现了List接口，jdk为什么要这样设计呢?

参考文章：

1、 ArrayList集合源码

https://www.cnblogs.com/zhangyinhua/p/7687377.html

2、 深入分析Java的序列化与反序列化

https://www.hollischuang.com/archives/1140