ArrayList 扩容源码浅析

你的名字 2024-04-06 11:51 74阅读 0赞

#### ArrayList ####

*   *  一.概述
     *  二.扩容
     *   *   *  add()
             *  ensureCapacityInternal()
             *  ensureExplicitCapacity()
             *  总结：

### 一.概述 ###

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

ArrayList是List接口下的一个实现类，它可以动态的修改数组，数组元素①有序②可重复；  
ArrayList中维护了一个Object类型的数组 `elementData` ；  
可以加入null，并且可以加入多个；  
ArrayList基本等同于Vector，但是ArrayList是线程不安全的；

### 二.扩容 ###

首先ArrayList底层是一个 `Object[ ] elementData` 数组；

##### add() #####

尝试插入一个元素的时候，会调用add方法，先判断是否需要扩容，将元素个数size+1作为参数传入 ensureCapacityInternal；

public boolean add(E e) {
        
        // 确认插入这个元素以后是否需要扩容 ？
        ensureCapacityInternal(size + 1);
        // 添加元素至数组尾部
        elementData[size++] = e;
        return true;
    }

##### ensureCapacityInternal() #####

size+1作为参数 minCapacity 传进来后，在 `calculateCapacity` 方法中， 和DEFAULT\_CAPACITY (10)比较，10 > 1，所以calculateCapacity方法返回 10；  
即如果数组为空，则初始化为10；

private void ensureCapacityInternal(int minCapacity) {
        
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
        
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
        // 如果当前的这个数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则直接扩容到DEFAULT_CAPACITY，也就是说，第一次add元素的时候会扩容到10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
           return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

##### ensureExplicitCapacity() #####

将 `calculateCapacity` 的返回值作为参数 `minCapacity` ，调用 **ensureExplicitCapacity**() 方法，判断：如果minCapacity 大于elementData 长度时，触发扩容 `grow`方法；

private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++;
        // 判断插入了当前元素后是否超过了数组的容量，是的话调用grow方法扩容 
        if (minCapacity - elementData.length > 0)
          grow(minCapacity);
    }

private void grow(int minCapacity) {
        
        // overflow-conscious code
        // 记录原来数组的长度
        int oldCapacity = elementData.length;
        // 新的容量就是原来数组长度的 1.5 倍，这里使用右移效率更高
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新的容量比最小容量小，就直接把最小容量赋值给新的容量
        // 如果不是，就不用变化
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果超出临界值，就调用 hugeCapacity 方法
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        // 进行扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    // 临界值
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

##### 总结： #####

1.  add()添加元素时，先判断数组是否需要扩容，将size+1作为参数传入 `ensureCapacityInternal`，判断size+1是否小于10，如果当前是即数组为空，就将容量初始化为10；
2.  `ensureCapacityInternal` 会执行 `ensureExplicitCapacity` ，参数是minCapacity也就是之前的siez+1，而当 `minCapacity` 大于elementData长度length时，触发扩容 `grow`；
3.  使用`>>1` 右移操作将 length扩大为之前的1.5倍并创建新数组，使用`Arrays.copyOf` 将元素复制到新数组；

参考：  
https://blog.csdn.net/efggfxfvhh/article/details/126432671  
https://blog.csdn.net/m0\_52462015/article/details/121552324  
https://blog.csdn.net/m0\_56085369/article/details/124182172

[eb9a60495e844e979f9a1448b45e9a58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/02e039da9c0f487ea4c9b93688d50898.png