ArrayList源码分析

整体介绍

ArrayList实现了List接口，是一个常见的集合类,它有一下特点：

• 是顺序容器，即元素存放的数据与放进去的顺序相同，
• 允许放入null元素，
• 底层通过数组实现。
• 添加元素而容量不足时，可自动扩充底层数组的容量。
• 除该类未实现同步外，其余跟Vector大致相同。
• 操作时间复杂度分别为：
  • size,isEmpty,get,set,iterator,listIterator方法运行时间为常量时间
  • add方法运行为摊还常量时间，也即增加n个元素的时间为O(n)
  • 其他的操作运行时间大致为线性时间，常数因子相较于LinkedList更小。

摊还时间是一个操作的平均代价，可能某次操作代价很高，但总体的来看也并非那么糟糕；add方法是摊还常量时间与底层数组容量自动扩充有关

image.png

源码分析

成员变量

    /**
     * 初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 当ArrayList的空实例,用于无参数初始化
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * ArrayList的底层数组
     * 泛型只是编译器提供的语法糖所以这里的数组是一个Object数组
     * ArrayList的容量就是elementData.length
     * 当ArrayList为空时,elementData == EMPTY_ELEMENTDATA
     * 当第一个元素加入时elementData.length == DEFAULT_CAPACITY
     * transient 说明这个数组无法序列化。
     */
    private transient Object[] elementData;

    /**
     * ArrayList包含的元素数量,与容量不同.
     */
    private int size;

    /**
     * 数组最大容量
     * 一些虚拟器需要在数组前加个头标签，所以减去8 。 
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 这个变量并不是ArrayList里面定义的,而是继承自父类AbstractList
     * ArrayList在使用Iterator时发生不同步会抛出错误就是依靠了这个变量
    (虽然不可靠,想要可靠的同步保证用
    List list = Collections.synchronizedList(new ArrayList(...))
    或
    concurrent包下的CopyOnWriteArrayList
    或
    用synchronized进行一层代理)
     * add和remove方法都是有modCount++.
     * 下面再具体说说modCount的作用
     */
     protected transient int modCount = 0;

get()

get()方法本身很简单,不涉及数组的容量扩充,除了检查下标范围以及类型转换,与一般的数组get()操作没区别

   public E get(int index) {
        //检查是否越界,
        //由于java数组本身就会检查是否越界,所以这里只是检查是否超过了size,
        //要知道数组的大小大于size,index大于size并不会触发数组越界.
        rangeCheck(index);
        return elementData(index);
    }
    
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        //对元素进行类型转换,底层储存是Object,但返回是E.
        return (E) elementData[index];
    }

set()

set()方法也很简单,不涉及数组的容量扩充,除了检查下标范围,与一般的数组set()操作没区别

    public E set(int index, E element) {
        //在get()中提到的,检查越界问题.
        rangeCheck(index);
        //直接用element替换elementData[index]
        //赋值到指定位置，复制的仅仅是引用
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

add()

• 如果不算入容量扩充的耗费,add()方法运行时间为常量时间.但是可能某次add()触发了容量扩充,那么那次操作的运行时间为线性时间.所以add()的运行时间为摊还常量时间,即n次操作的时间为O(n).

• add()会触发modCount++

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     *从这个方法可知第一次add元素,初始容量为DEFAULT_CAPACITY,即10
     */
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    /**
     *add()的modCount++来源于这里
     *当新容量大于当前容量时,触发容量扩充,即调用grow方法.
     */
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     *ArrayList实现容量自动扩充是依靠了这个方法.
     *新容量为原容量的1.5倍
     *耗费时间为O(n),因为需要复制原来的元素到扩充后的数组.
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //每次扩充,新容量为原容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // //扩展空间并复制
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

remove

• remove运行时间为O(n),因为ArrayList底层实现为数组,所以删除元素后,需要移动之后的元素.
• 除了越界检查,与一般数组的remove没有区别
• 在remove后并不会影响数组容量
• remove会触发modCount++

    public E remove(int index) {
        rangeCheck(index);

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

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
       //这里清除了elementData[size]的引用,
       //因为假如不清除引用,那么ArrayList就会一致保留那个对象
       //GC不能清除仍被持有引用的对象
        elementData[--size] = null;

        return oldValue;
    }

序列化

• 在上面成员变量那里提到了Object[] elementData用了transient关键字,无法序列化,这里ArrayList复写了readObject和writeObject方法,实现底层数组的序列化.
• 复写的writeObject用modCount保证了当发生不同步问题时抛出错误(虽然不可靠)
• 关于序列化的知识可以看我转载的<<深入理解Java对象序列化>>

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // 记下方法开始时的modCount
        int expectedModCount = modCount;
        //将没有transient关键字的成员变量写入
        s.defaultWriteObject();

        //这里写入数组的容量,但是把数组元素的数量size视为容量,
        //而不用原来的容量elementData.length
        s.writeInt(size);

        // 将底层数组的元素依次写入
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        //与之前记下的modCount对比,看是否有其他线程操作了ArrayList,有则抛出错误.
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // 将没有transient关键字的成员变量读入
        s.defaultReadObject();

        // 将数组容量读入,
        //但是如上面writeObject所写把size视为了数组容量,所以这里没有实质的作用
        s.readInt(); // ignored

        if (size > 0) {
            // 扩充数组大小
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // 把数组元素一次写入
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

迭代器

ArrayList用iterator()可以返回迭代器.

• 实现了Iterator<E>接口;private class Itr implements Iterator<E>
• 当有多个线程同时操作ArrayList,使用迭代器可以抛出错误,避免发生不同步(这里就是用了modCount,用法与writeObject()的差不多)
• 迭代器使得对容器的遍历操作完全与其底层相隔离，可以到达极好的解耦效果。

iterator()

    public Iterator<E> iterator() {
        //使用构造函数,返回一个新的迭代器
        return new Itr();
    }

迭代器成员变量

        int cursor;       // 下一个返回的元素的下标
        int lastRet = -1; // 上一次返回的元素的下标,初始为-1
        //记下创建迭代器时的modCount,用于之后的同步检查
        int expectedModCount = modCount;

hasNext()

hasNext()用于检测是否有下一个元素返回,实现很简单.

        public boolean hasNext() {
            return cursor != size;
        }

checkForComodification()

• 这个方法是迭代器可以在多个线程操作时抛出错误(fail-fast机制)的关键方法
• 下面的remove和next都调用了这个方法
• 实现很简单,对比modCount,如果不一致,则说明有其他线程也在用ArrayList,抛出错误.

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

next()

• next()方法的实现很简单,代码写的很清楚
• next()在内部做了很多安全检查,保证了使用迭代器的安全性
• next() 调用了checkForComodification(),使用了fail-fast机制

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            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];
        }

remove()

• 迭代器的remove()方法内部是调用了ArrayList的remove()方法
• remove() 调用了checkForComodification(),使用了fail-fast机制

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

后记

• ArrayList的源代码写的很好,注释也很清晰,我在这篇分析里面有很多内容其实都是从注释里翻译,或者加了点自己的理解.
• 这里只是挑了几个我觉得重要的地方做了分析,其余的推荐直接看源代码