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) {//如果数组为空的，那么此时返回默认最小长度间 - 10return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}private void ensureExplicitCapacity(int minCapacity) {//记录修改的次数modCount++;// overflow-conscious codeif (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) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

LinkedList

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

transient Node first; // 首节点transient Node last; // 尾节点private static class Node {E item;Node next; // 前一个对象Node prev; // 后一个对象Node(Node prev, E element, Node 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 l = last;final Node newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.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的扩容机制