目录

先从 ArrayList 的构造函数说起

一步一步分析 ArrayList 扩容机制

先来看 add 方法

再来看看 ensureCapacityInternal() 方法

ensureExplicitCapacity()和calculateCapacity方法

下面我们接着来看grow() 方法

再来看一下grow()中调用的hugeCapacity() 方法

System.arraycopy() 和 Arrays.copyOf()方法

System.arraycopy() 方法

Arrays.copyOf()方法

两者联系和区别

ensureCapacity方法

---

ArrayList的扩容是自动触发的所需要的空间大于ArrayList此时真正的空间时就会触发扩容每次扩容1.5倍。其实我们就可以理解为当我们把ArrayList中的数组都用完了后再往里面加入元素是就会触发扩容操作。

我们现在分析一下JDK1.8的扩容机制

先从 ArrayList 的构造函数说起

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

/**
 * 默认初始容量大小
 */
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 *默认构造函数使用初始容量10构造一个空列表(无参数构造)
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 带初始容量参数的构造函数。用户自己指定容量
 */
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元素的列表这些元素利用该集合的迭代器按顺序返回
*如果指定的集合为nullthrows NullPointerException。
*/
public ArrayList(Collection<? extends E> 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 扩容时会讲到这一点内容

补充JDK6 new 无参构造的 ArrayList 对象时直接创建了长度是 10 的 Object[] 数组 elementData 。

ArrayList的默认数组大小为什么是10

据说是因为sun的程序员对一系列广泛使用的程序代码进行了调研结果就是10这个长度的数组是最常用的最有效率的。也有说就是随便起的一个数字8个12个都没什么区别只是因为10这个数组比较的圆满而已。

一步一步分析 ArrayList 扩容机制

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

先来看 add 方法

/**
 * 将指定的元素追加到此列表的末尾。
 */
public boolean add(E e) {
    // 添加元素之前先调用ensureCapacityInternal方法用于确认容量插入元素之前会检查是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}

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

再来看看 ensureCapacityInternal() 方法

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

private void ensureCapacityInternal(int minCapacity) {
    // 进一步确认ArrayList的容量看是否需要进行扩容
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

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

该方法和之前JDK7 代码格式化略有不同但是其他核心代码是基本一样的整体源码思路也是一致的。

ensureExplicitCapacity()和calculateCapacity方法

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

// 该方法就是确认一下此时需要的空间大小
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果elementData为空则返回默认容量和minCapacity中的最大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 否则直接返回minCapacity
    return minCapacity;
}

// 判断是否需要扩容并调用扩容方法
private void ensureExplicitCapacity(int minCapacity) {
    // 修改次数自增
    modCount++;
    // overflow-conscious code
    // 判断是否需要扩容
    if (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此时 elementData.length(容量)在添加第一个元素后扩容成 10 了。此时minCapacity - elementData.length > 0 不成立所以不会进入 执行grow(minCapacity) 方法。
• 添加第 3、4....到第 10 个元素时依然不会执行 grow 方法数组容量都为 10。
• 直到添加第 11 个元素minCapacity(此时为11)比 elementData.length此时为 10要大。所以继续进入 grow 方法进行扩容。

这里我们插一句说一下JDK1.7在这一块代码上的区别注意只是代码的写法上有一点点区别但是整体的流程思路完全一样的。ArrayList在1.7和1.8版本区别并不大整体的源码和思路基本是一致的大多数的方法源码都是一样的。

下面是JDK1.7版本的ensureCapacityInternal方法源码

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

这里并没有和JDK1.8一样调用 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

其实如果细心一下我们就可以发现其实JDK1.7的这一段代码是将JDK1.8中的calculateCapacity和ensureExplicitCapacity两个方法整合在了一起而已代码流程其实是完全一样的。所以ArrayList其实在JDK1.7和JDK1.8上区别并不大。扩容章节如果没有特殊说明的源码JDK1.7和JDK1.8都是一样的。

下面我们接着来看grow() 方法

/**
 * 要分配的最大数组大小
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * ArrayList扩容的核心方法。
 */
private void grow(int minCapacity) {
    // 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 - 8`。
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 将旧数据拷贝到新数组中新数组的长度为newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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 方法。数组容量为 10add 方法中 return true,size 增为 1。
• 当 add 第 11 个元素进入 grow 方法时newCapacity 为 15比 minCapacity为 11大第一个 if 判断不成立。新容量没有大于数组最大 size不会进入 hugeCapacity 方法。数组容量扩为 15add 方法中 return true,size 增为 11。
• 以此类推······

注意

由于数组复制迁移的代价比较大因此建议在创建 ArrayList 对象的时候就指定大概的容量大小从而减触发扩容操作的次数。

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

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

再来看一下grow()中调用的hugeCapacity() 方法

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

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

至此自动扩容机制的流程就基本讲完了。下面来简单总结一下

1. ArrayList创建对象时若未指定集合大小那么初始化大小为0若已指定大小集合大小为指定的大小
2. 当第一次调用add方法时如果一开始未指定集合大小那么就创建一个长度为10的数组也就是将集合长度扩为10。如果第一次添加数据是调用addAll就选择10和加入的集合大小之间的较大值作为扩容大小来进行扩容
3. 之后如果向集合中添加元素再次导致数组满了触发扩容那么先判断将集合扩大1.5倍后是否够用如果仍然不够就将真正所需要最小容量minCapacity作为扩容大小。

总结一下扩容最大值

扩容的时候先判定数组大小。数组是空或者小于10那么在扩容的时候将数组直接分配大小到10。这也是一部分人认为ArrayList最小容量是10的原因。之后每次扩容是变成原数组长度的1.5倍。但是有一个最大值MAX_ARRAY_SIZE:

如果变大1.5倍之后大于这个数MAX_ARRAY_SIZE就会去看当前数组大小到底是多少如果小于该值MAX_ARRAY_SIZE那么直接扩容到最大值MAX_ARRAY_SIZE:

反之大于MAX_ARRAY_SIZE则扩容到真正的最大值Integer.MAX_VALUE

由源码我们就可以知道其实ArrayList的最小长度并不是10而是可以为0最大长度也并不是MAX_ARRAY_SIZEInteger.MAX_VALUE - 8而是Integer.MAX_VALUE。

System.arraycopy() 和 Arrays.copyOf()方法

阅读源码的话我们就会发现 ArrayList 中大量调用了这两个方法。比如我们上面讲的扩容操作以及add(int index, E element)、grow(int minCapacity)、构造方法ArrayList(Collection<? extends E> c)中调用的toArray()等方法中都用到了这两个方法

System.arraycopy() 方法

源码

// 我们发现 arraycopy 是一个 native 方法,接下来我们解释一下各个参数的具体意义
/**
*   复制数组
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPos 目标数组中的起始位置
* @param length 要复制的数组元素的数量
*/
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

场景

/**
 * 在此列表中的指定位置插入指定的元素。
 * 先调用 rangeCheckForAdd 对index进行界限检查然后调用 ensureCapacityInternal 方法保证capacity足够大
 * 再将从index开始之后的所有成员后移一个位置将element插入index位置最后size加1。
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // arraycopy()方法实现数组自己复制自己
    // elementData:源数组index:源数组中的起始位置elementData目标数组
    // index + 1目标数组中的起始位置 size - index要复制的数组元素的数量
    // 其实就是相当于将elementData数组下标index~size-1位置上的数据复制到elementData数组的index+1~size下标位置上去也就是实现了从index开始之后的所有成员后移一个位置
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 最后将element插入到空出来的index位置将size++
    elementData[index] = element;
    size++;
}

个人感觉这个方法主要用来整体移动数组中某个范围上的数据或者做数据的复制迁移。我们写一个简单的方法测试以下

public class ArraycopyTest {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[10];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        System.arraycopy(a, 2, a, 3, 3);
        a[2]=99;
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

结果

0 1 99 2 3 0 0 0 0 0

实现了将数组中原有的2和3向后整体移动了一个位置将下标2位置空了出来根据内存情况随便给这个位置留了一个值。

Arrays.copyOf()方法

源码

public static int[] copyOf(int[] original, int newLength) {
    // 申请一个新的数组
    int[] copy = new int[newLength];
    // 调用System.arraycopy,将源数组中的数据拷贝到新创建的数组中,并返回新的数组
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

该方法本质也是利用System.arraycopy()方法实现的。

场景

/**
 以正确的顺序返回一个包含此列表中所有元素的数组从第一个到最后一个元素; 返回的数组的运行时类型是指定数组的运行时类型。
 */
public Object[] toArray() {
    //elementData要复制的数组size要复制的长度
    return Arrays.copyOf(elementData, size);
}

个人觉得使用 Arrays.copyOf()方法主要是为了给原有数组扩容测试代码如下

public class ArrayscopyOfTest {
    public static void main(String[] args) {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        // 将数组a中的数据复制到一个容量更大的数组b中也就实现了数组的扩容
        int[] b = Arrays.copyOf(a, 10);
        System.out.println("b.length"+b.length);
    }
}

结果

10

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

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

两者联系和区别

联系

看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法copyOf()是基于System.arraycopy() 方法实现的。

区别

• arraycopy() 需要目标数组将原数组拷贝到你自己定义的数组里或者原数组而且可以选择拷贝的起点和长度以及放入新数组中的位置。
•  copyOf() 是系统自动在内部新建一个数组并将旧数组中的数据拷贝到新数组中并返回新数组。

ensureCapacity方法

ArrayList 源码中有一个 ensureCapacity 方法不知道大家注意到没有这个方法 ArrayList 内部没有被调用过所以很显然是提供给用户调用的那么这个方法有什么作用呢

/**
 * 如有必要增加此 ArrayList 实例的容量以确保它至少可以容纳由minCapacity参数指定的元素数。
 * @param   minCapacity   所需的最小容量
 */
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

理论上来说最好在向 ArrayList 添加大量元素之前用 ensureCapacity 方法以减少增量重新分配的次数。也就是在插入大量元素之前先将数组的容量扩建成要加入元素数量的大小这样就可以在加入元素的过程中不触发扩容操作避免多次数组扩容后数据迁移带来的性能损耗。

我们通过下面的代码实际测试以下这个方法的效果

1、加入元素之前不使用ensureCapacity方法

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法前"+(endTime - startTime));
    }
}

运行结果

使用ensureCapacity方法前2158

2、加入元素之前使用ensureCapacity方法

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后"+(endTime1 - startTime1));
    }
}

运行结果

使用ensureCapacity方法后1773

通过运行结果我们可以看出向 ArrayList 添加大量元素之前使用ensureCapacity 方法可以提升性能。不过这个性能差距几乎可以忽略不计。而且实际项目根本也不可能往 ArrayList 里面添加这么多元素。

至此我们就讲完了扩容流程的源码从源码层面理解的扩容的原理。

---

参考链接https://javaguide.cn/java/collection/arraylist-source-code.html#arraylist-%E6%89%A9%E5%AE%B9%E6%9C%BA%E5%88%B6%E5%88%86%E6%9E%90

---

 相关文章【Java集合】ArrayList源码分析