Java集合框架源码解析（一） - ArrayList

List接口

ArrayList

ArrayList是List接口最基础的实现。（比数组好的地方）它是以数组的形式实现的集合。想想看你用C语言怎么实现一个线性表呢？

struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; // 保存线性表中最后一个元素的位置
};

而在ArrayList里，同样有ElementData和size两个实例变量，通过两个基本变量来实现可动态变容的数组的。

（在构造器处看看这两个变量）

下面我们看看ArrayList一些常见接口和内部实现。

添加

ArrayList有两个add接口：允许把一个元素加在列表的最后，或指定位置。

分别看看它们的实现代码：

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

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

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

暂时先忽略ensureCapacityInternal，不出所料，加在最后的add方法是一个O(1)的操作，而加在指定位置的add方法需要对index之后的所有元素移位，是一个O(n)操作。No fancy ：）。

size是维护数组长度的属性，增加元素的时候，它会+1。

删除和查找

删除接口同样有两个：删除指定元素或删除指定下标上的元素。同样需要移位后继元素，是O(n)操作，代码和add方法十分相似，就不做展示了。

ArrayList提供get和indexOf接口，允许返回指定下标的元素和搜索一个特定元素的下标。时间复杂度多少，你自己猜猜。

扩容

ArrayList比数组好用的最重要原因就是：数组的大小是不可变的，而ArrayList是可扩容的。而这个扩容对客户来说是透明的，它发生在add操作内，也就是刚才看到的ensureCapacityInternal，现在重点来说一说它：

虽说ArrayList的扩容对客户而言是透明的，但它依然提供接口：ensureCapacity（方法用public修饰），提供手动扩容的功能：

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

在实现里，实际调用的是grow方法：

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

重点是grow方法的第二行：>>是向右移位操作符，得到的结果是原操作数除以二的值。整个表达式（oldCapacity + (oldCapacity >> 1)）的值约为oldCapacity的1.5倍。在这里有一个疑问，为什么每次扩容处理会是1.5倍，而不是2.5、3、4倍呢？因为一次性扩容太大(例如2.5倍)可能会浪费更多的内存(1.5倍最多浪费33%，而2.5被最多会浪费60%，3.5倍则会浪费71%……)。但是一次性扩容太小，需要多次对数组重新分配内存，对性能消耗比较严重。所以1.5倍是个经验值，它既能满足性能需求，也不会造成很大的内存消耗。

在1.8之前的版本，这一行运算是写成int newCapacity = (oldCapacity * 3)/2 + 1;，旧的算法增长的更快。无论新旧算法，capacity的增长都是指数级的，简单做个实验：

public static void main(String[] args) {
    int a = 10;
    int count = 0;
    while ((a = grow(a)) < Integer.MAX_VALUE && a > 0) {
        count++;
        System.out.println(a);
    }
    System.out.println(count);
}

private static int grow(int capacity) {
    return capacity + (capacity >> 1);
}

需要grow多少次呢？

15
22
33
49
73
109
163
244
366
549
823
....
354836040
532254060
798381090
1197571635
1796357452
48

48次，你应该对这个算法有个感性的认识了。所以扩容扩多少，是JDK开发人员在时间、空间上做的一个权衡，提供出来的一个比较合理的数值。

增加了容量之后，最后是调用Array.copyOf复制到新数组。