ArrayList
有多个不同的构造函数,不同的构造函数的初始容量是不同的。快速看一下 ArrayList
源码里关于元素存放的几个私有属性:
// 默认容量是10 private static final int DEFAULT_CAPACITY = 10; // 如果容量为0的时候,就返回这个数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 使用默认容量10时,返回这个数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 元素存放的数组 transient Object[] elementData; // 元素的个数 private int size; // 记录被修改的次数 protected transient int modCount = 0; // 数组的最大值 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 复制代码
ArrayList
有三个构造方法,不同的构造方法的容量是不一样的,具体可以查看JDK 源码。
elementData
为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
elementData
为 EMPTY_ELEMENTDATA
。 toArray()
方法把它变成一个数组并赋值给 elementData
。同样会判断它的长度是否为0,如果为0,设置 elementData
为 EMPTY_ELEMENTDATA
。
可以看到, ArrayList
里面有两个概念,一个是 capacity
,它表示的就是“容量”,其实质是数组 elementData
的长度。而 size
则表示的“存放的元素的个数”。
因为Java中,数组操作不能越界,所以我们必须要保证在插入操作的时候,不会抛出数组越界异常。
底层主要是这三个私有方法:
// 扩容一个 private Object[] grow() { return grow(size + 1); } // 保证扩容到期望容量minCapacity及以上 private Object[] grow(int minCapacity) { return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity)); } // 根据期望容量minCapacity计算实际需要扩容的容量 private int newCapacity(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // 得到旧容量 int newCapacity = oldCapacity + (oldCapacity >> 1); // 设置新容量为旧容量的1.5倍 if (newCapacity - minCapacity <= 0) { // 如果新容量仍然小于期望容量 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 如果是使用的默认容量 return Math.max(DEFAULT_CAPACITY, minCapacity); // 取默认容量和期望容量较大值返回 if (minCapacity < 0) // overflow // 检查期望容量是否越界(int 的范围) throw new OutOfMemoryError(); return minCapacity; // 返回期望容量 } // 如果新容量大于期望容量,判断一下新容量是否越界 return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity); } 复制代码
可以看到,底层其实是调用了 Arrays.copyOf
方法来进行扩充数组容量的。这里我们主要看一下最后一个方法newCapacity(int minCapacity)的实现。
默认情况下,新的容量会是原容量的1.5倍,这里用了位运算提高效率。一般情况下,如果扩容1.5倍后就大于期望容量,那就返回这个1.5倍旧容量的值。而如果小于期望容量,那就返回期望容量。这里对默认容量10做了特殊处理。
使用1.5倍这个数值而不是直接使用期望容量,是为了防止频繁扩容影响性能。试想如果每次add操作都要扩容一次,那性能将会非常低下。
上述grow方法其实主要是用于实现自动扩容的。而用户也可以通过调用以下方法实现手动扩容:
public void ensureCapacity(int minCapacity) { if (minCapacity > elementData.length && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA && minCapacity <= DEFAULT_CAPACITY)) { modCount++; grow(minCapacity); } } 复制代码
为什么需要手动扩容?试想一下,如果用户已经知道即将存入大量的元素,比如目前有20个元素,即将存入2000个。那这个时候使用自动扩容就会扩容多次。而手动扩容可以一次性扩容到2000,可以提高性能。