深入剖析ArrayList的底层源码-ArrayList 和 Vector 的区别

ArrayList 和 Vector 底层都是 数组

ArrayList 每次扩容的情况下扩容为原来的1.5 倍。线程不安全,当多个线程同时访问同一个ArrayList 集合时,如果两个或两个以上的线程修改了 ArrayList 集合,则必须手动保证该集合的同步性。

Vector 是同步类,其线程安全,但是它的访问比较慢。Vector 每次扩容为其空间大小的 2 倍。

五、对扩容原理源码剖析及其思考

在add()方法中调用ensureCapacityInternal()方法,用来确保添加元素的时候,最小容量是 minCapacity。

源码剖析

 

private void ensureCapacityInternal(int minCapacity) {

// 判断元素数组是否为空数组

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

     // 取最大值

        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

    }

 

    ensureExplicitCapacity(minCapacity);

}

 

在ensureCapacityInternal()方法里面调用ensureExplicitCapacity(int minCapacity)方法,用来判段集合在添加元素的时候是否需要对当前的数组进行扩容。

源码剖析

 

private void ensureExplicitCapacity(int minCapacity) {

   modCount++;

 

    // overflow-conscious code

    // 判断minCapacity与当前元素数组的长度的大小

    // 如果minCapacity比当前元素数组的长度的大小大的时候需要扩容

    if (minCapacity – elementData.length > 0)

     // 扩容

        grow(minCapacity);

}

 

在ensureExplicitCapacity() 方法里面调用grow(int minCapacity)方法,进行扩容。

源码剖析

 

 /**

  * Increases the capacity to ensure that it can hold at least the

  * number of elements specified by the minimum capacity argument.

  *

  * @param minCapacity the desired minimum capacity

  */

private void grow(int minCapacity) {

    // overflow-conscious code

    // 原本的容量

    int oldCapacity = elementData.length;

    // 新的容量是原本容量的1.5倍

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

}

/**

 *hugeCapacity()方法,用于处理minCapacity超出MAX_ARRAY_SIZE的情况

 */

private static int hugeCapacity(int minCapacity) {

    if (minCapacity < 0) // overflow

        throw new OutOfMemoryError();

    return (minCapacity > MAX_ARRAY_SIZE) ?

        Integer.MAX_VALUE :

        MAX_ARRAY_SIZE;

}

 

最后调用 Arrays.copyOf()方法,用来复制原数组,将 elementData 赋值为得到的新数组。

注意:

 

由于数组复制的代价比较大,因此建议在创建 ArrayList 对象的时候就指定大概的容量大小,从而减少扩容操作的次数。

 

六、ArrayList的优缺点

1. 优点

能够自动扩容,默认每次扩容为原来容量大小的1.5倍。

根据下标遍历元素,效率高。

根据下标访问元素,效率高。

2. 缺点

线程不安全。

根据下标查找元素的时候需要遍历整个元素数组,效率低。

插入和删除元素的时候需要移动元素,效率低。