ArrayList源码分析（基于JDK1.6）

朴灿烈づ我的快乐病毒、 2022-08-05 15:24 200阅读 0赞

最近可能要跳槽，想把Java基础再巩固一下。就先看集合框架吧。  
先从构造方法开始：

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;
            // 这里为了防止c.toArray()未正确返回Object[].class
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        }

可以看到ArrayList提供三种构造方式，其中initialCapacity表示了该ArrayList的初始化大小。通过第一个构造函数我们可以发现ArrayList内部是通过维护一个Object数组来储存数据的。而默认不提供参数的话那么该ArrayList的初始容量就为10。通过另一个现有集合来构造ArrayList，会将该集合中的元素拷贝到内部数组中去。  
需要注意的是，另一个重要的实例变量是size，这个变量用来表明当前ArrayList的实际长度（也就是实际元素的个数，并非内部数组的长度，一般内部数组的长度都会大于ArrayList的长度）

下面看ArrayList中的几个重要方法：

*  add方法

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

由于ArrayList是用数组来储存数据，那么add其实就是将e存储到数组的下一位。不过首先要保证该数组的长度要足够的大，否则就可能会溢出。这里我们也可以看到内部数组是会随着元素增加有一个自动扩容的过程的。

public void ensureCapacity(int minCapacity) {
            modCount++;
            int oldCapacity = elementData.length;
            if (minCapacity > oldCapacity) {
                Object oldData[] = elementData;
                int newCapacity = (oldCapacity * 3)/2 + 1;
                if (newCapacity < minCapacity)
                    newCapacity = minCapacity;
                elementData = Arrays.copyOf(elementData, newCapacity);
            }
        }

当数组的长度比传入的minCapacity要小时，则需要扩容。扩容为原来长度的1.5倍 + 1。如果扩容一次之后还是比minCapacity要小，那么直接扩到minCapacity。

*  get方法

public E get(int index) {
            RangeCheck(index);
            return (E) elementData[index];
        }

首先对index做一个检查，若index比ArrayList的size还要大，那么就抛出**IndexOutOfBoundsException**错误。否则，就返回数组中下标为index的元素，很简单。  
看到这里可能有些童鞋会问，为什么不需要检查**index**是否为负数呢？因为**index**为负数的话，本就会抛出异常，而对于**index**大于**size**小于底层数组的长度时，`elementData[index]`并不会报错，但是却是违反逻辑的，所以需要我们手动处理。

*  contains方法

public boolean contains(Object o) {
            return indexOf(o) >= 0;
        }

`indexOf()`，应该能想到**String**中的`indexOf()`，不难猜想到是用来得到o在数组中的下标的。看看源码来加深印象：

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

这里只是将**null**的情况特殊处理了，传入**null**也是会遍历数组进行匹配的。而对于**非null**的对象，是通过调用**equals**方法进行比较。并且返回的是第一个匹配的元素的下标。与之对应的还有一个`lastIndexOf(o)`方法用来返回最后一个匹配元素的下标（其实也就是从后向前遍历）。

*  remove方法  
    remove分为两种方式，一种是根据下标来remove，而另一种则是匹配传入的元素来remove，先来第一种：

public E remove(int index) {
            RangeCheck(index);
    
            modCount++;
            E oldValue = (E) elementData[index];
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index, numMoved);
            elementData[--size] = null; // Let gc do its work
    
            return oldValue;
        }

首先也要保证index的有效性，这个在前面讲get(index)方法的时候也讲过。  
那么既然是数组中元素的删除，且我们知道数组的内存空间分配好之后就是固定的了，那么只能新建数组并将未删除的元素拷贝过去。

System.arraycopy(elementData, index+1, elementData, index, numMoved);

这句代码的意思是，将**elementData**从**index + 1**开始，总计**numMoved**个元素，依次拷贝到前一个位置。而此时，**ArrayList**的**size**还没有变，且此时**elementData\[size-1\]**还是之前**elementData\[size-1\]**的值，所以需要将**size**减小1，并且将该位置置为**null**。后续回收该对象占用的内存空间的工作就交给**GC**来做了。

第二种remove方式：

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

逻辑不复杂，**fastRemove(index)**其实就是类似于**remove(index)**做的操作，只不过**fastRemove**不需要返回删除的对象，并且也无需**RangeCheck**。不过我倒是在想，为什么不通过**indexOf(o)**来得到**index**呢，效率上也是一样的。

*  clear()方法

public void clear() {
            modCount++;
    
            // Let gc do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }

将底层数组元素全部置为**null**，交给**GC**来回收内存，并将**size**置为0。

*  toArray方法  
    ArrayList转换为Array的方法，由于本来内部就是用数组来储存数据的，直接返回底层数组就好了：

public Object[] toArray() {
            return Arrays.copyOf(elementData, size);
        }

不过**ArrayList**中保存的数组是没有类型信息的，也就是**Object\[\]**，这在拿到之后无法强转为诸如**String\[\]**这样的形式。**ArrayList**提供了**toArray(T\[\] a)**方法来返回一个**T\[\]**：

public <T> T[] toArray(T[] a) {
            if (a.length < size)
                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**的**size**，那么直接创建一个新的数组，并且根据传入数组的类型来决定返回数组的类型。否则直接拷贝底层数组到传入的数组。若传入数组长度大于**size**，那么还要将传入数组下标为**size**的元素设置为**null**(这步我不是很理解具体用意)

*  关于**removeRange**方法  
    这是个**protected**修饰的方法：

protected void removeRange(int fromIndex, int toIndex) {
            modCount++;
            int numMoved = size - toIndex;
                System.arraycopy(elementData, toIndex, elementData, fromIndex,
                                 numMoved);
    
            // Let gc do its work
            int newSize = size - (toIndex-fromIndex);
            while (size != newSize)
                elementData[--size] = null;
        }

在哪里调用呢？一个是在AbstractList中的clear方法中调用了，另外一处是在**SubList**的**removeRange**方法（protected）中。不过ArrayList已经重写了**AbstractList**中的**clear**方法，所以第一处已经不会再调用了，那么只有第二处的**removeRange**方法在调用了，而**SubList**继承了**AbstractList**，所以对**removeRange**其实是通过**clear**来调用的。  
我们可以写段代码测试一下：

List<String> list = new ArrayList<String>();
            list.add("a");
            list.add("b");
            list.add("c");
            list.add("d");
            list.add("f");
            list.subList(2, 4).clear();
            System.out.println(list);

其实就是调用了**ArrayList**中的**removeRange**方法

你应该注意到了，上述很多方法都有一个`modCount++`的操作，这个属性是从**AbstractList**中继承下来的，官方文档说是用来记录**list**结构被改变的次数，但是实际上并不是很确切，比如我们看上面提到过的**ensureCapacity**方法：

这里每次调用**ensureCapacity**都会造成**modCount++**，但其实list结构并不一定改变。