＜Java八股文面试＞ArrayList源码 | Iterator源码 | LinkedList和ArrayList对比（上）

/**
     * 
     * 方法功能:测试ArrayList的扩容规则
     * 1.ArrayList扩容前20次的结果:
     * [0, 10, 15, 22, 33, 49, 73, 109, 163, 244, 366,549, 823, 1234, 1851, 2776, 4164, 6246, 9369, 14053, 21079]
     * 2.步骤分析:22 = 15 + (15 >> 2); 49 = 33 + (33 >> 2)
     * 3.可以看出,当元素个数为100个时,需要扩容的大小为109.
     */
private static List<Integer> arrayListGrowRule(int n) {
    List<Integer> list = new ArrayList<Integer>();
    int init = 0;
    list.add(init);
    if (n >= 1) {
        init = 10;
        list.add(init);
    }
    for (int i = 1; i < n; i++) {
        init += (init) >> 1;
        list.add(init);
    }
    return list;
}
/**
     * 方法功能:当集合为空时,使用addAll()向集合中添加元素
     * addAll方法扩容原理:下次扩容容量 和 实际元素个数之间选一个最大值.
     */
private static void testAddAllGrowEmpty() {//
    ArrayList<Integer> list = new ArrayList<Integer>();
    // list.addAll(List.of(1, 2, 3));//此时输出的length为10,
    list.addAll(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11));//此时输出的length为11=> max(11,10)_
    System.out.println(length(list));
}
/**
     * 方法功能:当集合不为为空时,使用addAll()向集合中添加元素
     */
private static void testAddAllGrowNotEmpty() {
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < 10; i++) {
        list.add(i);
    }
    // list.addAll(List.of(1, 2, 3));//此时输出的length为15=>max(15,13)
    list.addAll(List.of(1, 2, 3, 4, 5, 6));//此时输出的length为16=>max(15,16)
    System.out.println(length(list));
}

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    /**
     * 默认初始化容量
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 为空实例赋值的空数组对象.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
     * 空数组对象,和上面用途稍微不一样.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
     * 存放元素的数组对象
     */
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     * 元素个数
     */
    private int size;
    //无参构造
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//初始化为一个空数组
    }
    //参数为容量的有参构造
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//容量值为负数则抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    //参数为集合的有参构造
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {//集合不为空,则创建一个新的数组,并将元素复制到新数组里,elementData指向新数组.
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {// 如果是一个空集合初始化赋值,则直接将其赋值为空数组.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
}

//计算需要扩容的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果在添加的时候远数组是空的，取默认容量与minCapacity之间的最大值.
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 扩容后的为 Max(默认容量 , 加入元素后的容量) ,这样可以保证只扩容一次.
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //如果ArrayList不为空,就返回加入元素后的容量 (之前的元素容量+1) 
    return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果所需容量 比 elementData实际的容量 要小，则需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);//扩容
}
//注意:minCapacity代表加入 元素后需要的容量
//elementData:实际存放元素的数组, 和 minCapacity大小关系不确定.

//扩容方法
private void grow(int minCapacity) {
    //获取到ArrayList中elementData数组的内存空间长度
    int oldCapacity = elementData.length;
    //计算扩容后的大小:扩容至原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 再判断一下新数组的容量够不够，够了就直接使用这个长度创建新数组. 如果不够,则直接使用minCapacity 的值,这样可以避免重复扩容. 
    if (newCapacity - minCapacity < 0)
        // 不够就将数组长度设置为需要的长度
        newCapacity = minCapacity;
    //若预设值大于默认的最大值检查是否溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
    // 并将elementData的数据复制到新的内存空间
    elementData = Arrays.copyOf(elementData, newCapacity);
}