写在最后面

这个我的项目是从 20 年末就立好的 flag，通过几年的学习，回过头再去看很多知识点又有新的了解。所以趁着找实习的筹备，联合以前的学习储备，创立一个次要针对应届生和初学者的 Java 开源常识我的项目，专一 Java 后端面试题 + 解析 + 重点常识详解 + 精选文章的开源我的项目，心愿它能随同你我始终提高！

阐明：此我的项目内容参考了诸多博主（已注明出处），材料，N 本书籍，以及联合本人了解，从新绘图，从新组织语言等等所制。集体之力菲薄，或有不足之处，在劫难逃，但更新 / 欠缺会始终进行。大家的每一个 Star 都是对我的激励！心愿大家能喜爱。

注：所有波及图片未应用网络图床，文章等均开源提供给大家。

我的项目名: Java-Ideal-Interview

Github 地址：Java-Ideal-Interview – Github

Gitee 地址：Java-Ideal-Interview – Gitee（码云）

继续更新中，在线浏览将会在前期提供，若认为 Gitee 或 Github 浏览不便，可克隆到本地配合 Typora 等编辑器舒服浏览

若 Github 克隆速度过慢，可抉择应用国内 Gitee 仓库

• 一 ArrayList 源码剖析（含扩容机制剖析）

  • 1. ArrayList 概述

    • 1.1 List 是什么？
    • 1.2 ArrayList 是什么？
    • 1.3 程序表的优缺点
    • 1.4 工夫复杂度证实

  • 2. 外围源码剖析

    • 2.1 类申明
    • 2.2 类成员
    • 2.4 构造方法
    • 2.5 最小化实例容量办法
    • 2.5 扩容办法
    • 2.6 惯例办法

  • 3. 重点内容分析

    • 3.1 扩容机制再剖析

      • 3.1.1 ArrayList 是如何被初始化的

      • 3.1.2 扩容机制流程剖析（无参结构为例）

        • 3.1.2.1 add()
        • 3.1.2.2 ensureCapacityInternal()
        • 3.1.2.3 calculateCapacity()
        • 3.1.2.4 ensureExplicitCapacity
        • 3.1.2.5 grow()
        • 3.1.2.6 hugeCapacity()

    • 3.2 System.arraycopy() 和 Arrays.copyOf() 复制办法

      • 3.2.1 System.arraycopy()
      • 3.2.2 Arrays.copyOf()
    • 3.3 removeAll() 和 retainAll() 中的 batchRemove() 办法

    • 3.4 并发批改异样问题摸索

      • 3.4.1 起因解释：

      • 3.4.2 解决方案：

        • 3.4.2.1 形式 1：迭代器迭代元素，迭代器批改元素
        • 3.4.2.1 形式 2：汇合遍历元素，汇合批改元素（一般 for）
      • 3.4.3 iterator.remove() 的弊病

一 ArrayList 源码剖析（含扩容机制剖析）

1. ArrayList 概述

1.1 List 是什么？

List 在 Collection 中充当着一个什么样的身份呢？——有序的 collection(也称为序列)

实现这个接口的用户以对列表中每个元素的插入地位进行准确地管制。用户能够依据元素的整数索引（在列表中的地位）拜访元素，并搜寻列表中的元素。与 set 不同，列表通常容许反复的元素。

1.2 ArrayList 是什么？

ArrayList 的底层就是一个数组，依赖其扩容机制（前面会提到）它可能实现容量的动静增长，所以 ArrayList 就是数据结构中程序表的一种具体实现。

其特点为：查问快，增删慢，线程不平安，效率高。

1.3 程序表的优缺点

长处：

1. 逻辑与物理程序统一，程序表可能依照下标间接 疾速的存取元素
2. 毋庸为了示意表中元素之间的逻辑关系而减少额定的存储空间

毛病：

1. 线性表长度须要初始定义，经常难以确定存储空间的容量，所以只能以升高效率的代价应用扩容机制
2. 插入和 删除操作须要挪动大量的元素，效率较低

1.4 工夫复杂度证实

读取：

还记的这个公式吗？

$$Loc(a_i) = Loc(a_1) + (i -1)*L$$

通过这个公式咱们能够在任何时候计算出线性表中任意地位的地址，并且对于计算机所应用的工夫都是雷同的，即一个常数，这也就意味着，它的工夫复杂度为 O(1)

插入和删除：

咱们以插入为例子

• 首先最好的状况是这样的，元素在开端的地位插入，这样无论该元素进行什么操作，均不会对其余元素产生什么影响，所以它的工夫复杂度为 O(1)
• 那么最坏的状况又是这样的，元素正好插入到第一个地位上，这就意味着前面的所有元素全副须要挪动一个地位，所以工夫复杂度为 O(n)
• 均匀的状况呢，因为在每一个地位插入的概率都是雷同的，而插入越靠前挪动的元素越多，所以均匀状况就与两头那个值的肯定次数相等，为 (n – 1) / 2，均匀工夫复杂度还是 O(n)

总结：

读取数据的时候，它的工夫复杂度为 O(1)，插入和删除数据的时候，它的工夫复杂度为 O(n)，所以线性表中的程序表更加适宜解决一些元素个数比较稳定，查问读取多的问题

2. 外围源码剖析

2.1 类申明

先来看一下类的申明，有一个继承（抽象类）和四个接口关系

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{// 源码具体内容...}

• RandomAccess 是一个标记接口（Marker）只有 List 汇合实现这个接口，就能反对疾速随机拜访（通过元素序号疾速获取元素对象 —— get(int index)）
• Cloneable：实现它就能够进行克隆（clone()）
• java.io.Serializable：实现它意味着反对序列化，满足了序列化传输的条件

2.2 类成员

上面接着看一些成员属性

// 序列化主动生成的一个码，用来在正反序列化中验证版本一致性。private static final long serialVersionUID = 8683452581122892189L;

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

/**
 * 指定 ArrayList 容量为 0（空实例）时，返回此空数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 与 EMPTY_ELEMENTDATA 的区别是，它是默认返回的，而前者是用户指定容量为 0 才返回
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 具体寄存元素的数组
 * 保留增加到 ArrayList 中的元素数据（第一次增加元素时，会扩容到 DEFAULT_CAPACITY = 10）*/
transient Object[] elementData; // non-private to simplify nested class access

/**
 * ArrayList 理论所含元素个数（大小）*/
private int size;

2.4 构造方法

/**
 * 带参构造函数，参数为用户指定的初始容量
 */
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {
        // 参数大于 0，创立 initialCapacity 大小的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 参数为 0，创立空数组（成员中有定义）this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 其余状况，间接抛异样
        throw new IllegalArgumentException("Illegal Capacity:"+
                                           initialCapacity);
    }
}

/**
 * 默认无参构造函数，初始值为 0
 * 也阐明 DEFAULT_CAPACITY = 10 这个容量
 * 不是在构造函数初始化的时候设定的（而是在增加第一个元素的时候）*/
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

/**
 * 结构一个蕴含指定 collection 的元素的列表
 * 这些元素是依照该 collection 的迭代器返回它们的顺序排列的。*/
public ArrayList(Collection<? extends E> c) {
    // 将给定的汇合转成数组
    elementData = c.toArray();
    // 如果数组长度不为 0
    if ((size = elementData.length) != 0) {
        // elementData 如果不是 Object 类型的数据，返回的就不是 Object 类型的数组
        if (elementData.getClass() != Object[].class)
            // 将不是 Object 类型的 elementData 数组，赋值给一个新的 Object 类型的数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 数组长度为 0，用空数组代替
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

2.5 最小化实例容量办法

/**
 * 最小化实例容量办法，能够依据理论元素个数，将数组容量优化，避免节约
 */
public void trimToSize() {
    modCount++;
    // 数组容量大于理论元素个数（例如 10 个元素，却有 15 个容量）if (size < elementData.length) {
        // 依据元素理论个数，从新最小化实例容量
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

2.5 扩容办法

这里只是依照程序介绍，前面还会专门针对扩容进行一个剖析

/**
 * 减少 ArrayList 实例的容量，如果有必要，确保它至多能够保留由最小容量参数指定的元素数量。*/
public void ensureCapacity(int minCapacity) {
    // 如果元素数组不为默认的空，则 minExpand 的值为 0，反之值为 10
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;
    // 如果最小容量大于已有的最大容量
    if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);
    }
}

/**
 * 计算最小扩容量（被调用）*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
     // 如果元素数组为默认的空
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 获取“默认的容量”和“传入参数 minCapacity”两者之间的最大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

/**
 * 失去最小扩容量
 */
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}


/**
 * 判断是否须要扩容
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    // 如果最小容量比数组的长度还大
    if (minCapacity - elementData.length > 0)
        // 就调用 grow 办法进行扩容
        grow(minCapacity);
}

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

/**
 * ArrayList 扩容的外围办法
 */
private void grow(int minCapacity) {
    // 将以后元素数组长度定义为 oldCapacity 旧容量
    int oldCapacity = elementData.length;
    // 新容量更新为旧容量的 1.5 倍
    // oldCapacity >> 1 为按位右移一位，相当于 oldCapacity 除以 2 的 1 次幂
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 而后查看新容量是否大于最小须要容量，若还小，就把最小须要容量当作数组的新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 再查看新容量是否超出了 ArrayList 所定义的最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 若超出，则调用 hugeCapacity()
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
    
/**
 * 比拟 minCapacity 和 MAX_ARRAY_SIZE
 */
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

2.6 惯例办法

/**
 * 返回元素数量
 */
public int size() {return size;}

/**
 * 此列表元素数量为 0 则返回 true
 */
public boolean isEmpty() {return size == 0;}

/**
 * 此列表含有指定元素，则返回 true
 */
public boolean contains(Object o) {return indexOf(o) >= 0;
}

/**
 * 返回此列表中元素首次呈现地位的索引
 * 若不蕴含此元素，则返回 -1
 */
public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        // 实质就是循环 equals 比对
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

/**
 * 返回此列表中指定元素的最初一次呈现的索引
 * 如果此列表不蕴含元素，则返回 -1
 */
public int lastIndexOf(Object o) {if (o == null) {for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        // 逆向循环 equals 比对
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}


/**
 * 返回 ArrayList 实例的浅拷贝
 */
public Object clone() {
    try {ArrayList<?> v = (ArrayList<?>) super.clone();
        // 实现数组的复制，参数为被复制者的参数
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

/**
 * 返回一个蕴含此列表中所有元素的数组（了解为将汇合转为数组即可）*/
public Object[] toArray() {return Arrays.copyOf(elementData, size);
}

/**
 * 将 list 转化为你所须要类型的数组，而后返回
 */
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    // 复制用法，上面专题会解说此内容
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

// Positional Access Operations

@SuppressWarnings("unchecked")
E elementData(int index) {return (E) elementData[index];
}

/**
 * 返回此列表中指定地位的元素。*/
public E get(int index) {
    // index 范畴查看
    rangeCheck(index);
    return elementData(index);
}

/**
 * 用指定的元素替换此列表中指定地位的元素。*/
public E set(int index, E element) {
    // index 范畴查看
    rangeCheck(index);
    // 依据 index 找到想替换的旧元素
    E oldValue = elementData(index);
    // 替换元素
    elementData[index] = element;
    return oldValue;
}

/**
 * 将指定的元素追加到此列表的开端。*/
public boolean add(E e) {
    // 确认 list 容量，尝试容量加 1，看看有无必要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 赋值
    elementData[size++] = e;
    return true;
}

/**
 * 在此列表中的指定地位插入指定的元素
 * 再将从 index 开始之后的所有成员后移一个地位；将 element 插入 index 地位；最初 size 加 1。*/
public void add(int index, E element) {
    // 调用 rangeCheckForAdd 对 index 进行范畴查看
    rangeCheckForAdd(index);
    // 保障容量足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 本人复制本人，而后达到 index 之后全副元素向后挪一位的成果
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 而后将 index 赋值为指定的元素
    elementData[index] = element;
    size++;
}

/**
 * 移除该列表中指定地位的元素。将任何后续元素挪动到左侧（从其索引中减去一个元素）。*/
public E remove(int index) {
    // 调用 rangeCheckForAdd 对 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; // clear to let GC do its work
    return oldValue;
}

/**
 * 从汇合中移除第一次呈现的指定元素
 */
public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)
            if (elementData[index] == null) {fastRemove(index);
                return true;
            }
    } else {
        // 也很简略，就是一个循环 equals 判断，而后移除
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {fastRemove(index);
                return true;
            }
    }
    return false;
}

/*
 * 跳过范畴查看的删除形式，与 remove(Object o)雷同
 */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

/**
 * 从列表中删除所有元素。*/
public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        // 元素全副设为 null
        elementData[i] = null;
    // 长度设为 0
    size = 0;
}

/**
 * 按指定汇合的 Iterator 返回的程序
 * 将指定汇合中的所有元素追加到此列表的开端。*/
public boolean addAll(Collection<? extends E> c) {
    // 转为数组
    Object[] a = c.toArray();
    // 拿到待增加指定数组的长度
    int numNew = a.length;
    // 确认 list 容量，尝试容量加上 numNew，看看有无必要扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 利用 arraycopy 指定数组 a 的元素追加到以后数组 elementData 后
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

/**
 * 按指定汇合的 Iterator 返回的程序
 * 将指定汇合中的所有元素增加到此列表中，从指定地位开始
 * 
 */
public boolean addAll(int index, Collection<? extends E> c) {rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 计算须要挪动的元素
    int numMoved = size - index;
    if (numMoved > 0)
        // 实现元素指定地位的插入，实质还是 arraycopy 本身
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

/**
 * 删除指定索引范畴内的元素（fromIndex - toIndex）* 将任何后续元素挪动到左侧（缩小其索引）。*/
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {elementData[i] = null;
    }
    size = newSize;
}

/**
 * 查看给定的索引是否在范畴内。*/
private void rangeCheck(int index) {
    // 下标越界就间接抛异样
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 另一个版本，针对 add 和 addAll 应用
 */
private void rangeCheckForAdd(int index) {if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 与下面套娃应用
 */
private String outOfBoundsMsg(int index) {return "Index:"+index+", Size:"+size;}

/**
 * 从此列表中删除指定汇合中蕴含的所有元素。*/
public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
 * 仅保留此列表中蕴含在指定汇合中的元素。即删掉没有的局部
 */
public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);
    return batchRemove(c, true);
}

/**
 * 删除的具体逻辑，上面会有专题解说
 */
private boolean batchRemove(Collection<?> c, boolean complement) {final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {for (; r < size; r++)
            // 通过循环判断数组中有没有指定数组中的每一个值，complement 是参数传递的
            if (c.contains(elementData[r]) == complement)
                // 就将原数组的 r 地位的数据笼罩掉 w 地位的数据
                // r 地位的数据不变，并其 w 自增，r 自增
                // 否则，r 自增，w 不自增
                // 实质：把须要移除的数据都替换掉，不须要移除的数据前移
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

// writeObject readObject 序列化相干的省略
   
/**
 * 列表迭代器：List 汇合特有的迭代器
 */
public ListIterator<E> listIterator(int index) {if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index:"+index);
    return new ListItr(index);
}


public ListIterator<E> listIterator() {return new ListItr(0);
}

// foreach 遍历等同于 iterator
public Iterator<E> iterator() {return new Itr();
}


private class Itr implements Iterator<E> {
    // 下一个要拜访的元素下标
    int cursor; 
    // 上一个要拜访的元素下标
    int lastRet = -1; 
    // 代表对 ArrayList 批改次数的期望值，初始值为 modCount
    int expectedModCount = modCount;

    Itr() {}

    // 下标如果
    public boolean hasNext() {return cursor != size;}

    /**
     * 刚开始 cursor = 0，lastRet = -1
     * 整个过程完结 cursor 和 lastRet 都会自增 1
     */
    @SuppressWarnings("unchecked")
    public E next() {
        // 跳转实质是判断 modCount 是否等于 expectedModCount
        checkForComodification();
        int i = cursor;
       // 判断 cursor 是否超过汇合大小和数组长度
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        // 将 cursor 赋值给 lastRet，而后把此下标处的元素返回
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        // 先判断 lastRet 的值是否小于 0
        if (lastRet < 0)
            throw new IllegalStateException();
        // 跳转实质是判断 modCount 是否等于 expectedModCount
        checkForComodification();

        try {
            // 间接调用 ArrayList 的 remove 办法删除下标为 lastRet 的元素
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();
        }
    }
    
    // forEachRemaining 略

    final void checkForComodification() {if (modCount != expectedModCount)
            throw new ConcurrentModificationException();}
}

3. 重点内容分析

3.1 扩容机制再剖析

3.1.1 ArrayList 是如何被初始化的

ArrayList 提供了 1 个无参结构和 2 个带参结构来初始化 ArrayList，咱们在创立 ArrayList 时，常常应用无参结构的形式，其本质就是初始化了一个空数组，直到向数组内真的增加元素的时候才会真的去调配容量。例如：向数组中增加第一个元素，数组容量裁减为 10

补充：JDK7 无参结构 初始化 ArrayList 对象时，间接创立了长度是 10 的 Object[] 数组 elementData

3.1.2 扩容机制流程剖析（无参结构为例）

3.1.2.1 add()

一般来说，都是通过 add 办法触发扩容机制，咱们拿最简略的尾部追加的 add() 办法举例

/**
 * 将指定的元素追加到此列表的开端。*/
public boolean add(E e) {
    // 确认 list 容量，尝试容量加 1，看看有无必要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 赋值
    elementData[size++] = e;
    return true;
}

外围要点就这一句 ensureCapacityInternal(size + 1);

3.1.2.2 ensureCapacityInternal()

追踪进去

/**
 * 失去最小扩容量
 */
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

办法内调用了 ensureExplicitCapacity() 办法，参数是 calculateCapacity(elementData, minCapacity)

先来剖析一下这个参数的后果是什么，聚焦到 calculateCapacity() 办法中去

3.1.2.3 calculateCapacity()

/**
 * 计算最小扩容量（被调用）*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
     // 如果元素数组为默认的空
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 获取“默认的容量”和“传入参数 minCapacity”两者之间的最大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

也很简略，就是为了计算出一个最小扩容量，当元素为首次初始化时，数组还没进过扩容，是一个空数组，所以会走 if 这个判断，而且过后传入的 size + 1 也就是 minCapacity 的值为 0 + 1 = 1，通过一个取大值的操作，与默认的 DEFAULT_CAPACITY 进行比对，天然返回的就是 10。

如果数组曾经不是为空了，就间接返回一个 minCapacity（size + 1）就能够了

3.1.2.4 ensureExplicitCapacity

ensureCapacityInternal 办法内调用了 ensureExplicitCapacity(参数曾经计算出来了) 办法

持续去看它

/**
 * 判断是否须要扩容
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    // 如果最小容量比数组的长度还大
    if (minCapacity - elementData.length > 0)
        // 就调用 grow 办法进行扩容
        grow(minCapacity);
}

此办法的外围就是 if 判断这个数组需不需要扩容，能够分为三种状况

• add 第 1 个元素时：此时数组还只是一个被初始化过的空数组，minCapacity 通过 calculateCapacity 计算会返回 DEFAULT_CAPACITY 的默认值 10，而 elementData.length 也天然是 0，所以 minCapacity – elementData.length > 0 是成立的，间接进入 grow(minCapacity); 开始扩容。

• add 第 2 到 10 个元素的时候（以 2 举例）：此时 minCapacity = size + 1 = 1 + 1 = 2，而 elementData.length 曾经在增加第 1 个元素后等于 10 了。所以 minCapacity – elementData.length > 0 就不成立了，所以不会进入 grow(minCapacity);，也不会扩容

  • 增加第 3 … 10 个元素的时候，都是一样的。
• add 第 11 个元素的时候，minCapacity 变成了 11，比 10 还要大，所以又一次进去扩容了

3.1.2.5 grow()

这里是真正去执行扩容逻辑的代码

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

/**
 * ArrayList 扩容的外围办法
 */
private void grow(int minCapacity) {
    // 将以后元素数组长度定义为 oldCapacity 旧容量
    int oldCapacity = elementData.length;
    // 新容量更新为旧容量的 1.5 倍
    // oldCapacity >> 1 为按位右移一位，相当于 oldCapacity 除以 2 的 1 次幂
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 而后查看新容量是否大于最小须要容量，若还小，就把最小须要容量当作数组的新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 再查看新容量是否超出了 ArrayList 所定义的最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 若超出，则调用 hugeCapacity()
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容的外围就是这句：int

newCapacity = oldCapacity + (oldCapacity >> 1);

实质就是扩容 1.5 倍，而且其中应用了移位运算，这里从计算的角度上来看，相当于 oldCapacity 除以 2 的 1 次幂（偶数除以 2 刚好除尽，奇数丢掉小数局部）。应用按位右移，效率会高很多

>> 按位右移运算符：最高位为 0，右边补齐 0，最高位是 1，右边补齐 1

• 疾速计算：把 >> 右边的数据 除以 2 的挪动次幂：例如 -24 >> 2 即：-24 / 2 ^ 2 = -6

—— 此我的项目【001-Java 基础知识】章节中有具体介绍

扩容后，须要对这个新容量的范畴进行一个判断，不能小于最小须要容量，也不能大于定义的最大容量，分状况细细看一下（以 1 和 11 举例，是因为这两种都是刚好须要扩容的）

• add 第 1 个元素的时候，数组还为空，所以无论是 oldCapacity 还是 newCapacity 都是 0，通过第一次判断后，newCapacity = minCapacity 执行了，此时 newCapacity 为 10，第二个判断不会进入，它不可能大于数组的最大容量。
• add 第 11 个元素的时候，oldCapacity 为 10，newCapacity = 10 + 10/2 = 15，大于 minCapacity = 11，第一个判断不会进入，同时它必定也没有大于数组最大 size，不会进入。数组容量此时就扩为 15，add 办法中会返回一个 true，size 也减少成 11。
• 前面都是同样的情理 …

3.1.2.6 hugeCapacity()

这个办法就是在 newCapacity 大于 MAX_ARRAY_SIZE 的时候，开始判断 minCapacity 和 MAX_ARRAY_SIZE 谁大，而后赋予不同的值。

/**
 * 比拟 minCapacity 和 MAX_ARRAY_SIZE
 */
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

3.2 System.arraycopy() 和 Arrays.copyOf() 复制办法

在后面的办法中，大量的用到了这两个办法，根本凡是波及到元素挪动的都会用到。

3.2.1 System.arraycopy()

拿 add 办法中的举例

/**
 * 在此列表中的指定地位插入指定的元素
 * 再将从 index 开始之后的所有成员后移一个地位；将 element 插入 index 地位；最初 size 加 1。*/
public void add(int index, E element) {
    // 调用 rangeCheckForAdd 对 index 进行范畴查看
    rangeCheckForAdd(index);
    // 保障容量足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 本人复制本人，而后达到 index 之后全副元素向后挪一位的成果
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 而后将 index 赋值为指定的元素
    elementData[index] = element;
    size++;
}

arraycopy 是 System 类 中的一个办法

/**
 * 数组复制
 *     src - 源数组。*     srcPos - 源数组中的起始地位。*     dest - 指标数组。*     destPos - 目的地数据中的起始地位。*     length - 要复制的数组元素的数量。*/
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

举例：

public static void main(String[] args) {int[] arr = new int[10];
    arr[0] = 11;
    arr[1] = 22;
    arr[2] = 33;
    arr[3] = 44;
    arr[4] = 55;

    System.out.println("前：" + Arrays.toString(arr));
    // 指定下标后向后移动一位
    System.arraycopy(arr, 1, arr, 2, 4);
    // 指定下标处替换元素
    arr[1] = 666;
    System.out.println("后：" + Arrays.toString(arr));
}

运行后果：

前：[11, 22, 33, 44, 55, 0, 0, 0, 0, 0]
后：[11, 666, 22, 33, 44, 55, 0, 0, 0, 0]

这样就实现了 add 中的一个指定下标插入操作（不思考扩容）

3.2.2 Arrays.copyOf()

所以，能够简略的认为，这个办法的目标只有是为了给原数组扩容。

public static void main(String[] args) {int[] arr1 = {1, 2, 3, 4, 5};
    int[] arr2 = Arrays.copyOf(arr1, 5);
    int[] arr3 = Arrays.copyOf(arr1, 10);

    System.out.println(Arrays.toString(arr1));
    System.out.println(Arrays.toString(arr2));
    System.out.println(Arrays.toString(arr3));
}

运行后果：

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]

3.3 removeAll() 和 retainAll() 中的 batchRemove() 办法

在 removeAll() 和 retainAll() 办法中，都调用了 batchRemove()办法，区别只是传参不同，就能实现两种不同的正反删除成果

/**
 * 从此列表中删除指定汇合中蕴含的所有元素。*/
public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
 * 仅保留此列表中蕴含在指定汇合中的元素。即删掉没有的局部
 */
public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);
    return batchRemove(c, true);
}

来重点看一下这个办法的源码

/**
 * 删除的具体逻辑，上面会有专题解说
 */
private boolean batchRemove(Collection<?> c, boolean complement) {final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

解释一下刚开始的那些字段

• size：原数组长度
• elementData：原数组
• modCount：从父类继承过去的变量，作用是记录着汇合的批改次数。

来看第一个要害代码

for (; r < size; r++)
    if (c.contains(elementData[r]) == complement)
        elementData[w++] = elementData[r];

咱们以 removeAll() 为例，用意从此列表中删除指定汇合中蕴含的所有元素。即，有的就删，没有的就不删。

所以 complement 通过参数传递过去天然是 false，所以参数指定数组中不含有原数组指定地位下标的数据的时候，就将 elementData[r] 地位的数据笼罩掉 elementData[w++] 地位的数据，r 依据循环 ++ 自增，w 依据变量 w++ 自增，若 if 表达式不成立则，r 自增，w 不自增。

举例：原数组：[1, 2, 3, 4, 5, 6, 7, 8, 9]，指定参数数组：[a, b, c, 3, 5, 8, f]（例子参考自）从新排版

本人走一遍下面的逻辑，就能粗浅的感触失去

这步的作用：把须要移除的数据都替换掉，不须要移除的数据前移。（这步的解决尤为重要！）

接下来进入 finally 中，这一段是最终必定会执行的

if (r != size) {System.arraycopy(elementData, r,elementData, w,size - r);
    w += size - r;
}
if (w != size) {for (int i = w; i < size; i++)
        elementData[i] = null;
    modCount += size - w;
    size = w;
    modified = true;
}

首先判断 r 是否等于 size，如果下面的循环失常执行完结，r 和 size 应该是雷同的，所以必定不会走下面，第一个 if 判断的目标就是为了解决某种异常情况下（异样，并发批改）导致的 for 循环未完结，此时 r != size 所以通过 arraycopy 将增加的元素追加到 w 索引前面。

而第二个 if，次要是为了把 w 之后没解决过的给删掉，这样就能够达到目标了。

例如下面表格的例子，最初 w = 6，也就是 [1, 2, 4, 6, 7, 9, 7, 8, 9] 中从下标为 6 的元素 7 开始删除，将 7，8，9 赋值为 null 前面会被 GC 清理掉。最初失去的后果 [1, 2, 4, 6, 7, 9] 就是革除过的了。

3.4 并发批改异样问题摸索

public static void main(String[] args) {
    // 创立汇合对象
    List list = new ArrayList();

    // 存储元素
    list.add("I");
    list.add("love");
    list.add("you");

    Iterator it = list.iterator();
    while (it.hasNext()) {String s = (String) it.next();
        if ("love".equals(s)) {list.add("❤");
        }
        System.out.println(s);
    }
}

// 运行后果(节选)
Exception in thread "main" java.util.ConcurrentModificationException

应用加强 for 或者迭代器遍历汇合的时候，如果对汇合进行 list 的 remove 和 add 操作，会呈现 ConcurrentModificationException 并发批改异样的问题。

3.4.1 起因解释：

当咱们对汇合进行遍历的时候，咱们会获取以后汇合的迭代对象

//List 为例，获取汇合的迭代对象
Iterator it = list.iterator();

这个迭代对象中，封装了迭代器的办法与汇合自身的一些办法，当咱们在迭代中应用汇合自身的 add / remove 办法的时候，就产生了 ConcurrentModificationException 异样，艰深的说就是，在判断 equals 胜利后，执行了 list 的 add / remove 办法，操作汇合中元素或者删除减少了，然而迭代器不分明，所以就报错，如果迭代器中含有这一种办法（假如），咱们是用迭代器增加元素就不会有问题了。

具体解释：

• 开始时，cursor 指向下标为 0 的元素，lastRet 指向下标为 -1 的元素，每次调用 next 办法，cursor 和 lastRet 会别离自增 1。
• 当忽然 ArrayList 的 remove 办法被调用（不是 Itr 的 remove），会导致被删除元素前面的所有元素都会往前挪动一位，且 modCount 这个批改次数会减少，持续循环，去执行 next 办法，而 next 办法中首先判断的就是 modCount 和 expectedModCount 是否相等，很显著因为 ArrayList 的操作，导致 modCount 变动，两者当初曾经不等了，所以出现异常

final void checkForComodification() {if (modCount != expectedModCount)
        throw new ConcurrentModificationException();}

针对这个问题，咱们给出两个解决方案

3.4.2 解决方案：

3.4.2.1 形式 1：迭代器迭代元素，迭代器批改元素

咱们假想如果 Iterator 迭代器中有增加或者删除等性能就好了，但很遗憾并没有，然而它的子接口 ListIterator 却领有 add 这个性能（ListIterator 领有 add、set、remove 办法，Iterator 领有 remove 办法，这里只演示 add 办法，remove 办法就用原来的 Iterator .remove()）

ListIterator 的 add()和 Iterator 的 remove() 能够应用的起因都是因为，办法进行了增加删除操作后，都会执行 expectedModCount = modCount 这样的赋值操作，相当于通知迭代器我进行了批改操作。

public static void main(String[] args) {
    // 创立汇合对象
    List list = new ArrayList();
    
    // 存储元素
    list.add("I");
    list.add("love");
    list.add("you");

    ListIterator lit = list.listIterator();
    while (lit.hasNext()) {String s = (String) lit.next();
        if ("love".equals(s)) {
            // add、remove 都是能够的
            lit.add("❤");
        }
        System.out.print(s + " ");
    }
    
    System.out.println();

    for (Object l : list){System.out.print(l + " ");
    }
}

// 运行后果
I love you
I love ❤ you 

3.4.2.1 形式 2：汇合遍历元素，汇合批改元素（一般 for）

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Demo2 {public static void main(String[] args) {
        // 创立汇合对象
        List list = new ArrayList();

        // 存储元素
        list.add("I");
        list.add("love");
        list.add("you");

        for (int x = 0; x < list.size(); x++){String s = (String)list.get(x);
            if ("love".equals(s)){list.add("❤");
            }
            System.out.print(s + " ");
        }
    }
}

// 运行后果
I love you ❤ 

两者均能够解决并发批改异样的问题，然而通过运行后果也能够看出，办法一增加后，在本次遍历中不会输入增加的后果，而办法二却能够。

补充：加强 for 循环实现将汇合进行遍历，也产生了并发批改异样，这是因为加强 for 在底层也是调用的汇合自身的 remove

3.4.3 iterator.remove() 的弊病

• Iterator 只有 remove() 办法，add 办法在 ListIterator 中有
• remove 之前必须先调用 next，remove 开始就对 lastRet 做了不能小于 0 的校验，而 l astRet 初始化值为 -1
• next 后只能调用一次 remove，因为 remove 会将 lastRet 从新初始化为 -1