ArrayList&Vector详解

ArrayList基本介绍

ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。数组是一个Object数组，以便能够容纳任何类型的对象。

为追求效率，ArrayList没有实现同步(synchronized)，如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。

ArrayList底层实现

底层数据结构

ArrayList中维护了一个Object类型的数组

transient Object[] elementData; // transient标识瞬间，短暂的，表示该属性不会被序列化

构造函数

无参构造默认容量为0的空数组，但是在add操作时，首次扩容为10.

add()扩容机制

debug跟踪下面代码

ArrayList list = new ArrayList<>();
list.add(1);

创建一个空的数组

1. 先处理扩容逻辑
2. 进行赋值逻辑

1. 判断是否为第一次扩容，是的话，minCapacity = max(10,size+1)。这里的size+1 = 1
2. 因此返回的minCapacity = 10。

1. modCount++ 记录集合被修改的次数
2. 如果数组(elementData)的容量不够，就去扩容-->grow

1. 开始扩容
2. 将容量扩容为原来的1.5倍
3. copy一份原数组，定义新的容量

扩容结束，则进行赋值，add()操作结束

get()

由于底层是数组，get方法实现很简单

public E get(int index) {
    rangeCheck(index);//检查下标越界

    return elementData(index);
}

set()

由于底层是数组，set方法实现很简单

public E set(int index, E element) {
    rangeCheck(index);//检查下标越界

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;//返回旧值
}

remove()

remove()方法也有两个版本，一个是remove(int index)删除指定位置的元素，另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置赋null值。

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

indexOf()

获取元素的第一次出现的index

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

lastIndexOf()

获取元素最后一次出现的index

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

Fail-Fast机制

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

Vector基本介绍

Vector是实现了List接口的子类，其底层是一个对象数组，维护了一个elementData数组，是线程安全的，Vector类的方法带有synchronized关键字，在开发中考虑线程安全中使用Vector。

Vector的底层实现

底层数据结构

底层数据结构和ArrayList相同，都是数组

protected Object[] elementData; 

构造函数

add()扩容机制

Vector的扩容机制基本和ArrayList类似。

每次默认扩容为原来容量的2倍

注意：由于Vector在初始化时，定义长度为10，因此add()操作时，如果空间不满足会直接扩容。但是ArrayList会判断是否为第一次扩容，因为ArrayList初始化的长度为0，第一次扩容后才改为10。

从源码得知，newCapacity = oldCapacity+oldCapacity。

其中 capacityIncrement 为用户定义的扩容量，如果为0则每次扩容量为原来的容量。

ArrayList和Vector比较

	底层结构	版本	线程安全/效率	扩容倍数
ArrayList	可变数组	jdk1.2	不安全/效率高	1.5
Vector	可变数组	jdk1.0	安全/效率不高	2

参考

• https://www.bilibili.com/video/BV1YA411T76k?p=11

• https://www.pdai.tech/md/java/collection/java-collection-ArrayList.html