Java中ArrayList的扩容机制

ArrayList作为List接口的实现类，它是一种可以根据需要动态增长的数组。在Java中标准的数组都是定长的，当一个数组被创建后，它不能再被修改长度，也就是说我们在创建数组时要确定数组所需的长度。但有时我们需要动态程序中获取数组长度，此时，我们就可以使用ArrayList来存储数据，但是它并不是线程安全的。

首先，ArrayList扩容发生在add()方法调用的时候，它是调用ensureCapacityInternal()来扩容的，通过方法calculateCapacity(elementData, minCapacity)获取需要扩容的长度，ensureExplicitCapacity方法可以判断是否需要扩容，ArrayList扩容的关键方法grow(): 获取到ArrayList中elementData数组的内存空间长度 扩容至原来的1.5倍，调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间，从此方法中我们可以清晰的看出其实ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。

ArrayList有三种方式来初始化，构造方法源码如下：

// 默认初始容量private static final int DEFAULT_CAPACITY = 10;/*** Shared empty array instance used for empty instances.*/private static final Object[] EMPTY_ELEMENTDATA = {};

第一种：

// 默认构造函数，使用初始容量10构造一个空列表(无参数构造) 
/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

第二种：

 // 带初始容量参数的构造函数。（用户自己指定容量）/*** Constructs an empty list with the specified initial capacity.** @param  initialCapacity  the initial capacity of the list* @throws IllegalArgumentException if the specified initial capacity*         is negative*/public ArrayList(int initialCapacity) {if (initialCapacity > 0) { // 初始容量大于0// 创建initialCapacity大小的数组this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) { // 初始容量等于0// 创建空数组this.elementData = EMPTY_ELEMENTDATA;} else {// 初始容量小于0，抛出异常throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}

第三种：

// 构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
// 如果指定的集合为null，throws NullPointerException。/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/public ArrayList(Collection c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}

我们发现，以无参构造方法创建ArrayList时，实际上初始化赋值的是一个空数组，当真正对数组进行添加元素操作时，才真正分配容量。级向数组中添加第一个元素时，数组容量扩为10。

        分析扩容机制：

以无参构造函数创建的 ArrayList 为例分析：

1.先看add()方法

// 将指定的元素追加到此列表的末尾/*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return true (as specified by {@link Collection#add})*/public boolean add(E e) {// 添加元素之前，先调用ensureCapacityInternal方法ensureCapacityInternal(size + 1);  // Increments modCount!!// 这里看到ArrayList添加元素的实质就相当于为数组赋值elementData[size++] = e;return true;}

2.再看 ensureCapacityInternal() 方法

 add 方法 首先调用了 ensureCapacityInternal(size + 1)

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

ensureCapacityInternal()方法调用calculateCapacity(elementData, minCapacity)方法

private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 获取默认的容量和传入参数的较大值return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}

当 要 add 进第1个元素时，minCapacity为1，在Math.max()方法比较后，minCapacity 为10。

3.ensureExplicitCapacity() 方法

如果调用 ensureCapacityInternal() 方法就一定会(执行）这个方法

// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)// 调用grow方法进行扩容，调用此方法代表已经开始扩容了grow(minCapacity);}

当我们要 add 进第1个元素到 ArrayList 时，elementData.length 为0 （因为还是一个空的 list），因为执行了ensureCapacityInternal() 方法 ，所以 minCapacity 此时为10。此时， minCapacity -elementData.length > 0 成立，所以会进入 grow(minCapacity) 方法。当add第2个元素时，minCapacity 为2，此时e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时， minCapacity - elementData.length > 0 不成立，所以不会进入 （执行） grow(minCapacity) 方法。添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大。进入grow方法进行扩容。

4.grow() 方法

※ ArrayList扩容的核心方法

// 要分配的最大数组大小/*** The maximum size of array to allocate.* Some VMs reserve some header words in an array.* Attempts to allocate larger arrays may result in* OutOfMemoryError: Requested array size exceeds VM limit*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious code// oldCapacity为旧容量，newCapacity为新容量int oldCapacity = elementData.length;// 将oldCapacity 右移一位，其效果相当于oldCapacity /2，// 我们知道位运算的速度远远快于整除运算，整句运算式结果就是将新容量更新为旧容量的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);//然后检查新容量是否大于最小需要容量，若还是小于最小需要容量//那么就把最小需要容量当作数组的新容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和            // MAX_ARRAY_SIZE，// 如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，// 否则，新容量大小则为MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}

当add第1个元素时，oldCapacity 为0，经比较后第一个if判断成立，newCapacity = minCapacity(为10)。但是第二个if判断不会成立，即newCapacity 不比 MAX_ARRAY_SIZE大，则不会进入 hugeCapacity 方法。数组容量为10，add方法中 return true,size增为1。

当add第11个元素进入grow方法时，newCapacity为15，比minCapacity（为11）大，第一个if判断不成立。新容量没有大于数组最大size，不会进入hugeCapacity方法。数组容量扩为15，add方法中return true,size增为11。

5. hugeCapacity()方法

从上面 grow() 方法源码我们知道：如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较minCapacity 和 MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为 Integer.MAX_VALUE ，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8 。

private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();// 对minCapacity和MAX_ARRAY_SIZE进行比较// 若minCapacity大，将Integer.MAX_VALUE作为新数组的大小// 若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

最后， ArrayList 中调用Arrays.copyOf()方法进行对数组进行重新分配空间和复制原有数组内容。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！