剖析Java 集合框架(二)-List

序

    周末早上又被深圳特色修路的嘟嘟嘟声轰醒，打开手机，习惯性的点开了Boss直聘，想到工作，想到简历，瞬间清醒，深深感受到这世界的恶意。不过就像我自己要求的，不能怨天尤人，不能自怨自艾，调整心态继续热爱生活。
    感谢小平给我做的爱心早餐，煮的牛奶木瓜(好像发现了盲点~)，煎鸡蛋。小平开始就在是要煎鸡蛋还是煎糍粑还是手抓饼纠结，发现比我这天秤座还能纠结，但是我正抑郁于个人简历中，掩饰自己烦躁的心情和语气，选了个鸡蛋。话说鸡蛋煎的针不戳，外脆内舒，口感十足。奈何cc没文化，一句nb走天下。我想说的是工作跟生活还是要分开，放宽心态，对身边的人要好。与君共勉！

1. ArrayList

1.1 概述

List 接口的可伸缩数组实现。支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。在添加大量元素之前，使用 ensureCapacity 操作，可以减少增量重新分配的数量。
size、isEmpty、get、set。iterator 和 listIterator 操作以常量运行。add 操作以分摊常量时间运行，即添加n个元素需要O(n)。其他所有的操作近似于线性时间运行。

List 接口的可伸缩数组实现。支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。在添加大量元素之前，使用 ensureCapacity 操作，可以减少增量重新分配的数量。
size、isEmpty、get、set。iterator 和 listIterator 操作以常量运行。add 操作以分摊常量时间运行，即添加n个元素需要O(n)。其他所有的操作近似于线性时间运行。

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

1.2 构造函数

ArrayList 有三种方式来初始化，构造方法如下：
删除了中间的其他逻辑代码

 // 默认初始容量大小
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;

 // 默认无参构造函数，构造一个初始容量为十的空列表。 
 // 当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
     // 构造具有指定初始容量的空列表。
public ArrayList(int initialCapacity) {
        this.elementData = new Object[initialCapacity]; 
    //...
}

// 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。 
 public ArrayList(Collection<? extends E> c) {//...}

1.3 扩容

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。
扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

public boolean add(E e) {
    //先调用ensureCapacityInternal方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //添加元素就是为数组赋值
    elementData[size++] = e;
    return true;
}
//保证容量足够
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      // 最小也得为10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
 // 最大数组大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 扩容为原始容量 * 1.5;
    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); 
}

1.4 删除元素

需要调用 System.arraycopy() 将随后的元素向左移动( index+1 的元素都复制到 index 位置上)，该操作的时间复杂度为 O(N)，可以看到 ArrayList 删除元素的代价是非常高的。

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

1.5 System.arraycopy()和Arrays.copyOf()方法

先看看 System.arraycopy()的声明，该方法用了native关键字，说明调用的是其他语言写的底层函数。

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

再看Arrays.copyOf(), 仔细观察发现，copyOf()内部调用了System.arraycopy()方法

//该方法对应不同的数据类型都有各自的重载方法
//original:要复制的数组;newLength:要返回的副本的长度;newType:要返回的副本的类型
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

总结：

1. copyOf()内部调用了System.arraycopy()方法;
2. arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置
3. copyOf()是系统自动在内部新建一个数组，调用arraycopy()将原数组拷贝到一个长度为newLength的新数组中，并返回该数组。

1.6 ensureCapacity方法

ArrayList 源码头部的注释里面有提到，在添加大量元素之前，使用 ensureCapacity 操作，可以减少增量重新分配的数量。这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，我们来看看这个方法有什么作用？

//如果需要，增加此 ArrayList实例的容量，以确保它至少可以容纳最小容量参数指定的元素数。
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        ? 0
        : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

最好在 add 大量元素之前用 ensureCapacity 方法，直接一次扩容到位，防止频繁触发扩容，影响性能。

1.7 序列化

所谓的 JAVA 序列化与反序列化，序列化就是将 JAVA 对象以一种的形式保持，比如存放到硬盘，或是用于传输。反序列化是序列化的一个逆过程。
JAVA 规定被序列化的对象必须实现java.io.Serializable 这个接口，而我们分析的目标 ArrayList 同样实现了该接口。
如果一个类不仅实现了 Serializable 接口，而且定义了 readObject（ObjectInputStream in）和 writeObject(ObjectOutputStream out)方法，那么将按照如下的方式进行序列化和反序列化：

ObjectOutputStream 会调用这个类的writeObject方法进行序列化。
ObjectInputStream 会调用相应的readObject方法进行反序列化。

ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。

transient Object[] elementData; // non-private to simplify nested class access

ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    // Read in size, and any hidden stuff
    s.defaultReadObject();
    // Read in capacity
    s.readInt(); // ignored
    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);
        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}
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);
    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

序列化时使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

1.8 Fail-Fast

fail-fast 机制是 Java 集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationExceptio。

LinkedList

LinkedList 是以双向链表实现的，插入、删除时只需要改变前后两个节点指针指向即可，无需移动其他元素。
LinkedList 继承自 AbstractSequentialList 接口，同时了还实现了 Deque, Queue 接口。LinkedList 底层的链表结构使它支持高效的插入和删除操作, 也具有队列的特性。

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;     // size：集合的长度
    transient Node<E> first;   // first：双向链表头部节点
    transient Node<E> last;    // last：双向链表尾部节点

针对 first 变量和 last 变量，我们看到是 Node 类的实体，这是一个静态内部类，类中通过 item 变量保存了当前节点的值，通过 next 变量指向下一个节点，通过 prev变量指向上一个节点。

private static class Node<E> {
    E item;       //节点值
    Node<E> next; //后继节点
    Node<E> prev; //前驱节点
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList结构图

添加元素

add(E e) 和 add(int index, E element) 没有本质区别，都是通过新建一个 Node 实体，同时指定其 prev 和 next 来实现，不同点在于需要调用 node(int index)通过传入的index来定位到要插入的位置，这个也是比较耗时的。

public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * 设置元素e为最后一个元素
*/
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}


// 在指定位置添加元素
public void add(int index, E element) {
    checkPositionIndex(index); //检查索引是否处于[0-size]之间

    if (index == size)//添加在链表尾部
        linkLast(element);
    else//添加在链表中间
        linkBefore(element, node(index));
}

LinkedList 插入效率高是相对的，因为它省去了 ArrayList 插入数据可能的数组扩容和数据元素移动时所造成的开销，但数据扩容和数据元素移动却并不是时时刻刻都在发生的。

LinkedList插入元素
删除操作原理同插入相反，基本逻辑可参照上图从插入后到插入前的变化。

get

我们知道随机读取元素不是 LinkedList 所擅长的，读取效率比起 ArrayList 也低得多，那么我们一起来看一下为什么。

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

/**
 * 返回一个指定索引的非空节点.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

从上述代码中我们可以看到 get(int index)方法的实现机制是:往后或往前遍历查找。也就是说越靠近中间的元素，遍历的次数越多，效率也就越低。因此在使用 LinkedList 的时候，我们不建议使用这种方式读取数据，可以使用 getFirst()，getLast()方法，将直接用到类中的first和last变量。

Arraylist 与 LinkedList 区别?

1. 是否保证线程安全：都是不同步的，也就是不保证线程安全；
2. 底层数据结构：Arraylist 底层使用的是动态数组；LinkedList 底层使用的是 双向链表
3. 时间复杂度：ArrayList 访问时O(1)，但是删除(移动后面的元素)/添加(扩容时复制元素)O(n)。LinkedList 访问平均为o(n)，删除/添加需要先访问到对应位置近视O(n)。
4. 内存空间占用：ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

Vector

同步

Vector 的实现与 ArrayList 类似，但是基本每个方法都用 synchronized 进行同步。保证了相对安全。

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public synchronized E remove(int index) {
      modCount++;
      if (index >= elementCount)
          throw new ArrayIndexOutOfBoundsException(index);
      E oldValue = elementData(index);
      int numMoved = elementCount - index - 1;
      if (numMoved > 0)
          System.arraycopy(elementData, index+1, elementData, index,
                           numMoved);
      elementData[--elementCount] = null; // Let gc do its work
      return oldValue;
}

public synchronized E get(int index) {//...}

扩容

Vector 的构造函数可以传入 capacityIncrement 参数，它的作用是在扩容时使容量 capacity 增长 capacityIncrement。如果这个参数的值小于等于 0，扩容时每次都令 capacity 为原来的两倍。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 调用没有 capacityIncrement 的构造函数时，capacityIncrement 值默认为 0，
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
  //...
}

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
public Vector() {
    this(10);
}

Vector 与 ArrayList 的比较

• Vector 是同步的，因此性能会受到影响，访问速度更慢。
• Vector 每次扩容请求其大小的 2 倍（也可以通过构造函数设置增长的容量），而 ArrayList 是 1.5 倍。

CopyOnWriteArrayList

概述

写入时复制（CopyOnWrite，简称COW）思想是计算机程序设计领域中的一种优化策略。其核心思想是，如果有多个调用者（Callers）同时要求相同的资源（如内存或者是磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者视图修改资源内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。此做法主要的优点是如果调用者没有修改资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。
CopyOnWriteArrayList 的读写分离：

• 写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。
• 写操作需要加锁，防止并发写入时导致写入数据丢失。
• 写操作结束之后需要把原始数组指向新的复制数组。
  内部持有一个 ReentrantLock;底层是用 volatile transient 声明的数组 array

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}
final void setArray(Object[] a) {
    array = a;
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    return (E) a[index];
}

适用场景

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。比如白名单，黑名单，商品类目的访问和更新场景等等。
CopyOnWrite 的缺点

1. 内存占用：写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右。
2. 数据不一致：只能保证数据的最终一致性，不能保证数据的实时一致性。因为部分写操作的数据还未同步到读数组中。

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

后记

感谢各位观众姥爷看到最后。很不容易，磕磕碰碰，铿锵铿锵挤出来了，可能对于很多大佬都是基本知识，不过还是希望能帮助到人，和加深自己的理解。