1.ArrayList继承结构

ArrayList源码 扩容机制分析 - 图1

2.代码分析

2.1 构造方法

ArrayList 有三个构造器，分别为：

1.无参构造器

  1. /**
  2. * 默认初始容量大小
  3. */
  4. private static final int DEFAULT_CAPACITY = 10;
  5. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  7. /**
  8.  *默认构造函数，使用初始容量10构造一个空列表(无参数构造)
  9.  */
  10. public ArrayList() {
  11.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  12. }

该构造器涉及两个变量：elementData 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。这两个变量的定义如下：

  1. transient Object[] elementData; // non-private to simplify nested class access

可以看到 elementData 是一个 Object 类型的数组，该数组也是 ArrayList 作为容器用于存储数据的地方。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个 Object 类型的空数组。因此，该无参构造器的作用就是将 elementData 初始化为一个 Object 类型的空数组。

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

2.指定初始化容量的构造器

该构造器传入一个参数，即初始化内部数组容量的 initialCapacity，如下：

  1. /**
  2.      * 带初始容量参数的构造函数。（用户自己指定容量）
  3.      */
  4.     public ArrayList(int initialCapacity) {
  5.         if (initialCapacity > 0) {//初始容量大于0
  6.             //创建initialCapacity大小的数组
  7.             this.elementData = new Object[initialCapacity];
  8.         } else if (initialCapacity == 0) {//初始容量等于0
  9.             //创建空数组
  10.             this.elementData = EMPTY_ELEMENTDATA;
  11.         } else {//初始容量小于0，抛出异常
  12.             throw new IllegalArgumentException("Illegal Capacity: "+
  13.                                                initialCapacity);
  14.         }
  15.     }

该构造器根据传入的初始容量（initialCapacity）初始化用于存储元素的数组 elementData 变量。当初始容量为 0 时，elementData 被初始化为 EMPTY_ELEMENTDATA，该变量如下：

  1. private static final Object[] EMPTY_ELEMENTDATA = {};

该数组与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是一个空的 Object 数组，二者名字不同是为了区分 ArrayList 初始化时是否指定了容量，后期进行扩容的时候有所不同。

3.指定初始化集合的构造器

该构造器传入一个集合 Collection，即使用 Collection 中的元素初始化 ArrayList 对象，代码如下：

  1. /**
  2.     *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
  3.     *如果指定的集合为null，throws NullPointerException。
  4.     */
  5.     public ArrayList(Collection<? extends E> c) {
  6.         elementData = c.toArray();
  7.         if ((size = elementData.length) != 0) {
  8.             // c.toArray might (incorrectly) not return Object[] (see 6260652)
  9.             if (elementData.getClass() != Object[].class)
  10.                 elementData = Arrays.copyOf(elementData, size, Object[].class);
  11.         } else {
  12.             // replace with empty array.
  13.             this.elementData = EMPTY_ELEMENTDATA;
  14.         }
  15.     }

注意：这里若 Collection 为空时会抛出 NPE，因此初始化前有必要判空。

2.2 扩容机制

2.2.1. 先来看 add 方法

  1. /**
  2.      * 将指定的元素追加到此列表的末尾。
  3.      */
  4.     public boolean add(E e) {
  5.    //添加元素之前，先调用ensureCapacityInternal方法
  6.         ensureCapacityInternal(size + 1);  // Increments modCount!!
  7.         //这里看到ArrayList添加元素的实质就相当于为数组赋值
  8.         elementData[size++] = e;
  9.         return true;
  10.     }

注意 ：JDK11 移除了 ensureCapacityInternal() 和 ensureExplicitCapacity() 方法

2.2.2. 再来看看 ensureCapacityInternal() 方法

（JDK7）可以看到 add 方法 首先调用了ensureCapacityInternal(size + 1)

  1. //得到最小扩容量
  2.     private void ensureCapacityInternal(int minCapacity) {
  3.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  4.               // 获取默认的容量和传入参数的较大值
  5.             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  6.         }
  7.         ensureExplicitCapacity(minCapacity);
  8.     }

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

2.2.3. ensureExplicitCapacity() 方法

如果调用 ensureCapacityInternal() 方法就一定会进入（执行）这个方法，下面我们来研究一下这个方法的源码！

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

我们来仔细分析一下：

  • 当我们要 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 方法进行扩容。

2.2.4. grow() 方法

  1. /**
  2.      * 要分配的最大数组大小
  3.      */
  4.     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  5.     /**
  6.      * ArrayList扩容的核心方法。
  7.      */
  8.     private void grow(int minCapacity) {
  9.         // oldCapacity为旧容量，newCapacity为新容量
  10.         int oldCapacity = elementData.length;
  11.         //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
  12.         //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
  13.         int newCapacity = oldCapacity + (oldCapacity >> 1);
  14.         //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
  15.         if (newCapacity - minCapacity < 0)
  16.             newCapacity = minCapacity;
  17.        // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
  18.        //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
  19.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  20.             newCapacity = hugeCapacity(minCapacity);
  21.         // minCapacity is usually close to size, so this is a win:
  22.         elementData = Arrays.copyOf(elementData, newCapacity);
  23.     }


int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！** 奇偶不同，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

“>>”（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了 1 位所以相当于 oldCapacity /2。对于大数据的 2 进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源


我们再来通过例子探究一下grow() 方法 ：

  • 当 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。
  • 以此类推······

这里补充一点比较重要，但是容易被忽视掉的知识点：
**

  • java 中的 length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
  • java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法.
  • java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!