ArrayList源码解读

ArrayList特点总结

• ArrayList实现List接口，底层是使用数组实现的，可以根据元素的个数进行动态扩容

• ArrayList线程不安全而Vector是线程安全的，多线程环境下，可以考虑使用

  List list = Collections.synchronizedList(new ArrayList(...));

• 元素可以是null

• 查询修改元素的时间复杂度O(1),而插入删除为O(n)

• 构造方法 有3种 一种是指定list的容量 一种是无参构造方法 还有一种是使用一个Collection为参数

• 扩容方法 见grow方法 int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容当前数组长度的一半 1.8之前是 newCapacity = (oldCapacity * 3)/2+1

源码分析

为了代码的简洁，将非核心的代码去掉了，这里还是想说英文的注释是最好的学习材料，有条件的还是应该多看源码中的英文注释

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{  
 //实现List接口
 //实现RandomAccess接口，可以进行随机访问
 //实现Cloneable接口，可以被clone
 //实现序列化接口

    private static final long serialVersionUID = 8683452581122892189L;

    //默认的初始容量是10，也就是数组的大小默认是10，面试时会问问
    private static final int DEFAULT_CAPACITY = 10;

    //两个空的数组对应不同的构造方法
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量的空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

     //存储ArrayList元素的数组
     //任何一个空的ArrayList(使用elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA进行初始化的，
     //在第一个元素被add的时候都会自动扩容到DEFAULT_CAPACITY）
     //使用transient时为了不被序列化
    transient Object[] elementData;

    //ArrayList中元素的个数
    private int size;


    //构造方法
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) { //初始化容量
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { //当初始化容量为0的时候 elementData = {}
            this.elementData = EMPTY_ELEMENTDATA;
        } else { //初始化容量<0时 抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    //无参构造方法，elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA 当第一个元素被添加的时候扩容到10
    //jdk1.7的时候 好像是this(10)
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }


    //构造方法 参数是一个Collection对象
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray(); //将c转成数组对象
        if ((size = elementData.length) != 0) { 
            // 判断elementData的类型 因为c.toArray不一定返回的Object[] 见
            // http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 替换空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }


    //将数组中的元素剔除，这样可以使ArrayList实例占用的存储空间尽可能小
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }


     //判断当前ArrayList的容量是否够用
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0 : DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //minCapacity为默认大小10和参数指定大小的较大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            //如果参数minCapacity比数组长度长就进行扩容
            grow(minCapacity);
    }

   //用来扩容的函数
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length; //获取当前数组长度
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容当前数组长度的一半 1.8之前是 newCapacity = (oldCapacity * 3)/2+1
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;   //如果新容量还是比指定的minCapacity小就将容量扩充到minCapacity
        if (newCapacity - MAX_ARRAY_SIZE > 0) //新容量超过了Integer.MAX_VALUE - 8 可能是Integer.MAX_VALUE
            newCapacity = hugeCapacity(minCapacity); 
        // minCapacity通常是接近size的
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    //返回的是一个合理的容量值
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE; //Integer.MAX_VALUE - 8
    }

   //获取ArrayList中元素的个数
    public int size() {
        return size;
    }
    
    //判断是够为空
    public boolean isEmpty() {
        return size == 0;
    }

  
     //判断是否含有某个元素注意这种情况(o==null?e==null:o.equals(e))
     //因为ArrayList可以塞进null，所以当o是null的时候只要ArrayList中元素e也是null就返回true
     //如果o不是null的话，就是使用equals判断list中是否含有元素o
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

     //返回list中元素的下标（第一个），如果存在就返回该元素下标，如果不存在就返回-1
    public int indexOf(Object o) {
        if (o == null) { //如果元素指定的元素是null
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else { //指定的元素不为null
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i])) //循环遍历list 使用eqauls判断list中与指定元素相同的元素
                    return i;
        }
        return -1;
    }

    //获取最后一个元素o在list中的下标
    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--)
                //使用equals方法判断相同
                if (o.equals(elementData[i]))
                    return i;
        }
        //如果元素不存在返回-1
        return -1;
    }

    //clone方法
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

    //返回数组
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
     
   //返回指定index的元素
    public E get(int index) {
        rangeCheck(index); //index合法性检查

        return elementData(index);
    }

    //根据index对list元素进行赋值
    public E set(int index, E element) {
        rangeCheck(index); //index越界检查

        E oldValue = elementData(index); //返回旧值
        elementData[index] = element; //设置新值
        return oldValue;
    }

   //添加指定的元素到list的末尾
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 确保添加一个元素不会越界 如果是DEFAULTCAPACITY_EMPTY_ELEMENTDATA第一次添加的时候list会扩容到默认的10
        elementData[size++] = e;
        return true;
    }

   //在指定index添加元素
    public void add(int index, E element) {
        rangeCheckForAdd(index); //index越界检测

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    //删除指定index的元素并返回原先的元素
    public E remove(int index) {
        rangeCheck(index); //index下标检查

        modCount++;
        E oldValue = elementData(index); //获取原先的值

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // GC
        //返回原先的值
        return oldValue;
    }

    //删除list中出现的第一个元素o
    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判断相等
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    //私有的删除方法，在remove中调用，在这个方法中不包含越界检查和返回原来值
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; //GC
    }

    //清空列表
    public void clear() {
        modCount++;

        for (int i = 0; i < size; i++)
            elementData[i] = null; //GC
        size = 0;
    }

    //添加Collection中所有的元素到当前的list中
    public boolean addAll(Collection<? extends E> c) {
        //collection转数组
        Object[] a = c.toArray();
        //获取数组的长度 即元素的个数
        int numNew = a.length;
        //确保list内部数组容量
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //复制数组
        System.arraycopy(a, 0, elementData, size, numNew);
        //修改list 元素个数
        size += numNew;
        return numNew != 0;
    }

    //指定index向list插入Collection的所有元素
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index); //检查index

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

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

     //index越界检查，如果不合法抛出一个运行时异常，
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    // add和addAll的越界检查
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    //下标越界异常信息
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    //删除Collection中所有的元素
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

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

    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 {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }
  
}