ArrayList源码分析

基于jdk1.7源码

一、源码分析

属性

//默认的初始容量大小，为10
private static final int DEFAULT_CAPACITY = 10;
 
//Arraylist为空时，使用该共享的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
 
//用来存放元素的数组。
private transient Object[] elementData;
 
//存放的元素个数
private int size;

①DEFAULT_CAPACITY：默认初始容量为10。

②EMPTY_ELEMENTDATA：表示空数组，

Arraylist在刚创建时通常是一个空数组，不含任何元素，如果一次创建了

③elementData：是用来缓存元素的数组，该属性被声明为transient。我们知道被声明为transient的属性在序列化时会被排除掉，Arraylist在序列化(已经实现了Serializable接口)时岂不是元素全部丢失了吗？

实际上ArrayList在序列化时会调用writeObject方法，直接将size和element写入ObjectOutputStream；反序列化时调用readObject，从ObjectInputStream获取size和element，再恢复到elementData。
为什么不直接用elementData来序列化，而采用上诉的方式来实现序列化呢？原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。

④size：实际存放的元素的个数。

构造方法

    /**
     * 构造器(指定初始容量)
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
 
    /**
     * 默认构造器
     */
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
 
    /**
     * Constructs a list containing the elements of the specified collection, 
       in the order they are returned by the collection's iterator.
       用指定容器中的元素来填充构造Arraylist。元素添加的顺序是指定容器的迭代器返回的元素的顺序
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        // toArray()方法不总是返回Object[]
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

创建ArrayList时，如果使用默认构造器，则默认的初始容量值为10。也可以手动指定初始容量值，还可以用其它容器填充的方式来创建ArrayList。

注意：如果手动指定初始容量值，则该值既不能设置过大，也不能设置过小。如果过大，但元素增长过慢，则导致内存浪费。如果过小，则会造成频繁的扩容，而扩容时内部元素会进行移动，因此影响效率。所以需要根据具体的业务需求来指定合适的初始容量值。

add方法

    //添加元素到尾部
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 
        elementData[size++] = e;
        return true;
    }

添加元素之前，先使用ensureCapacityInternal确保数组有足够空间存储元素。来看看ensureCapacityInternal是如何实现的。

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
 
        ensureExplicitCapacity(minCapacity);//***
    }
 
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//***
    }
    private void grow(int minCapacity) {
     // overflow-conscious code
     int oldCapacity = elementData.length;
 
     //扩容了0.5倍容量
     int newCapacity = oldCapacity + (oldCapacity >> 1);//>>表示右移一位，相当于除以2
     
     //控制容量的上限和下限
     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);
    }

扩充了多少容量呢？

//jdk7
int newCapacity = oldCapacity + (oldCapacity >> 1)
//jdk6
int newCapacity = (oldCapacity * 3)/2 + 1;

(如果初始容量为10，JDK6扩容后为16，而JDK7扩容后为15，两者写法不同，但都大约扩容了0.5倍容量，也就是扩容到原容量的1.5倍)

这里我把jdk6中的相应代码也列出来了，两者写法略有不同。为什么jdk7会换了个写法？

其实原因很简单，因为oldCapacity直接乘以3(暴增)，很可能会造成int溢出，而jdk7中的写法则是缓慢的增加，相比要安全的多。

更多关于ArrayList和Vector扩容1.5倍的讨论请参阅：

Why does ensureCapacity() in Java ArrayList extend the capacity with a const 1.5 or (oldCapacity * 3)/2 + 1?

Logic used in ensureCapacity method in ArrayList

get方法

    public E get(int index) {
        //先检查index是否越界
        rangeCheck(index);
 
        return elementData(index);
    }

get方法非常简单，先判断下标是否越界，然后通过下标来获取元素。

remove方法

    public E remove(int index) {
        //检查index是否越界
        rangeCheck(index);
        
        modCount++;
        //暂存要删除的元素
        E oldValue = elementData(index);
        //要移动的元素个数
        int numMoved = size - index - 1;
        //如果删除位置不是末尾，进行元素的移动
        if (numMoved > 0)
            //删除位置之后的所有元素都往前挪动。
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        
            //将末尾元素设为null，元素个数减1
            elementData[--size] = null; // 【clear to let GC do its work】
 
            //返回删除的元素
        return oldValue;
    }

如果删除的是末尾的元素，直接删除即可。而如果是其它位置，则需要将删除位后面的所有元素往前移动。

注意：

1.System.arraycopy()是一个native方法。

使用此方式拷贝数组比使用for循环的方式效率要高的多。

【疑问：System.arraycopy()是深克隆还是浅克隆？】

2.elementData[--size] = null这段代码有两层意思。

①删除元素后，末位元素已经没有存在的意义了，所以将其设为null。

②如果该元素是某个对象的引用，且不存在其它对该对象的引用，则设为null以便垃圾回收器尽早进行清理工作(不保证进行回收)

注意：如果是复杂类型，容器中存放的是对象的引用，所以删除时仅仅删除的是引用，真实的对象并未删除。

remove(Object o)方法

删除首次出现在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 {//非null则用equals来比较
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

二、快速失败机制

请移步到fail-fast(快速失败/报错机制)-ConcurrentModificationException

总结

1.ArrayList底层使用对象数组实现。因为带有下标索引，所以随机访问速度快。而由于对数组的插入、移除、扩容等都需要进行元素的移动，所以相比基于链表实现的LinkedList，插入和移除操作速度慢。

插入、删除、扩容都需要进行元素的移动，是因为ArrayList底层是数组实现，数组一旦分配内存就不能发生改变，对ArrayList的插入、删除、扩容操作只是使用System.arraycopy(x…)重新生成了一个新的数组，然后将原有数组中的元素复制到新数组中。

2.ArrayList具有自动扩容机制。

我们在使用数组时通常会使用Arraylist来代替原生数组(例如int[])，这是因为ArrayList具有自动扩容机制，也就是当ArrayList中存放的元素个数达到了其容量之后，继续向其中添加元素，它会帮我们自动扩充容量。

3.ArrayList是非线程安全的。

ArrayList和Vector的比较请看Vector和ArrayList的比较

另外：需要搞清楚的问题：ArrayList(容器)中存放的是对象的引用还是对象本身？

如果是基本类型，存入的是变量的值。如果是复杂类型则存入的是对象的引用