探秘ArrayList源码：Java动态数组的背后实现

比眉伴天荒 2023-09-27 21:28 8阅读 0赞

### 探秘ArrayList源码：Java动态数组的背后实现 ###

*  一、成员变量
 *  二、构造器
 *   *  1、默认构造器
     *  2、带初始容量参数构造器
     *  3、指定collection元素参数构造器
 *  三、add()方法扩容机制
 *  四、场景分析
 *   *  1、对于ensureExplicitCapacity（）方法
     *   *  1.1 add 进第 1 个元素到 ArrayList 时
         *  1.2 当 add 第 2 个元素时
         *  1.3 直到添加第 11 个元素
     *  2、对于grow() 方法：
     *   *  2.1 当 add 第 1 个元素时
         *  2.2 当 add 第 11 个元素进入 grow 方法时
 *  五、心得体会
 *  六、源码简易流程图

--------------------

# 一、成员变量 #

读者需先对源码的成员变量阅览一遍，看个眼熟，有助于后面源码的理解

private static final long serialVersionUID = 8683452581122892189L;
    
        /**
         * 默认初始容量大小
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * 空数组（用于空实例）。
         */
        private static final Object[] EMPTY_ELEMENTDATA = {
        };
    
         //用于默认大小空实例的共享空数组实例。
          //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    
        /**
         * 存储ArrayList元素的数组缓冲区
         */
        transient Object[] elementData; 
    
        /**
         * ArrayList 所包含的元素个数
         */
        private int size;

# 二、构造器 #

## 1、默认构造器 ##

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

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

## 2、带初始容量参数构造器 ##

/**
     * 带初始容量参数的构造函数。（用户自己指定容量）
     */
    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);
        }
    }

## 3、指定collection元素参数构造器 ##

/**
    *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
    *如果指定的集合为null，throws 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;
        }
    }

# 三、add()方法扩容机制 #

在进入ArrayList的核心源码扩容机制前，我们首先需要对源码中涉及到的一些变量进行一个初步的了解，这将有助于你对源码的深入了解

1.  `minCapacity`：数组所需的最小容量
2.  `elementData`：存储ArrayList元素的数组缓冲区

![在这里插入图片描述][8825be6dfd10433a82b370923f8e5012.png]

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

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
        //判断elementData是否为空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //DEFAULTCAPACITY_EMPTY_ELEMENTDATA =  {}
            return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10;minCapacity = 1
        }
        return minCapacity;
    }

private void ensureCapacityInternal(int minCapacity) {
        //minCapacity = 1
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//ensureExplicitCapacity(10)
    }

private void ensureExplicitCapacity(int minCapacity) {
        //minCapacity = 10
        modCount++;
    
        if (minCapacity - elementData.length > 0)//elementData.length = 0
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        //minCapacity = 10
        int oldCapacity = elementData.length;//oldCapacity = 0
        int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity  = 1.5*oldCapacity = 0
        if (newCapacity - minCapacity < 0)//minCapacity = 10
            newCapacity = minCapacity;//newCapacity = 10
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //利用Arrays.copyOf()方法进行扩容
        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;
     }

1.  增加一个新元素，此时所需的最小容量是 `minCapacity = size+1`
2.  首先判断底层数组 `elementData` 是否是空数组
    
     *  如果是空数组，则更新 `minCapacity` 为默认容量10，
     *  如果不是空数组，则对 `minCapacity` 不做变更
3.  判断所需最小容量 `minCapacity` 是否大于缓冲数组 `elementData` 的长度：
    
     *  如果大于，则进行扩容 `grow()`，
     *  否则不做处理
4.  扩容 `grow()`中，首先一上来就将 `elementData` 的长度扩长为原来长度的1.5倍，再对扩容后的 `elementData` 的长度和所需最小的容量 `minCapacity`进行判断
    
     *  如果扩容后的 `elementData` 的长度还小于 `minCapacity` 的长度，说明还是不够，此时就直接将`minCapacity`的长度赋值给`elementData`
     *  否则的话直接进行下一步即可
5.  最后需要对 `elementData` 的长度进行一个是否超过最大限度值`MAX_ARRAY_SIZE`判断
    
     *  如果超过最大限度值，就看看所需的最小容量`minCapacity`是否大于最大限度值`Integer.MAX_VALUE`
     *  如果不是，就将数组的长度扩容为数组的最大限度值`MAX_ARRAY_SIZE`，如果是，则返回`Integer.MAX_VALUE`

# 四、场景分析 #

## 1、对于ensureExplicitCapacity（）方法 ##

### 1.1 add 进第 1 个元素到 ArrayList 时 ###

当我们要 `add` 进第 1 个元素到 `ArrayList` 时，`elementData.length` 为 0 （因为还是一个空的 list），因为执行了 `ensureCapacityInternal()` 方法 ，所以 `minCapacity` 此时为 10。此时，`minCapacity - elementData.length > 0`成立，所以会进入 `grow(minCapacity)` 方法。

### 1.2 当 add 第 2 个元素时 ###

当 add 第 2 个元素时，`minCapacity` 为 2，此时 `elementData.length(容量)`在添加第一个元素后扩容成 10 了。此时，`minCapacity - elementData.length > 0` 不成立，所以不会进入 （执行）`grow(minCapacity)` 方法。  
添加第 3、4···到第 10 个元素时，依然不会执行 `grow` 方法，数组容量都为 10。

### 1.3 直到添加第 11 个元素 ###

`minCapacity(为 11)`比 `elementData.length`（为 10）要大。进入 `grow` 方法进行扩容。

## 2、对于grow() 方法： ##

### 2.1 当 add 第 1 个元素时 ###

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

### 2.2 当 add 第 11 个元素进入 grow 方法时 ###

`newCapacity` 为 15，比 `minCapacity（为 11）`大，第一个 if 判断不成立。新容量没有大于数组最大 size，不会进入 `hugeCapacity` 方法。数组容量扩为 15，add 方法中 return true,size 增为 11。以此类推······

# 五、心得体会 #

1.  变量 `minCapacity` 理解为我们添加元素进ArrayList集合中，底层数组所需的**最小容量**
2.  变量 `elementData.length` 理解为我们添加元素进ArrayList集合中，底层数组的**最大限度容量**
3.  当最小容量 `minCapacity`> **最大限度容量** `elementData.length` ,必定会触发扩容机制。
4.  我们总是频繁地向ArrayList集合添加元素，开发人员也想到了这点，所以在ArrayList集合的扩容机制中，当我们添加第一个元素时，直接就把`minCapacity`设置为10，此处可以理解为，因为我们后续要频繁添加元素，为了不总是触发该集合的扩容机制，便“谎称”所需的最小容量是10，所以系统就直接把`elementData.length`设置为10

# 六、源码简易流程图 #

![在这里插入图片描述][b35dbcd4b0764828b65f76c5f028f4c5.png]

[8825be6dfd10433a82b370923f8e5012.png]: https://img-blog.csdnimg.cn/8825be6dfd10433a82b370923f8e5012.png
[b35dbcd4b0764828b65f76c5f028f4c5.png]: https://img-blog.csdnimg.cn/b35dbcd4b0764828b65f76c5f028f4c5.png