ArrayList和Vector

(Updated: )
面试 › Java
,

前言

今天阅读ArrayList和Vector的源码，了解其底层结构和扩容机制

首先，需要知道的是

  • ArrayList和Vector底层都是可变数组实现
  • ArrayList非线程安全，Vector是线程安全的

对比一下ArrayList和Vector的常量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 序列版本号
    private static final long serialVersionUID = 8683452581122892189L;

    // 默认大小为10
    private static final int DEFAULT_CAPACITY = 10;

    // 空的缓存数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 缓存数组没有指定大小时 容量大小为空
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 底层实现方式 其实就是通过缓存数组 随时扩充容量 这里使用transient关键字 表示不参与ArrayList的序列化 原因每当ArrayList类序列化和反序列化时会分别调用writeObject和readObject方法读写相关数据 这样避免了缓存数组中存在多余的无用空间 避免占用内存
    transient Object[] elementData;

    // 数组的实际大小
    private int size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 缓存数组
    protected Object[] elementData;

    // 缓存数组中实际容量大小
    protected int elementCount;

    // 自定义的容量增长量
    protected int capacityIncrement;

    // 序列化版本号
    private static final long serialVersionUID = -2767605614048989439L;
}

总结一下，ArrayList和Vector的底层都是通过缓存数组来实现的

ArrayList的elementData使用transient关键字修饰，不参与对象的序列化

而Vector的elelmentData没有参与对象的序列化，至于原因，网上说是因为重写了writeObject方法，因为Vector本质就是线程安全的，我不是很理解，希望有大佬再解释一下

对比构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 无参构造 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 new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 将已有的集合塞入构造
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 无参构造 初始化容量大小为10
public Vector() {
    this(10);
}

// 给定初始容量
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

// 给定初始容量和每次容量的扩容值
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

// 将已有的集合塞入
public Vector(Collection<? extends E> c) {
    Object[] a = c.toArray();
    elementCount = a.length;
    if (c.getClass() == ArrayList.class) {
        elementData = a;
    } else {
        elementData = Arrays.copyOf(a, elementCount, Object[].class);
    }
}

对比而言，Vector的构造具有更多的自主性，开发者可以限定扩容时的增长值

扩容机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

当ArrayList添加元素时，会先将当前实际元素容量和缓存数组容量做对比，大小不够时则考虑扩容

1
2
3
4
5
6
7
8
9
10
11
12
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

当Vector添加元素时，同ArrayList，容量不够则考虑扩容

其中，ArrayList多出的代码主要是因为Vector在无参构造时，默认初始化了10个空间，而ArrayList在添加第一个元素时，若缓存数组容量为默认值（空数组），则也给一个初始化的大小（10）

另外，Vector的add函数加上了同步锁，保证了线程的安全性

ArrayList扩容细节

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

一目了然，newCapcity = oldCapcity + ( oldCapcity >> 1 )

进行1.5倍扩容 若初始化空间为10 那么容量大小变化就为 10 -> 15 -> 22 -> 33 -> ……

Vector扩容细节

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Vector中，若开发者没有自定义增长容量，则按2倍扩容，否则每次在当前容量的基础上加上开发者自定义的增长容量