ArrayList,LinkedList,CopyOnWrite
本文基于JDK1.8
在看dubbo的时候，看到使用了CopyOnWriteArrayList，顺带了解下
ArrayList
底层结构
ArrayList的底层是基于数组的
transient Object[] elementData;
并且默认初始化的大小为0,可以从构造函数看到
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
在默认没有设置大小或者传入Collection为空的情况下，会设置elementData为EMPTY_ELEMENTDATA或者DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这两个常量都是长度为0数组
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
扩容机制
由于数组初始化长度是固定的，所以当个数超过一定限制时，会进行扩容操作，从add方法看起
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
可以看到在对数组增加元素前，会调用ensureCapacityInternal方法进行扩容相关工作
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
在ensureCapacityInternal方法中来确定扩容的最小值，在数组长度为0的情况下，使用默认数组大小，其他情况使用当前数组长度+1,
private static final int DEFAULT_CAPACITY = 10;
然后在ensureExplicitCapacity会判断是否需要进行扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
只有最小扩容长度大于当前的数组长度时，才需要进行扩容，因为minCapacity是数组放入下一个元素后的长度，如果大于 elementData.length，说明当前数组已经放不下下一个数据，需要进行扩容
在grow方法中是具体的扩容逻辑
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);
}
对于初始化为0的数组，会直接扩容为10
对于长度不为0的数组，扩容大小为 oldCapacity + (oldCapacity >> 1)，也就是变为原来的1.5倍
具体扩容的方式，使用Arrays.copyOf(elementData, newCapacity)进行深拷贝处理，新建一个数组，把老数组元素拷贝过去
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
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;
}
关于 System.arraycopy方法，是一个native方法
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
如果是数组比较大，那么使用System.arraycopy会比较有优势，因为其使用的是内存复制，省去了大量的数组寻址访问等时间
SubList
可以调用subList方法来获取当前数组的子数组，对子数组的操作会影响到父数组，因为实际操作对象还是父数组,看下add方法
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
其实parent就指向了父数组
迭代器
在ArrayList中迭代器有2种，Itr和ListItr，分别通过iterator和listIterator拿到，ListItr继承于Itr
使用Itr只支持删除数组中的元素，不支持新增
使用ListItr支持新增,修改操作，但是新增的元素不会迭代出来
Itr的next方法返回的是原数组的引用
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];
}
因此对使用迭代器获取的元素进行修改时，原数组的元素也会被修改
但是在Itr迭代器使用过程中不能对数组内的元素个数进行修改，不然会抛出ConcurrentModificationException异常,主要通过modCount来实现
在得到迭代器的时候，会把当前数组的modCount存到expectedModCount变量中，并且涉及数组元素的修改操作都会对modCount++
当使用next方法获取下一个元素的时候，会使用checkForComodification方法会对比两个modCount，如果不一致，说明数组被修改了，抛出异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
下面看下remove方法的实现
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();
}
}
lastRet保存的是当前元素的index，cursor保存的是下一个元素的index
remove的时候因为把当前元素删除了，后面元素整体向前移动一位，所以cursor就等于lastRet了，并且要重置expectedModCount
继续看下ListItr的add方法
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
在增加元素后，会把cursor向右移动一位，并且重置expectedModCount
线程安全
ArrayList不是线程安全的，如果在多线程进行add的时候，发生了扩容，会发生不可知的错误吧，在多线程中使用ArrayList，需要进行同步
LinkedList
底层结构
LinkedList底层基于链表，会保留first，last 头尾指针，不存在扩容问题
transient Node<E> first;
transient Node<E> last;
Node节点定义如下
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支持对头尾的操作，可以用来当栈，队列
查询优化
因为是链表，所以查询一个元素必须从头或尾开始查找，LinkedList会根据查找元素index进行优化
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;
}
}
size >> 1就是当前长度的中位数
如果在中位数左边，那么从头开始遍历
如果在中位数右边，从尾开始遍历
相比数组的随机访问，链表在查询方面是要慢一些，插入方面，也不一定链表占优，因为涉及到数组插入删除的位子，以及是否扩容问题。
CopyOnWriteArrayList
底层结构
CopyOnWriteArrayList底层基于数组，是一个线程安全的List，进行增删改的时候都会底层数组同步进行覆盖，相当于每次修改都会扩容，主要用于使用迭代器或者foreach的时候返回的是副本，提高遍历效率，但是修改操作性能降低。
修改操作
在修改，增加，删除操作都会使用ReentrantLock进行同步,我们以增加方法示例
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();
}
}
在add方法中会调用Arrays.copyOf方法对原数组进行深拷贝，增加元素后，对原数组进行覆盖
其他修改操作也都会这样做，为什么？在修改操作把底层数组指向新的数组，但是迭代器里面引用的还是老数组，相当于每个迭代器都会存在特定时间点的一个副本，当然，对副本的操作，不会影响到新的底层数组
这个设计很巧妙，并没有弄两个数组来回切换，很好的利用了强引用。
看下CopyOnWriteArrayList中一个变量
private final Object[] snapshot;
会把之前老数组的引用保存下来，
而在ArrayList或者LinkedList使用的都是从外部类拿直接引用，如
Object[] elementData = ArrayList.this.elementData;
总结
ArrayList和LinkedList不是线程安全的，在多线程情况下需要进行同步，
ArrayList底层数组，查询，修改快，插入，删除较慢
LinkedList底层链表插入，删除较快，查询，修改慢，同时可以模拟栈，队列操作
ArrayList和LinkedList不太好对比，和数据量，插入删除位置都有关，量级到一定程度在根据操作择优而选吧，一般使用ArrayList
而CopyOnWriteArrayList是线程安全的，但是也要考虑场景，查询以及遍历是多数操作的情况下适合使用，毕竟每次修改都需要深拷贝，数据量大了也很损耗性能，并且也浪费内存，可能还不如同步的ArrayList
最后
希望大家关注下我的公众号
image
