ArrayList 的底层是一个数组,且该数组不可被序列化。

transient Object[] elementData;

ArrayList 的容量就是这个数组的长度。而我们用 size() 方法获得的是 ArrayList 的元素个数,也称之为“逻辑”长度。也就是说元素个数是不包含这个数组中的空值的,ArrayList 的容量是大于等于其元素个数的。

奇怪的注释

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
		this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

从无参构造器的注释,我们会发现,ArrayList 会构造一个初始容量为 10 的空 list。然而通过对源码分析,我发现 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是一个空数组。

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

那么 ArrayList 的初始容量究竟是0,还是10?通过对 ArrayList 源码的分析,其实我们很容易得出下面的结论:

  • 无参构造器和泛型参数构造器都会构建一个长度为0的数组。
  • 整型参数构造器通过传入的整型数据的大小来确认初始化存储容器elementData 的大小,当initialCapacity为0时,还是会构建一个长度为0的数组。
  • 由于 DEFAULT_CAPACITY 为10,当第一次调用 add() 方法时,elementData 的长度就会自动扩容为10。
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}

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

        ensureExplicitCapacity(minCapacity);
}

通过反射验证分析

在 ArrayList 中,我们是无法直接获得它的 CAPACITY,也就是 elementData 的长度。但是我们可以通过反射来做到这一点:

import org.junit.Test;

import java.lang.reflect.Field;
import java.util.ArrayList;

public class CapacityTest {
    @Test
    public void test() {
        ArrayList arrayList = new ArrayList();
        System.out.println("capacity: " + getCapacity(arrayList) + " size: " + arrayList.size());

        arrayList.add("test");
        System.out.println("capacity: " + getCapacity(arrayList) + " size: " + arrayList.size());

        arrayList = new ArrayList(11);
        System.out.println("capacity: " + getCapacity(arrayList) + " size: " + arrayList.size());
    }

    public static int getCapacity(ArrayList arrayList) {
        try {
            Field elementDataField = ArrayList.class.getDeclaredField("elementData");
            elementDataField.setAccessible(true);
            return ((Object[]) elementDataField.get(arrayList)).length;
        } catch (NoSuchFieldException | IllegalAccessException e) {
            e.printStackTrace();
						return -1;
        }
    }
}

输出结果:

capacity: 0 size: 0
capacity: 10 size: 1
capacity: 11 size: 0

ensureCapacity(int minCapacity)

从add()与addAll()方法中可以看出,每当向数组中添加元素时,都要去检查添加元素后的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。在java 8中,向用户提供了一个 ensureCapacity(int minCapacity) 方法,使用户可以手动的设置 ArrayList 实例的容量,以减少递增式再分配的数量。 显示的调用这个函数,如果参数小于底层数组长度,即小于10,那么这个数组长度保持不变;如果参数大于10但小于低层数组长度的1.5倍,那么这个容量就会被扩容到低层数组长度的1.5倍;如果参数大于低层数组长度的1.5倍,那么这个数组的容量就会被扩容到这个参数值。

import org.junit.Test;

        import java.lang.reflect.Field;
        import java.util.ArrayList;

public class EnsureCapacityTest {
    @Test
    public void test() {
        ArrayList list = new ArrayList();
        list.add("test");
        System.out.println("capacity: " + getCapacity(list));

        list.ensureCapacity(5);
        System.out.println("capacity: " + getCapacity(list));

        list.ensureCapacity(11);
        System.out.println("capacity: " + getCapacity(list));

        list.ensureCapacity(100);
        System.out.println("capacity: " + getCapacity(list));
    }

    public static int getCapacity(ArrayList arrayList) {
        try {
            Field elementDataField = ArrayList.class.getDeclaredField("elementData");
            elementDataField.setAccessible(true);
            return ((Object[]) elementDataField.get(arrayList)).length;
        } catch (NoSuchFieldException | IllegalAccessException e) {
            e.printStackTrace();
            return -1;
        }
    }
}

输出结果:

capacity: 10
capacity: 10
capacity: 15
capacity: 100

那么为什么要引入这个方法呢?请看下面一段代码:

 @Test
    public void speedTest() {
        final int N = 1000000;
        Object obj = new Object();
        ArrayList list1 = new ArrayList();
        long start1 = System.currentTimeMillis();
        for(int i = 0; i < N; i++){
            list1.add(obj);
        }
        System.out.println("interval time: " + (System.currentTimeMillis() - start1));

        ArrayList list2 = new ArrayList();
        long start2 = System.currentTimeMillis();
        list2.ensureCapacity(N);//显示的对低层数组进行扩容
        for(int i = 0; i<N; i++){
            list2.add(obj);
        }
        System.out.println("interval time: " + (System.currentTimeMillis() - start2));
    }

输出结果:

interval time: 20
interval time: 9

很明显,第二段代码的效率有了明显的提升。因为第一段没有一次性扩到想要的最大容量,它就会在添加元素的过程中,一点一点的进行扩容,要知道对数组扩容是要进行数组拷贝的,这就会浪费大量的时间。如果已经预知容器可能会装多少元素,最好显示的调用 ensureCapacity() 方法一次性扩容到位。

参考资料:

ArrayList 源码分析 -- 扩容问题及序列化问题

最后修改于 2019-03-23 20:04:36
上一篇