原文链接

基本原理

内部组成

可以看出，ArrayList的基本用法是比较简单的，它的基本原理也是比较简单的，原理与我们在前面几节介绍的DynaArray类似，内部有一个数组elementData，一般会有一些预留的空间，有一个整数size记录实际的元素个数，如下所示：

1
2
transient Object[] elementData;
private int size;

我们暂时可以忽略transient这个关键字。各种public方法内部操作的基本都是这个数组和这个整数，elementData会随着实际元素个数的增多而重新分配，而size则始终记录实际的元素个数。

Add方法

add方法的代码：

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

它首先调用ensureCapacityInternal确保数组容量是够的，ensureCapacityInternal的代码是：

1
2
3
4
5
6
7
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

它先判断数组是不是空的，如果是空的，则首次至少要分配的大小为DEFAULT_CAPACITY，DEFAULT_CAPACITY的值为10，接下来调用ensureExplicitCapacity，代码为：

1
2
3
4
5
6
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

modCount++是什么意思呢？modCount表示内部的修改次数，modCount++当然就是增加修改次数，为什么要记录修改次数呢，在迭代器里会用到，每次发生结构性变化的时候modCount都会增加，而每次迭代器操作的时候都会检查expectedModCount是否与modCount相同，这样就能检测出结构性变化。

如果需要的长度大于当前数组的长度，则调用grow方法。这段代码前面有个注释：overflow-conscious code，翻译一下，大意就是代码考虑了溢出这种情况，溢出是什么意思呢？我们解释下，假设a,b都是int，下面两行代码是不一样的：

1
2
1 if(a>b)
2 if(a-b>0)

为什么呢？考虑a=Integer.MAX_VALUE, b=Integer.MIN_VALUE：

a>b为true

但由于溢出，a-b的结果为-1

反之，再考虑a=Integer.MIN_VALUE, b=Integer.MAX_VALUE:

a>b为false

但由于溢出，a-b的结果为1。

不过，在a, b都为正数且数值没有那么大的情况下，一般也没有溢出问题，为便于理解，在后续的分析中，我们将忽略溢出问题。

接下来，看grow方法：

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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);
}

排除边缘情况，长度增长的主要代码为：

1
int newCapacity = oldCapacity + (oldCapacity >> 1);

右移一位相当于除2，所以，newCapacity相当于oldCapacity的1.5倍。

Remove方法

Remove方法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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; // clear to let GC do its work

    return oldValue;
}

它也增加了modCount，然后计算要移动的元素个数，从index往后的元素都往前移动一位，实际调用System.arraycopy方法移动元素。elementData[--size] = null;这行代码将size减一，同时将最后一个位置设为null，设为null后就不再引用原来对象，如果原来对象也不再被其他对象引用，就可以被垃圾回收。

RandomAccess

RandomAccess的定义为：

1
2
public interface RandomAccess {
}

没有定义任何代码。这有什么用呢？这种没有任何代码的接口在Java中被称之为标记接口，用于声明类的一种属性。

这里，实现了RandomAccess接口的类表示可以随机访问，可随机访问就是具备类似数组那样的特性，数据在内存是连续存放的，根据索引值就可以直接定位到具体的元素，访问效率很高。下节我们会介绍LinkedList，它就不能随机访问。

有没有声明RandomAccess有什么关系呢？主要用于一些通用的算法代码中，它可以根据这个声明而选择效率更高的实现。比如说，Collections类中有一个方法binarySearch，在List中进行二分查找，它的实现代码就根据list是否实现了RandomAccess而采用不同的实现机制，如下所示：

1
2
3
4
5
6
7
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

ArrayList特点分析

各种容器类和数据组织方式，之所以有各种不同的方式，是因为不同方式有不同特点，而不同特点有不同适用场合。考虑特点时，性能是其中一个很重要的部分，但性能不是一个简单的高低之分，对于一种数据结构，有的操作性能高，有的操作性能可能就比较低。

作为程序员，就是要理解每种数据结构的特点，根据场合的不同，选择不同的数据结构。

对于ArrayList，它的特点是：内部采用动态数组实现，这决定了：

  • 可以随机访问，按照索引位置进行访问效率很高，用算法描述中的术语，效率是O(1)，简单说就是可以一步到位。
  • 除非数组已排序，否则按照内容查找元素效率比较低，具体是O(N)，N为数组内容长度，也就是说，性能与数组长度成正比。
  • 添加元素的效率还可以，重新分配和拷贝数组的开销被平摊了，具体来说，添加N个元素的效率为O(N)。
  • 插入和删除元素的效率比较低，因为需要移动元素，具体为O(N)。