ArrayList

变量

• elementData：用来存放数据

elementData 是用 transient 修饰的

ArrayList 实现了 Serializable 接口，这意味着 ArrayList 是可以被序列化的，用 transient 修饰 elementData 意味着不希望 elementData 数组被序列化

因为序列化 ArrayList 的时候，elementData 未必是满的

• 比方说 elementData 有 10 的大小，但是只用了其中的 3 个，那么没有必要序列化整个 elementData ，因此 ArrayList 中重写了 writeObject 方法
  • 提高了序列化的效率，减少了无意义的序列化
  • 减少了序列化后文件大小

初始化 & 扩容

ArrayList 的初始化是在插入的时候，跟 HashMap 一样

扩容也在插入的时候判断

• 扩容后的数组大小是 newCapacity = oldCapacity + (oldCapacity >> 1)

• 初始化发生在 calculateCapacity 里面( 这里是针对没指定数组大小的初始化，如果给了指定的数组大小，初始化就在构造里 )
• 扩容在 grow 方法里面

对于没有指定数组大小的构造，直接给一个空数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

对于有指定大小的，直接在构造里初始化

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // throw...
    }
}

精华都在注释里

( 下面的 初始化 是针对没指定数组大小的情况！！！ )

public boolean add(E e) {
    // 实参是 假如添加成功后的 真·元素个数
    ensureCapacityInternal(size + 1);  // Increments modCount!!

    elementData[size++] = e;
    return true;
}

// 注意 minCapacity 是 假如添加成功后的 真·元素个数
private void ensureCapacityInternal(int minCapacity) {
    // 先进入 calculateCapacity 确定是不是第一次来，要不要初始化
    // 然后通过 ensureExplicitCapacity 再看看需不需要扩容
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}


// 先看 calculateCapacity

// 初始化
// 确定是不是第一次来，要不要初始化
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果 elementData 是空的，就意味着要初始化，即返回默认一开始要开辟的数组大小
    // 默认是 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 如果 elementData 不为空，就知道你来过了，不需要初始化
    return minCapacity;
}

// 这里判断需不需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    // 操作数 + 1
    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);

    // 如果加了一半还是比假设成功添加元素后的元素个数小，那就直接把按传进来的来
    // ( 这种情况发生在 add 了另一个集合，两个长度和都比原来加了一半还大 )
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 无论是哪种情况，如果都超过了 MAX_ARRAY_SIZE( Integer.MAX_VALUE - 8 )
    // 那就直接 Integer.MAX_VALUE
    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);
}

// 如果都超过了 MAX_ARRAY_SIZE( Integer.MAX_VALUE - 8 )，那就直接Integer.MAX_VALUE
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

// 复制到新数组
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

// 复制到新数组
// 再下去就 native 了，不看了。。。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {

    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

遍历

迭代器最强

对于集合的迭代器，请看 集合的迭代器

子集

SubList 是 ArrayList 的子类

其实也就那样，大多数用的还是 ArrayList 的接口

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}