Java ArrayList自动扩容机制

2020 年 4 月 5 日
笔记

动态扩容

1、add(E e)方法中

① ensureCapacityInternal(size+1),确保内部容量，size是添加前数组内元素的数量

② elementData[size++] = e 添加元素到相应位置，元素数量加1

2、 ensureCapacityInternal(size+1)确保内部容量

① 计算最小需要空间（如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值）

② 判断是否需要扩容（如果最小需要空间比elementData的内存空间要大，则扩容）

3、扩容 grow(int minCapacity)

newCapacity=oldCapacity + (oldCapacity >> 1),原来元素数量的1.5倍

再与最小需要空间比较，与最大数组长度比较

一初始化

先看一下ArrayList的两个构造方法

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

在无参构造中，我们看到了在用无参构造来创建对象的时候其实就是创建了一个空数组，长度为0

在有参构造中，传入的参数是正整数就按照传入的参数来确定创建数组的大小，否则异常

二确保内部容量

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

① ensureCapacityInternal方法名的英文大致是“确保内部容量”，size表示的是执行添加之前的元素个数，

并非ArrayList的容量，容量应该是数组elementData的长度。ensureCapacityInternal该方法通过将现有的元素个数与数组的容量比较。看如果需要扩容，则扩容。
②是将要添加的元素放置到相应的数组中。

可以看出ensureCapacityInternal()是用来扩容的，形参为最小扩容量，进入此方法后：

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

通过方法calculateCapacity(elementData, minCapacity)获取最小需要空间

private static int calculateCapacity(Object[] elementData, int minCapacity) {          //如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值          if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {              return Math.max(DEFAULT_CAPACITY, minCapacity);          }          return minCapacity;      }

ensureExplicitCapacity方法可以判断是否需要扩容：

 private void ensureExplicitCapacity(int minCapacity) {            modCount++;              // 如果最小需要空间比elementData的内存空间要大，则需要扩容            if (minCapacity - elementData.length > 0)                //扩容                grow(minCapacity);        }

三扩容

ArrayList扩容的关键方法grow():

  private void grow(int minCapacity) {            // 获取到ArrayList中elementData数组的内存空间长度            int oldCapacity = elementData.length;           // 扩容至原来的1.5倍           int newCapacity = oldCapacity + (oldCapacity >> 1);           // 再判断一下新数组的容量够不够，够了就直接使用这个长度创建新数组，            // 不够就将数组长度设置为需要的长度           if (newCapacity - minCapacity < 0)               newCapacity = minCapacity;           //若预设值大于默认的最大值检查是否溢出           if (newCapacity - MAX_ARRAY_SIZE > 0)               newCapacity = hugeCapacity(minCapacity);           // 调用Arrays.copyOf方法将elementData数组指向新的内存空间newCapacity的连续空间           // 并将elementData的数据复制到新的内存空间           elementData = Arrays.copyOf(elementData, newCapacity);       }

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

int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 右移运算符原来长度的一半再加上原长度也就是每次扩容是原来的1.5倍

之前的所有都是确定新数组的长度，确定之后就是把老数组copy到新数组中，这样数组的扩容就结束了

###每次扩容都是通过Arrays.copyOf(elementData, newCapacity) 这样的方式实现的。ArrayList的自动扩容机制底层借助于System实现System.arraycopy(0,oldsrc,0,newsrc,length);

扩展：System源码中的arraycopy（）标识为native意味JDK的本地库，不可避免的会进行IO操作，如果频繁的对ArrayList进行扩容，毫不疑问会降低ArrayList的使用性能，因此当我们确定添加元素的个数的时候，我们可以事先知道并指定ArrayList的可存储元素的个数，这样当我们向ArrayList中加入元素的时候，就可以避免ArrayList的自动扩容，从而提高ArrayList的性能。