Java源码解读——ArrayList（一）

为了提高自己的Java开发能力，我也向高手、牛人学习，去解读源码。自己底子差了点，不过看个源码还是没问题的。第一站ArrayList。

源码为Java 1.7的源码

ArrayList是一个实现可变长数组，继承AbstractList类，实现所有的List接口，还实现了RandomAccess、Cloneable、Serializable接口。ArrayList不进行同步，除此之外基本和Vector等同。

 

1、成员变量

 

private transient Object[] elementData;

elementData用于保存数据的数组。

 

private int size;

 size为ArrayList内的数据数量，但并不是elementData的长度。

 

2、构造方法

    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    public ArrayList() {
        this(10);
    }

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

  第一个是根据指定长度建立List，第二个是根据默认长度建立List，第三个根据传入Collection子类实例创建List。通过第三个实例看到Collection子类都会实现toArray()方法，可以看出至少很多Collection子类依赖于数组来实现（还没看过其他的集合实现，这只是我的妄言而已）。

 

3、add方法

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

 该方法在数组最后添加一个元素。ensureCapacityInternal方法提供了ArrayList的自增长实现，以确保elementData有足够的长度来容纳新进入的元素（后面介绍自增长的实现）。

 

    public void add(int index, E element) {
        rangeCheckForAdd(index);

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

 该方法是在第i个位置插入一个元素。rangeCheckForAdd方法用于检查index是否越界，代码如下：

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

System.arraycopy方法使用native修饰符（这个修饰符第一次看到，谷歌了下，大致是说这个修饰的方法是通过底层实现的），效率自然高。arraycopy如果对同一个数组进行操作时，会首先把从源部分拷贝到一个临时数组，在把临时数组的元素拷贝到目标位置。值得注意的是，如果数组内不是基本类型，System.arraycopy的拷贝过来的也只是个引用而已。

 

4、remove方法

    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] = null;

        return oldValue;
    }

 删除指定位置的元素，并返回删除的元素。以前还真没注意过删除时候还返回删除的元素。rangeCheck方法用于检查越界，代码如下：

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

  modCount用于记录ArrayList的结构性变化的次数，add()、remove()、addall()、removerange()及clear()方法都会让modCount增长。add()及addall()方法的对modCount的操作在ensureCapacityInternal中。

numMoved用于检查删除的元素是否是最后ArrayList的最后一个元素（不一定是数组elementData的最后一个）。如果不是最后一个，则用arraycopy移动数组，最后将数组size-1处赋值为空。

 

    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++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

 删除与Object o相同的第一个元素。这里fastRemove方法，从代码来看和remove(int index)类似。

    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;
    }

 

5、addAll方法

   //将Collection c内的数据插入ArrayList中
   public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    //将Collection c中的数据插入到ArrayList的指定位置
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(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;
    }

这两个方法都会调用ensureCapacityInternal方法使数组能够容纳下新的数据。后一个方法会判断是否是在数据最后插入，如果是则和第一个方法相同，如果不是，则先使用arraycopy移动数组。

 

6、removeAll和retainAll

删除或保留ArrayList中包含Collection c中的的元素，这两个方法都依赖batchRemove(Collection<?> c, boolean complement)实现。

 

7、get和set

前者是获取元素，后者是替换某个位置上的元素，然后返回被替换的元素。这两个都用rangeCheck做越界检查。set方法不进行自增长，也就说替换的元素必须是size内的。

 

 

 

发现感觉快把源码复制过来了。唉，以后不能这么写