ArrayList回顾

ArrayList 常见问题…

问题 ：ArrayList 的 size 和 capacity 怎么理解？

size 记录 ArrayList 实例中 elementData 数组中元素的个数，而 capacity 记录 elementData 数组的长度，包括已使用的数组空间和未使用的数组空间。

capacity 过大和过小都不好，过大会造成浪费，过小又存放不下多个元素的值，capacity == size，则 ArrayList 空间利用率最大，但是不利于添加新的元素。

当 ArrayList 实例内的元素个数不再改变了，可以使用 trimToSize() 方法最小化 ArrayList 实例来节省空间，也即是使 capacity == size。

问题：ArrayList 类常量 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 怎么理解？是不是多余？

// Shared empty array instance used for empty instances.
private static final Object[] EMPTY_ELEMENTDATA = {};

// Shared empty array instance used for default sized empty instances.
// We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.
// 用来区分扩容方式
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList(int initialCapacity) {
    // ....
    if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private void ensureCapacityInternal(int minCapacity) {//minCapacity=size+1
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);// 无参构造初始化为10
    }
    return 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;
    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);
}

但是 EMPTY_ELEMENTDATA 是使用带初始化值的构造方法（有参构造函数，一个是指定初始容量，一个是指定初始集合）时使用的，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是使用默认的构造方法，也即是无参的构造方法时使用的。

ArrayList(0)有参扩容：

after i=0, list capacity:1
after i=1, list capacity:2
after i=2, list capacity:3
after i=3, list capacity:4
after i=4, list capacity:6
after i=6, list capacity:9
after i=9, list capacity:13
after i=13, list capacity:19
after i=19, list capacity:28
after i=28, list capacity:42
after i=42, list capacity:63
after i=63, list capacity:94
after i=94, list capacity:141

ArrayList()无参扩容：

after i=0, list capacity:10
after i=10, list capacity:15
after i=15, list capacity:22
after i=22, list capacity:33
after i=33, list capacity:49
after i=49, list capacity:73
after i=73, list capacity:109

问题：ArrayList 的 add 操作优化？

核心就是避免 ArrayList 内部进行扩容。

1. 对于普通少量的 add 操作，如果插入元素的个数已知，最好使用带初始化参数的构造方法，避免 ArrayList 内部再进行扩容，提高性能。
2. 对于大量的 add 操作，最好先使用 ensureCapacity 方法来确保 elementData 数组中有充足的容量来存放我们后面 add 操作的元素，避免 ArrayList 实例内部进行扩容。上面提到的 ensureCapacityInternal 方法是一个私有方法，不能直接调用，而 ensureCapacity 方法是一个共有方法，专门提供给开发者使用的，提高大量 add 操作的性能。

测试代码如下：

public class ArrayList_01 {
    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
        Field elementDataField = ArrayList.class.getDeclaredField("elementData");
        elementDataField.setAccessible(true);

        ArrayList<Integer> arrayList = new ArrayList<>();
        int expectedCount = 100_0000;
        arrayList.ensureCapacity(expectedCount);

        Object[] elementDataArr = (Object[]) elementDataField.get(arrayList);
        System.out.printf("list capacity:%d%n", elementDataArr.length);

        long start = System.currentTimeMillis();
        for (int i = 0; i < 100_0001; i++) {
            arrayList.add(i);
        }
        long end = System.currentTimeMillis();
        long cost = end - start;

        elementDataArr = (Object[]) elementDataField.get(arrayList);
        System.out.printf("list capacity:%d%n", elementDataArr.length);

        arrayList.trimToSize();
        elementDataArr = (Object[]) elementDataField.get(arrayList);
        System.out.printf("list capacity:%d%n", elementDataArr.length);

        System.out.printf("大量 add 操作的时间花费：%d ms%n", cost);
    }
}

Result

list capacity:1000000         // ensureCapacity
list capacity:1500000         // after add expectedCount+1
list capacity:1000001         // trimToSize
大量 add 操作的时间花费：7 ms

问题：subList 方法生成的子列表会对父列表产生影响吗？

会，不管使修改子列表的值还是修改父列表的值都会对双方产生影响。阅读源码，就会发现，subList 方法后的子列表对元素的操作实际上调用的还是父列表中对应的方法。

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}
SubList(AbstractList<E> parent,
        int offset, int fromIndex, int toIndex) {
    this.parent = parent;                         // 原ArrayList
    this.parentOffset = fromIndex;
    this.offset = offset + fromIndex;
    this.size = toIndex - fromIndex;
    this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {
    E oldValue = ArrayList.this.elementData(offset + index);
    ArrayList.this.elementData[offset + index] = e;
}
public E get(int index) {
    return ArrayList.this.elementData(offset + index);
}
public void add(int index, E e) {
    parent.add(parentOffset + index, e);
    this.modCount = parent.modCount;
}
public E remove(int index) {
    E result = parent.remove(parentOffset + index);
}

问题：ArrayList 中既有 Itr 迭代器类，又有 ListItr 迭代器类，该用哪个？

List 集合可以看作是数组的包装类型，遍历并不像数组那样方便，迭代器是为了迭代集合中的元素而存在的。

• Itr 迭代器类实现了 Iterator 接口，ListItr 迭代器类继承 Itr 迭代器类，并且实现了 ListIterator 接口，所以 ListItr 类的功能比 Itr 类更强大。
• Itr 类在迭代过程中不能修改 List 的结构（如 add 操作），否则会抛出并发修改异常 ConcurrentModificationException，并且在 next 方法之后才能 remove 元素，而 ListItr 类还支持在迭代过程中添加元素，对于 List 集合元素操作更加友好。

所以对于 List 集合迭代，最好使用 ListItr 迭代器类。