集合 - 05、ArrayList - 《Java 知识导图》

实现Iterable接口，支持for-each迭代
实现List接口，元素按照有序、可重复
实现Serializable接口，支持序列化、反序列化
实现RandomAccess接口，支持随机访问

实现Cloneable接口，支持克隆

成员变量

  // 默认容量
  private static final int DEFAULT_CAPACITY = 10;
  // 用于空实例的共享空数组实例（有参构造函数）
  private static final Object[] EMPTY_ELEMENTDATA = {};
  // 用于空实例的共享空数组实例（无参构造函数）    
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  /**
   * 用来存储我们的数据，add方法增加的元素存放在这个数组里
   * 【所以ArrayList内部是由数组实现的】
   */
  transient Object[] elementData;
  // 不是elementData数组的长度，而是它包含的数据的长度
  private int size;

transient关键字

transient修饰的变量不是对象持久化的一部分，在对象序列化后访问不到
transient只能修饰变量（本地变量除外），不能修饰类或者方法
transient修饰的变量如果是用户自定义类变量，该类需要实现Serializable接口
被transient修饰的变量不能被序列化，被static修饰的变量无论是否被transient修饰都不能被序列化、

如果对象实现的是Externalizable接口，且指定该变量被序列化，那么无论该变量有没有被transient关键字修饰，都将会被序列化

实现Serializable接口，会自动进行所有的序列化（**transient修饰的除外**）
实现Externalizable接口，不会自动序列化，需要在**writeExternal方法中指定需要序列化的变量（不管transient是否修饰**）

构造方法

ArrayList()

// 初始化一个空实例的list，在第一次新增元素时容量扩展至默认容量
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

初始化一个空元素的elementData数组【DEFAULTCAPACITY_EMPTY_ELEMENTDATA】，在新增元素时会将elementData容量扩展至默认容量（10）

ArrayList(int initialCapacity)

// 初始化一个指定容量（initialCapacity）的list
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);
    }
}

初始化一个指定容量（initialCapacity）的elementData数组

initialCapacity > 0，初始化initialCapacity容量的elementData数组
initialCapacity = 0，初始化一个空元素的elementData数组【EMPTY_ELEMENTDATA】
initialCapacity < 0，抛出非法参数异常

ArrayList(Collection<? extends E> c)

// 根据指定集合（c）创建一个和c集合顺序一致的list
public ArrayList(Collection<? extends E> c) {
    //1. 集合元素转为一个数组传给elementData
    elementData = c.toArray();
    //2. 根据elementData中是否有元素分别处理
    if ((size = elementData.length) != 0) {
        //2.1 elementData不是object[]类型，转成object数组并复制元素
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //2.2 elementData没有元素直接赋值EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

根据集合（c）创建一个和集合（c）顺序一致的新的list

将集合（c）转换成一个Object数组并赋给elementData数组
根据elementData中是否存在元素分别处理
- 存在，确保elementData是Object数组
  - 如果不是Object[]类型，转换为Object[]后将全部元素复制给elementData
  - 是Object[]类型，不需要处理【第一步elementData = c.toArray();已经处理】
- 不存在，EMPTY_ELEMENTDATA直接赋值给elementData

有参数构造方法使用EMPTY_ELEMENTDATA构造空实例数组
无参数构造方法使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA构造空实例数组

常用方法

增

boolean add(E e)

集合列表末尾追加一个集合元素，添加成功返回true

// 列表末尾增加一个指定元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

集合新增元素执行步骤

确保集合存储元素的数组elementData数组容量充足
elementData数组中最后一个元素后追加新元素 ```java //确定列表容量：判断是否需要扩容 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }

// 计算新增元素后列表容量 private static int calculateCapacity(Object[] elementData, int minCapacity) { //通过无参构造方法创建的列表，添加第一个元素时需要将列表扩容至默认容量（10） if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }

// 确保集合容量充足，不够就扩容 private void ensureExplicitCapacity(int minCapacity) { // 修改次数+1 modCount++;

// 集合数组容量不足
if (minCapacity - elementData.length > 0)
    // 扩容
    grow(minCapacity);

}

保证elementData容量步骤：
- 计算新增元素后列表容量
   - 通过无参构造方法创建的实例，首次添加元素时会将容量扩展至默认容量（10）
   - 否则，计算新的容量就是当前elementData数组存储的元素个数 + 1
- 列表结构修改次数modCount增加1
- 确保集合容量足够存放新元素，不够就扩容
```java
// 扩容
private void grow(int minCapacity) {
    // 数组之前的容量
    int oldCapacity = elementData.length;
    // 新的容量 = 1.5 * 之前的容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 扩容后容量还小于添加元素需要的最小容量，新容量赋值为添加元素需要的最小容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 扩容后新容量大于MAX_ARRAY_SIZE，根据需要的最小容量计算新容量
    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 int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 溢出
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

扩容步骤：

在之前容量的基础上扩容1.5倍
扩容后的容量（newCapacity）和添加新元素所需的最小容量（minCapacity）进行比较
- 如果newCapacity < minCapacity，那么newCapacity = minCapacity
- 如果newCapacity >= minCapacity
  - newCapacity和MAX_ARRAY_SIZE（要分配数组最大的大小）进行比较
    - newCapacity > MAX_ARRAY_SIZE
      - newCapacity > Integer.MAX_VALUE，溢出，值变成int类型的负值，OOM异常
      - newCapacity < Integer.MAX_VALUE，设置容量为Integer>MAX_VALUE

void add(int index, E element)

将指定元素插入列表的指定位置，该位置元素（如果有）和后面的所有元素全部向右移（索引加一），不需要返回

// 将指定元素插入列表的指定位置，该位置元素（如果有）和后面的所有元素全部向右移（索引加一）
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * System类本地方法
 *        从源数组srcPos位置开始复制length个元素到目标数组（从destPos位置开始）
 * @param      src      源数组
 * @param      srcPos   源数组起始位置
 * @param      dest     目标数组
 * @param      destPos  目标数组起始位置
 * @param      length      需要复制的长度
 */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos, int length);

boolean addAll(Collection<? extends E> c)

将集合c中的全部元素都添加到集合中

/**
 * 按照指定集合的Iterator返回的顺序，将指定集合中的所有元素追加到此列表的末尾
 * 如果在操作进行过程中修改了指定的集合，则此操作的行为是不确定的
 *（这意味着如果指定的集合是这个列表自己，并且这个列表是非空的，则此调用的行为是不确定的）
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // modCount++
    // 复制a数组中的元素到集合末尾
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

如果在操作进行过程中修改了指定的集合，则此操作的行为是不确定的（这意味着如果指定的集合是此列表，并且此列表是非空的，则此调用的行为是不确定的）
e.g、list.addAll(list)的过程中又对list进行了其他操作，结果就不能确定了

boolean addAll(int index, Collection<? extends E> c)

将集合c中的全部元素从集合指定位置index开始依次添加到集合中

/**
 * 按照指定集合的Iterator返回的顺序，将指定集合中的所有元素追加到此列表的指定位置
 * 如果在操作进行过程中修改了指定的集合，则此操作的行为是不确定的
 *（这意味着如果指定的集合是此列表，并且此列表是非空的，则此调用的行为是不确定的）
 */
public boolean addAll(int index, Collection<? extends E> c) {
    //1. 范围检查
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    //2. 确保集合容量（是否需要扩容）
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //3. 计算需要移动的元素个数
    int numMoved = size - index;
    if (numMoved > 0)
        //3.1 index位置及其后面的所有元素复制到从index+numNew开始的位置
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    //4. 将c中所有元素复制到第3步中空出的位置
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

删

E remove(int index)

删除指定位置元素，返回被删除的元素

/**
 * 删除此列表中指定位置的元素
 * 将所有后续元素向左移动（从其索引中减去一个）
 */
public E remove(int index) {
    // 范围检查，index是否在列表实际长度之内
    rangeCheck(index);
    // 修改次数+1
    modCount++;
    // index位置的值
    E oldValue = elementData(index);
    // 需要移动的元素个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // index后的全部元素向前移动一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

操作步骤：

范围检查
删除指定位置元素
该位置后续所有元素向左移动一位

boolean remove(Object o)

删除列表中第一次出现的指定元素，返回删除是否成功

/**
 * 删除列表中第一次出现的指定元素
 * 如果存在指定元素，则从该列表中删除该元素的第一次出现。 如果列表不包含该元素，则该元素不变
 * 更正式地，根据(o==null ? get(i)==null : o.equals(get(i)))删除具有最低索引（i）的元素
 * 如果此列表包含指定的元素（或者列表由于调用该方法而发生修改），则返回true
 */
public boolean remove(Object o) {
    // 目标元素为null
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else { // 目标元素不为null
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
// 私有删除方法，跳过边界检查并且不返回删除的值
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
}

操作步骤：

找到指定元素（o）第一次出现的位置，找不到返回false
调用快速删除方法删除该元素（没有返回值）
返回操作结果（boolean类型）

void removeRange(int fromIndex, int toIndex)

    /**
     * 从此列表中删除索引在fromIndex（含）和toIndex（不包含）之间的所有元素 
     * 将所有后续元素向左移动（减少其索引）
     * 此调用通过（toIndex-fromIndex）元素来缩短列表，如果toIndex == fromIndex，则此操作无效
     */
    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;
    }

操作步骤：

根据toIndex计算需要移动的元素个数
将需要移动的元素从fromIndex开始复制到elementData中
重新计算集合现有元素数量，需要清空的元素开始位置newSize
从newSize位置开始将后续位置元素置为null

boolean retainAll(Collection<?> c)、boolean removeAll(Collection<?> c)

    /**
     * 仅保留此列表中指定集合中包含的元素
     * @param c 包含要保留在此列表中的元素的集合
     */
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    /**
     * 从此列表中删除指定集合中包含的所有元素
     * @param c 包含此列表中要被删除的元素集合
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }
    /**
     * 指出指定的对象引用不是null
     */
    public static <T> T requireNonNull(T obj) {
        if (obj == null)
            throw new NullPointerException();
        return obj;
    }

boolean batchRemove(Collection<?> c, boolean complement)

/**
     * 批量删除集合c中的所有元素
     * @param c 
     * @param complement 是否保留
     *        true：集合中只保留在集合c中存在的元素
     *        false：集合中删除包含在集合c中的所有元素
     */
    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 {
            // 即使c.contains（）抛出异常，仍保留与AbstractCollection的行为兼容性
            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;
    }

集合A：a、1、b、2、c、3、d 删除集合B：1、2、3
A.batchRemove(B, false)操作步骤：
步骤一：【r：读，w：写】将所有不需要删除的元素移动到集合左侧并记录最后一个不需要删除元素现在的位置

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

循环次数	r	w	contains()	if()	当前元素	交换	集合全部元素
1	0	0	false	true	a	e[0]=e[0]	a、1、b、2、c、3、d
2	1	1	true	false	1	不交换	a、1、b、2、c、3、d
3	2	1	false	true	b	e[2]=e[1]	a、b、b、2、c、3、d
4	3	2	true	false	2	不交换	a、b、b、2、c、3、d
5	4	2	false	true	c	e[4]=e[2]	a、b、c、2、c、3、d
6	5	3	true	false	3	不交换	a、b、c、2、c、3、d
7	6	3	false	true	d	e[6]=e[3]	a、b、c、2、c、3、2

步骤二：将步骤一中w之后的元素全部置为null【清除】

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;
}

改

E set(int index, E element)

用指定元素替换该列表中指定位置的元素

    /**
     * 用指定元素替换该列表中指定位置的元素
     *
     * @param index 需要替换的指定位置
     * @param element 替换的新元素
     * @return 返回该位置之前的元素
     * @throws IndexOutOfBoundsException
     */
    public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

查

E get(int index)

返回列表指定位置的元素

    /**
     * 返回列表指定位置的元素
     *
     * @param  index 需要返回元素的位置
     * @return  列表指定位置的元素
     * @throws IndexOutOfBoundsException
     */
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

克隆

Object clone()

返回该ArrayList实例的浅拷贝副本（元素本身不会被复制）

    /**
     * 返回该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);
        }
    }

序列化、反序列化

void writeObject(java.io.ObjectOutputStream s)

序列化：将ArrayList实例的状态保存到流中（对其进行序列化）

    /**
     * 序列化该ArrayList实例
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();
        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);
        // 将集合元素按顺序写入流中
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        // 序列化过程中如果该ArrayList实例发生变化会抛出异常
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

序列化的是elementData实际上存储的集合元素，而不是实例化整个elementData数组所有的元素
序列化过程中如果该ArrayList实例发生变化会抛出异常

void readObject(java.io.ObjectInputStream s)

反序列化：从流中重构ArrayList实例（反序列化）

    /**
     * 从流中重构ArrayList实例（反序列化）
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
        // 读到ArrayList的size、实际存储元素等信息
        s.defaultReadObject();
        // 读到ArrayList的容量
        s.readInt(); // ignored
        if (size > 0) {
            // 像clone（）一样，根据大小而不是容量分配数组
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);
            Object[] a = elementData;
            // 按顺序读入全部元素
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

elementData使用**transient关键字修饰的原**因，就是JDK不想把整个elementData数组都序列化/反序列化，而只是将size和实际存储的元素序列化或反序列化，从而节省空间和时间

迭代器

Iterator iterator()

以正确的顺序返回此列表中元素的迭代器

    /**
     * 以正确的顺序返回此列表中元素的迭代器
     * 返回的迭代器是一个快速失败的迭代器
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

Itr

优化AbstractList的Itr迭代器

    /**
     * AbstractList迭代器的优化
     */
    private class Itr implements Iterator<E> {
        int cursor;       // 下一个要返回元素的下标
        int lastRet = -1; // 最后一次返回元素的下标，没有就返回-1
        int expectedModCount = modCount; // 期望的modCount
        Itr() {}
        /**
         *    是否有下一个元素
         */
        public boolean hasNext() {
            return cursor != size;
        }
        /**
         *    获取下一个元素
         */
        @SuppressWarnings("unchecked")
        public E next() {
            // 检查集合是否发生变化
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        /**
         * 删除迭代器当前迭代到的集合元素
         */
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                // 删除迭代器目前迭代到的元素
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        /**
         * 检查modCount和期望的是否一致，检查迭代过程中集合是否发生变化
         * 不一致就抛出ConcurrentModificationException，快速失败（fast-fail）机制
         */
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

测试迭代器使用

public class ArrayListDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        list.add("ee");
        System.out.println("list = " + list);
        // 抛出ConcurrentModificationException
        for (String s : list) {
            list.remove(2);
        }
        // 不会抛异常，但是[aa, bb, cc, dd, ee]执行完结果是[aa, bb]
        for (int i = 0; i < list.size(); i++) {
            list.remove(2);
        }
        // 抛出ConcurrentModificationException
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String str = it.next();
            if ("cc".equals(str)) {
                list.remove(str);
            }
        }
        // 抛出ConcurrentModificationException
        Iterator<String> it2 = list.iterator();
        while (it2.hasNext()) {
            String str = it2.next();
            if ("cc".equals(str)) {
                it2.remove();
            }
        }
        System.out.println("list = " + list);
    }
}

快速失败（fast-fail）机制：
多个线程同时对集合进行操作时，一个线程通过Iterator迭代器对集合遍历，其他线程修改了该集合内容，此时就会抛出ConcurrentModificationException触发fast-fail

迭代器迭代时会检查modCount是否发生变化【checkForComodification()方法】，发生变化就抛出ConcurrentModificationException
- 所以如果想要在迭代过程中删除元素不抛出ConcurrentModificationException，可以使用迭代器Itr内部的remove方法实现