【Java 基础】ArrayList 的底层原理和源码分析

左手的ㄟ右手 2024-03-16 14:18 45阅读 0赞

tip：作为程序员一定学习编程之道，一定要对代码的编写有追求，不能实现就完事了。我们应该让自己写的代码更加优雅，即使这会费时费力。

推荐：[体系化学习Java（Java面试专题）][Java_Java]

#### 文章目录 ####

*  一、简介
 *  二、自动扩容机制
 *  三、add方法的源码分析
 *  四、addAll方法的源码分析
 *  五、set方法的源码分析
 *  六、remove方法的源码分析
 *  七、Fail-Fast机制

## 一、简介 ##

ArrayList 是 Java 中常用的动态数组实现，它的底层是基于数组实现的。当创建一个 ArrayList 对象时，实际上是创建了一个 Object 类型的数组，初始容量为 10。当添加元素时，如果数组已满，ArrayList 会自动扩容，它会创建一个新的数组，并将原数组中的元素复制到新数组中。

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

## 二、自动扩容机制 ##

它的本质是数组，所以扩容机制，我们想想数组怎么扩容的？那么 ArrayList 就是怎么扩容的。

在ArrayList 的源码中，可以看到 ArrayList 内部维护了一个 Object 类型的数组 elementData，这个数组用于存储 ArrayList 中的元素。在添加元素时，ArrayList 会先判断数组是否已满，如果已满，就会调用 ensureCapacityInternal 方法进行扩容。这个方法会计算出新的容量大小，并创建一个新的数组 newElementData，然后将原数组中的元素复制到新数组中，最后将新数组赋值给 elementData。

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

private Object[] elementData;
    
    public ArrayList() {
        
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    public boolean add(E e) {
        
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++;
        if (minCapacity - elementData.length > 0) {
        
            grow(minCapacity);
        }
    }
    
    private void grow(int minCapacity) {
        
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0) {
        
            newCapacity = minCapacity;
        }
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
        
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

add 方法会先调用 ensureCapacityInternal 方法进行扩容，然后将元素添加到数组中。在 ensureCapacityInternal 方法中，会根据当前数组是否为空来决定是否使用默认容量大小 10，然后再调用 ensureExplicitCapacity 方法进行扩容。在 ensureExplicitCapacity 方法中，会计算出新的容量大小，并调用 grow 方法进行扩容。在 grow 方法中，会计算出新的容量大小，然后调用 Arrays.copyOf 方法创建一个新的数组，并将原数组中的元素复制到新数组中，最后将新数组赋值给 elementData。

## 三、add方法的源码分析 ##

public boolean add(E e) {
        
        ensureCapacityInternal(size + 1);  // 检查容量是否足够，不足则进行扩容
        elementData[size++] = e;  // 插入元素到数组的末尾
        return true;
    }

ensureCapacityInternal 方法用于确保ArrayList的容量足够存储新元素。如果当前容量不足，则会进行扩容操作。具体实现可以查看 ensureCapacityInternal 方法的源码;

private void ensureCapacityInternal(int minCapacity) {
        
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++;
        // 如果需要扩容，则调用grow方法进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 将原数组中的元素复制到新数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

在进行扩容时，ArrayList会先将原有数组中的元素复制到一个新的数组中，然后将新数组作为ArrayList的内部数组。这里使用了 Arrays.copyOf 方法进行数组复制操作。

在容量检查和扩容操作之后， add 方法将新元素插入到数组的末尾，并将列表的size属性加1。最后， add 方法返回一个布尔值，表示元素是否成功添加到列表中。

## 四、addAll方法的源码分析 ##

public boolean addAll(Collection<? extends E> c) {
        
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // 检查容量是否足够，不足则进行扩容
        System.arraycopy(a, 0, elementData, size, numNew);  // 将新元素插入到数组的末尾
        size += numNew;
        return numNew != 0;
    }

addAll 方法首先将要添加的元素转换为数组，然后将新数组中的元素插入到ArrayList的内部数组中。具体实现可以查看以下代码：

Object[] a = c.toArray();  // 将要添加的元素转换为数组
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // 检查容量是否足够，不足则进行扩容
    System.arraycopy(a, 0, elementData, size, numNew);  // 将新元素插入到数组的末尾
    size += numNew;
    return numNew != 0;

在进行容量检查和扩容操作之后， addAll 方法使用 System.arraycopy 方法将新数组中的元素插入到ArrayList的内部数组中。这里需要注意的是， System.arraycopy 方法是一个本地方法，它能够快速地将一个数组中的元素复制到另一个数组中。在将新元素插入到ArrayList的内部数组中之后， addAll 方法会更新列表的size属性，并返回一个布尔值，表示元素是否成功添加到列表中。

## 五、set方法的源码分析 ##

public E set(int index, E element) {
        
        rangeCheck(index);  // 检查索引是否越界
        E oldValue = elementData(index);
        elementData[index] = element;  // 将新元素设置到指定位置
        return oldValue;
    }

set 方法首先会检查指定的索引是否越界，如果越界则会抛出 IndexOutOfBoundsException 异常。具体实现可以查看以下代码：

private void rangeCheck(int index) {
        
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

如果索引没有越界，则 set 方法会将指定位置的元素替换为新元素，并返回原有元素的值。具体实现可以查看以下代码：

E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;

需要注意的是，在将新元素设置到指定位置之前， set 方法会先获取该位置上原有的元素，并将其保存到一个临时变量中。这是因为， set 方法需要返回原有元素的值。

## 六、remove方法的源码分析 ##

public E remove(int index) {
        
        rangeCheck(index);  // 检查索引是否越界
        modCount++;
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null;  // 将最后一个元素置为null，方便垃圾回收
        return oldValue;
    }

remove 方法首先会检查指定的索引是否越界，如果越界则会抛出 IndexOutOfBoundsException 异常。具体实现可以查看以下代码：

private void rangeCheck(int index) {
        
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

如果索引没有越界，则 remove 方法会将指定位置上的元素从ArrayList中移除，并返回原有元素的值。具体实现可以查看以下代码：

modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;
    return oldValue;

在将指定位置上的元素从ArrayList中移除之前， remove 方法会先获取该位置上原有的元素，并将其保存到一个临时变量中。这是因为， remove 方法需要返回原有元素的值。在移除元素之后， remove 方法会将列表的modCount属性加1，表示对列表的修改次数增加了1。此外， remove 方法还会将被移除元素后面的所有元素向前移动一位，以便填补被移除元素的位置。具体实现可以查看以下代码：

int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);

最后， remove 方法将列表的size属性减1，并将被移除的元素置为null，以便垃圾回收。

## 七、Fail-Fast机制 ##

ArrayList的\*\*快速失败机制（Fail-Fast机制）\*\*指的是在多线程环境下，如果一个线程修改了ArrayList的结构（增加、删除或修改元素），那么其他线程在访问ArrayList时，如果发现modCount属性（记录ArrayList结构修改次数的属性）与自己持有的modCount属性不一致，就会抛出ConcurrentModificationException异常，从而防止多个线程同时修改ArrayList的结构，导致数据不一致的情况发生。

快速失败机制是一种保护措施，它能够及时发现并报告程序中的错误，从而避免因为错误的数据导致程序崩溃或者出现其他异常情况。在ArrayList中，快速失败机制的实现是通过modCount属性和一个迭代器的expectedModCount属性来实现的。每当ArrayList的结构发生变化时，modCount属性就会加1，而每个迭代器的expectedModCount属性则会保存它创建时的modCount属性的值。当一个迭代器在遍历ArrayList时，如果发现expectedModCount和modCount不一致，就会抛出ConcurrentModificationException异常，从而保证了遍历的安全性。

[Java_Java]: https://blog.csdn.net/qq_37967783/article/details/130940512
[691c5cc58e92444ebb3063726d610a4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/8bc59bd40a1343aa812721d52c9d4015.png
[dc2db6e9668d4a848fe1382c6955b95a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/5d3d5bda24dd4a6aae6e619e5fc1fcf5.png