ArrayList底层逻辑与实现

重点

扩容规则：底层是System.arraycopy()这个方法

1. 每次扩容都是将新容量设置为1.5 * 旧容量
2. 新容量如果小于需要的容量，将新容量设置为需要的容量
3. 新容量如果大于可以分配的最大容量（整型最大值 - 8），新容量设置为（需要的容量小于最大分配容量）需要的容量或者设置为（需要的容量大于最大分配容量）整型最大值

懒加载机制：ArrayList初始化的时候并没有直接给数组分配容量，而是使用的一个空数组进行赋值，只有当第一次增加的时候才会真正的给数组进行容量分配。这样是为了防止用户初始化后没有进行使用导致内存的浪费。（只有用户调用无参构造方法的时候才是懒加载，其他两个构造函数是分配的另外一个空数组）

属性

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

// 用来表示当用户输入初始容量为0时的数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 用来表示是懒加载的数组，与EMPTY_ELEMENTDATA做区分
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 用来存储元素
transient Object[] elementData;

// 用来记录已经存储了的元素数量
private int size;

构造方法

我们可以看到我们经常用的List<Integer> arr = new ArrayList<>()，并没有一开始给我们初始化为默认的10容量，而是先赋值的是一个空数组。这里其实就是懒加载的开始，

public ArrayList() {
    // 使用的是懒加载的空数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    ......
    if (initialCapacity == 0) {
        // 使用的是非懒加载的空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
    ......
}

public ArrayList(Collection<? extends E> c) {
    ......
    if (size == 0)
        // 使用的是非懒加载的空数组
        elementData = EMPTY_ELEMENTDATA;
    }
}

重要方法

add()

public boolean add(E e) {
    // 用来确定是否需要扩容
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

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

/**
 * 实现懒加载的方法
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 判断当前数组是否是懒加载的数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果是的话返回max(默认初始容量，需要的容量)
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 如果不是直接返回需要的容量
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    // 用于记录操作数量
    modCount++;

    // 如果需要的容量小于数组容量，进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 扩容函数
 * 每次在原来基础上一半一半的扩容。
 * 如果新容量还是小于需要的容量，将新容量设为需要的容量
 * 如果新容量大于最大分配的容量：
 *      1. 需要的容量也大于。将新容量设置为整型的最大值
 *      2. 需要的容量小于，将新容量直接设置为需要的容量
 */
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);
}

简易实现

/**
 * @author zmm
 * @date 2021/11/11 15:12
 */
public class ArrList<E>{

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

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

    /**
     * 空的数组集合，用于懒加载
     */
    private static final Object[] EMPTY_ELEMENT_DATA = {};

    /**
     * 用来记录已经存放了的数据个数
     */
    private int size;

    /**
     * 用来存放数据
     */
    private Object[] elementData;

    public ArrList() {
        // 注意：这里是给数组赋值的空数组
        this.elementData = EMPTY_ELEMENT_DATA;
    }

    public ArrList(int initCapacity) {
        // 这里直接就给数组进行了初始化
        if (initCapacity < 0){
            throw new IllegalArgumentException("Illegal Capacity");
        } else if (initCapacity == 0){
            this.elementData = EMPTY_ELEMENT_DATA;
        } else {
            this.elementData = new Object[initCapacity];
        }
    }

    /**
     * 添加一个新元素
     * @param e             新元素
     */
    public void add(E e) {
        lazyLoad();
        size++;
        if (size > elementData.length) {
            grow();
        }
        elementData[size] = e;
    }

    /**
     * 在指定下标处添加元素
     * @param index         下标
     * @param element       元素
     */
    public void add(int index, E element) {
        if (index < 0 || index > elementData.length) {
            throw new IllegalArgumentException("Illegal index");
        }
        lazyLoad();
        size++;
        if (size > elementData.length) {
            grow();
        }
        // 将原数组下标在index及以后的所有元素复制到以index + 1开始的下标处
        System.arraycopy(elementData, index, elementData,
                 index + 1, size - index - 1);
        elementData[index] = element;
    }

    /**
     * 获取指定下标处的元素
     * @param index         下标
     * @return              指定下标处的元素
     */
    @SuppressWarnings("unchecked")
    public E get(int index) {
        if (index < 0 || index > size){
            throw new IllegalArgumentException("Illegal index");
        }
        return (E) elementData[index];
    }

    /**
     * 修改指定下标处的元素
     * @param index         下标
     * @param element       新元素
     */
    public void set(int index, E element) {
        if (index < 0 || index > size){
            throw new IllegalArgumentException("Illegal index");
        }
        elementData[index] = element;
    }

    /**
     * 懒加载机制
     * 当调用第一次添加的时候才对数组进行初始化操作
     * 如果当类加载后直接进行初始化，而用户未使用
     * 这样就会导致额外的内存浪费
     * 所以这就是为什么刚初始化ArrayList，显示的容量为0
     * 添加后就变成了10
     */
    private void lazyLoad() {
        if (size == 0){
            this.elementData = new Object[DEFAULT_CAPACITY];
        }
    }

    /**
     * 扩容函数
     * 每次在原来基础上一半一半的扩容。
     * 如果新容量还是小于需要的容量，将新容量设为需要的容量
     * 如果新容量大于最大分配的容量：
     *      1. 需要的容量也大于。将新容量设置为整型的最大值
     *      2. 需要的容量小于，将新容量直接设置为需要的容量
     */
    private void grow() {
        int oldSize = elementData.length;
        int newSize = oldSize + (oldSize >> 1);
        if (newSize - size < 0) {
            newSize = size;
        }
        if (newSize > MAX_ARRAY_SIZE){
            newSize = size > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
        }
        elementData = Arrays.copyOf(elementData, newSize);
    }
}