【Java集合】2 ArrayList

Vector

Q：ArrayList 和 Vector 的区别？

1. 都是基于动态数组实现，支持随机访问，查询快，增删慢，因为要移动后续所有的元素，但 Vector 是线程安全的，ArrayList 不是线程安全的，性能更好；
2. 底层使用对象数组保存数据，当数组满时，会自动扩容，创建新的数组，并拷贝原有数组数据，扩容后 ArrayList 容量增加 50%，Vector 增加一倍。

LinkedList

Q：ArrayList 和 LinkedList 的区别？

1. 都不是线程安全的。
2. ArrayList 基于动态数组实现，支持随机访问，查询快；LinkedList 基于双向链表实现，只能顺序访问，查询慢。
3. ArrayList 快在寻址，慢在要移动元素以及可能的扩容，所以越往后，不发生扩容时，效率越高；LinkedList 快在只需修改 Entry 的引用，慢在寻址，所以越往前，效率越高；整体上，由于元素增删的不确定性，以及可能的扩容，LinkedList 增删快于 ArrayList。
4. LinkedList 因为要存放元素、直接前驱和后继，所以会占用更多内存。

扩容机制

使用 add() 时，内部先调用 ensureCapacityInternal() ，传入 size + 1，来检查底层数组 elementData 是否需要扩容。

public boolean add(E e) {
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}
// JDK11 移除了 ensureCapacityInternal() 和 ensureExplicitCapacity() 方法

在这个方法中，先判断数组 elementData 是否为空，如果为空，那么 minCapacity 取默认容量 10 和 size + 1 中更大的那个，

然后调用 ensureExplicitCapacity() 。

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

它会先进行 modCount 自增，来记录集合结构发生变化的次数，用于迭代的快速失败；

然后判断 minCapacity 是否大于数组长度，如果是，就调用 grow()，进行扩容。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow() 中，新容量为原来的 1.5 倍，如果还不够，就使用它指定要扩容的大小 minCapacity，然后判断 minCapacity 是否大于 MAX_ARRAY_SIZE，如果大于，新容量为 Integer.MAX_VALUE；最后调用 Arrays.copyOf() 拷贝原数组数据，完成扩容。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

ArrayList源码分析（扩容机制jdk8）