2.1 ArrayList、Vector

Wu Jun 2020-01-01 15:43:49
Categories: > > Tags:

ArrayList 除未实现同步外,跟 Vector 大致相同。同步效率低,在不需要同步的时候使用 ArrayList。

1 ArrayList

1.1 总体介绍

ArrayList 实现了 ListRandomAccess 接口。是顺序容器,允许 null 元素,支持随机访问。

ArrayList 底层通过动态数组实现,主要包含Object数组 elementData ,实际容量 capacity 以及当前大小 size

capacity默认10,容量不足时会自动扩容。

为追求效率,ArrayList 没有实现同步。用户可以手动同步,也可使用 Vector 替代,还可采用 Collections.synchronizedList() 包装。

1.2 方法剖析

1)add()

调用 add(E e)
  1. 扩容校验。
  2. 将插入的值放到尾部,并将 size + 1 。
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
调用 add(index,e)
  1. 扩容校验。
  2. 复制数据,本次数据插入 index ,后面数据后移。
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++;
}
2)grow()

扩容操作

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制
}
3)remove()

删除操作是 add() 操作的逆过程,需要将删除点之后的元素向前移动一个位置。为了让 GC 起作用,必须显式的为最后一个位置赋 null 值。

1.3 序列化

ArrayList 只序列化了被使用的数据。

由于 ArrayList 是基于动态数组实现的,所以并不是所有的空间都被使用。因此使用了 transient 修饰,可以防止被自动序列化。

transient Object[] elementData;

ArrayList 自定义了序列化与反序列化: writeObject 和 readObject 方法。

2 Vector

Vector 实现与 ArrayList 类似, 但所有方法都被 synchronized 修饰 ,开销较大。