ArrayList的动态扩容

拼搏现实的明天。 2022-05-28 02:08 339阅读 0赞

ArrayList可以实现容量的自适应的增加，通过阅读源代码，对这个机制进行一下简单的分析。

首先，ArrayList有一个初始的默认大小，为10.

private static final int DEFAULT_CAPACITY = 10;

从add方法为入口

public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

可见，在添加元素之前，会先调用ensureCapacityInternal这个方法，那就再进到这个这个方法中去。

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

  1.     ensureExplicitCapacity(minCapacity);  
  2. \}  
  5.    首先，看看数组是否为空，如果是，就将DEFAULT\_CAPACITY和minCapacity的较大的一个作为初始大小赋值给minCapacity ，DEFAULT\_CAPACITY是10，minCapacity就是add方法中传入的size + 1。
  10.     如果数组不为空，就直接执行ensureExplicitCapacity方法。ensureExplicitCapacity方法的实现如下：

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

  1.     // overflow-conscious code  
  2.     if (minCapacity - elementData.length > 0)  
  3.         grow(minCapacity);  
  4. \}  
  7.  在这个方法里，会比较minCapacity 与elementData.length 的大小。当第一次插入值时，由于minCapacity 一定大于等于10，而

elementData.length是0，所以会去继续执行grow方法，那就继续进入到这个方法中去。grow方法的实现如下：

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);
}

这个方法首先计算出一个容量，大小为oldCapacity + (oldCapacity >> 1)。即elementData数组长度的1.5倍。再从minCapacity 和

这个容量中取较大的值作为扩容后的新的数组的大小。

  1. 这时，会出现两种情况：

一. 新的容量小于数组的最大值MAX_ARRAY_SIZE ，即

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  1.  最大的容量之所以设为Integer.MAX\_VALUE - 8，在定义上方的注释中已经说了，大概是一些JVM实现时，会在数组的前面放一些额外的数据，再加上数组中的数据大小，有可能超过一次能申请的整块内存的大小上限，出现OutOfMemoryError。

二. 新的容量大于数组的最大值MAX_ARRAY_SIZE

这时，又会进入另一个方法hugeCapacity

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

会对minCapacity 和 MAX_ARRAY_SIZE进行比较，minCapacity 大的话，就将Integer.MAX_VALUE 作为新数组的大小，否则将MAX_ARRAY_SIZE作为数组的大小。

  1.   最后，就把原来数组的数据复制到新的数组中。调用了Arrays的copyOf方法。内部是System的arraycopy方法，由于是native方法，所以效率较高。

通过分析可以发现，ArrayList的扩容会产生一个新的数组，将原来数组的值复制到新的数组中。会消耗一定的资源。所以我们初始化ArrayList时，最好可以估算一个初始的大小。

发表评论

表情：
评论列表 （有 0 条评论，339人围观）

还没有评论，来说两句吧...

相关阅读