List 原理分析 - ArrayList - 《Java Core》

RandomAccess
Cloneable
- 浅拷贝
Serializable
ArrayList 的几个属性
关于扩容
指定下标添加元素
删除元素
迭代器
小知识点

说到 ArrayList 通常都会有一道面试题，ArrayList 和 LinkedList 有什么区别？一般都会说，ArrayList 的底层是数组实现，LinkedList 底层是链表实现，故 ArrayList 的查找快，LinkedList 的插入快，那么这么说是正确的么？还是片面了？

先看 ArrayList 的实现

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

我们可以看到 ArrayList 集成了 RandomAccess, Cloneable, java.io.Serializable 三个接口，我们先说这三个接口的作用

RandomAccess

RandomAccess 只是一个标志接口，没有任何内容，实现这个这个接口的 List 集合是支持快速随机访问（下标访问）的

public interface RandomAccess {
}

也就是说，实现了这个接口的集合是支持 快速随机访问 策略的。同时，官网还特意说明了，如果是实现了 RandomAccess 接口的 List，那么使用 for 循环的方式获取数据会优于用迭代器获取数据。

if(object instanceof RandomAccess) {
    // 使用 for 循环遍历
}

Cloneable

拷贝的都是栈中的对象

Cloneable 是一个标记接口，实现了这个接口，就可以实现克隆

public interface Cloneable {
}

浅拷贝

基本类型是独立的，不受干扰，引用类型是不是独立的，会受干扰，String 类型除外

String 类型虽然是引用类型，但是 String 类型是 final 修饰的，不可被修改，所以 String 类型也不会受干扰

Serializable

Serializable 是一个标记接口，实现了这个接口的类，就可以实现序列化，他需要一个版本号 serialVersionUID 属性，private static final long serialVersionUID = -3790927052270933690L; 这个属性就是类的指纹信息，就可以实现序列化和反序列化（存盘、网络传输）

public interface Serializable {
}

ArrayList 的几个属性

/**
 * 默认的容量
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * 当指定了容量，且没有添加元素时，就会使用 EMPTY_ELEMENTDATA 来指向 ArrayList
 * 表示 ArrayList 是一个空集合
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * 当没有指定容量，且没有添加元素时，就会使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 来指向 ArrayList
 * 表示 ArrayList 是一个空集合
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * 真正存储数据的数组
 */
transient Object[] elementData;
/**
 * 数组的长度
 */
private int size;

那么 EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都表示一个空集合，那么他们有什么区别呢？为什么这么设计呢？其实这样做是为了判断加载因子，为扩容做准备

由于空集合指向的是 private static final Object[] EMPTY_ELEMENTDATA = {} ，且这个数组是 static 修饰的，所以无论我们创建多少个空集合 new ArrayList<>(); 都只会指向同一个空数组对象，也就是 EMPTY_ELEMENTDATA 这样做的原因是为了节约空间**

关于扩容

modCount：记录操作数，是做 fail-fast 用的minCapacity = 当前集合的容量 + 1

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

当现有的集合元素为数组的长度时候，就会触发扩容机制

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

默认先计算：新的容量 = 老的容量 + 老的容量的一半

新的容量 - 要扩容的容量 < 0，就是用要扩容的容量
新的容量 - Integer.MAX_VALUE - 8 > 0，那么可能就超出最大范围了，会抛出 OOM

否则新的容量就等于 Integer.MAX_VALUE

private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
  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);
}

最后其实就是复制数组操作，完成扩容

指定下标添加元素

如果指定下标添加元素，在判断完扩容的后，会直接拷贝从要添加的元素位置到最后一个元素，然后将当前的 index 赋值给新的值

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

删除元素

计算出要从当前 index 开始要移动的元素数量，然后进行向前拷贝

public E remove(int 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;
}

迭代器

使用迭代器删除元素不会报错的原因是因为 modCout 会更新

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = 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();
        }
    }
}

小知识点

如果可以计算出容量，可以指定容量大小，减少扩容次数