从零到Offer -- List的那些事

ArrayList

作为日常最常见的collection对象，相信大家对于ArrayList都不陌生。但是ArrayList的实现你是否又了解呢？开门见山，ArrayList的最底层实现其实就是一个数组：

 transient Object[] elementData;
 ​
 public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

然而我们都知道，java下，一个数组的长度是固定的，是无法变化的。但是实际我们应用ArrayList的时候不难发现，无论你怎么往这个集合中添加元素，他都不会显示越界。相反，数组就像有了魔法一样，会随着你的添加而不断变长。要了解这个原因，就不得不提到add方法。

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

乍一看，add方法本身平平无奇。但是实际上在ensureCapacityInternal方法中，它悄悄为你做了好多事。

 private void ensureCapacityInternal(int minCapacity) {
     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 }
 ​
 //计算长度
 private static int calculateCapacity(Object[] elementData, int minCapacity) {
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         //如果数组为空的，那么此时返回默认最小长度间 - 10
         return Math.max(DEFAULT_CAPACITY, minCapacity);
     }
     return minCapacity;
 }
 ​
 private void ensureExplicitCapacity(int minCapacity) {
     //记录修改的次数
     modCount++;
 ​
     // overflow-conscious code
     if (minCapacity - elementData.length > 0)
         grow(minCapacity);
 }

越界处理

首先看到modCount++这个代码，相信我们在使用中不免有过这样的操作，在for循环中尝试删除/移除一个元素对象：

 for (String s : arrayList) {
     arrayList.remove(s);
 }

然后此时可能就会抛出这样的报错：

其实本质原因是，for循环的代码依赖每个对象的iterator实现的。而iterator又依赖是数组的长度和下标。其是否可以往下循环会通过hasNext进行判断。如果我们随意删除元素，那么此时就可能出现越界。

 public boolean hasNext() {
     return cursor != size;
 }

为了尽早的避免这种情况发生（FailFast原则），ArrayList在设计上就采用一个modCount的变量来记录数组变更的次数，并通过判断迭代器生成时的modCount同循环进行时的modCount进行比较，从而达到目的。

容量变化

除了modCount以外，我们还关注到ArrayList里有grow(minCapacity);这样一句代码，这个其实就是ArrayList能够不断添加元素的关键：

 private void grow(int minCapacity) {
     int oldCapacity = elementData.length;
     // 扩容
     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);
 }

grow中主要做了以下三件事：数组扩容、设置最小长度、判断溢出

数组扩容

在数组扩容上，新的容量长度是通过旧容量*1.5倍（左右）得到的，这里为什么要采用1.5倍而不是2倍也不是1.2倍呢？原因个人理解有两个：

1、添加引发的扩充是很频繁的，因此需要更快的运算速度。而我们都知道位运算运算速度是最快的，自然就不优先考虑1.2、1.4这些用运算较难得到的数字。那么只剩下1.5、2（只需要一次移位）、1.25、4（需要两次移位）的选择了。

2、从上述描述中，我们优先会考虑1.5和2，采用2倍空间进行扩容自然也是可以的，但是实际中2倍扩充会浪费比较多的空间，且数组的空间是无法被GC回收的。因此，为了更少的浪费空间，于是采用了1.5倍这个关键值。

设置最小长度

在设置最小长度的点上，这个相对简单，需要注意的是，虽然初始ArrayList创建时是一个空数组，但是实际ArrayList会保存一个

默认长度，其值为10.

 private static final int DEFAULT_CAPACITY = 10;

判断溢出

ArrayList能扩容不假，但也不能无限创建空间。因此ArraysList为数组的长度划定了一个上限：Integer.MAX_VALUE-8。这里之所以要减8，是为了适配不同VM虚拟机，因为不同的VM虚拟机会保存一部分header头信息。

如果当前长度超过了Integer的最大值，毫无疑问会变成负数。此时系统就会判定为超出了ArraysList的存储大小了。若是当前最小长度介于Integer.MAX_VALUE和Integer.MAX_VALUE-8之间，会默认转换成最大值。

 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 ​
 //判断是否溢出
 private static int hugeCapacity(int minCapacity) {
     if (minCapacity < 0) // overflow
         throw new OutOfMemoryError();
     return (minCapacity > MAX_ARRAY_SIZE) ?
         Integer.MAX_VALUE :
         MAX_ARRAY_SIZE;
 }

LinkedList

介绍完了ArrayList，我们自然还需要介绍他的亲戚LinkedList。与ArrayList明显不同的是，LinkedList底层的实现是基于链表实现的。其中有first、last两个节点，用于保存链表的首节点和尾节点。对于每个node来说，其都会保存其前一个节点的指针及后一个节点的指针。

 transient Node<E> first; // 首节点
 ​
 transient Node<E> last; // 尾节点
 ​
 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;
     }
 }

同arrayList类似，要介绍LinkedList就也得介绍他的add方法：

 public boolean add(E e) {
     linkLast(e);
     return true;
 }
 ​
 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++;
 }

从上可以看到，linkLast()方法其实组成了add方法的全部。相信如果各位学过数据结构与算法的话，一定会对上述代码不陌生。就是一个简单的带尾部节点的链表尾插算法。（不了解的同学就百度一下吧，限于篇幅这里就不展开了。）

同时可以看到LinkedList也会保存一个size变量用于保存数组的长度，避免链表在获取长度时所需要消耗的耗时。与ArrayList类似的是，linkedList也会保存一个modCount变量用于保存数据变更的次数，作用是类似的，这里就不再赘述了。

Vector

上文介绍到的ArrayList和linkedList是我们日常最常使用到的数组结构。但是他们都存在一个缺陷，就是没法应对多并发。LinkedList在多并发下指针可能会紊乱，而ArrayList则可能出现数组越界、数据污染等问题。

为此，Collection包下还有一个数组结构，那就是Vector。那么vector又是如何支持多并发的呢？其实很简单粗暴，vector本身也是采用数组实现的，与ArrayList不同的是，其所有数据变更的方法都采用同步关键字synchronized进行修饰。从而达到同步互斥的逻辑。

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

尽管Vector是支持高并发的，但是由于其实现的方式太过"粗暴"。因此，建议少用，可以选择CopyOnWriteArrayList等其他轻量级的实现。

参考文献：

Java并发编程（十八）Java 并发包中并发List源码剖析

源码角度谈论ArrayList的扩容机制