Java集合-List篇

JDK提供的集合类型主要分为四种类型：

List：支持重复元素
Set：不支持重复元素
Map：键/值对的映射集
Queue/Deque（double ended queue）：queue是在集合尾部添加元素，在头部删除元素的队列，deque是可在头部和尾部添加或者删除元素的双端队列，deque既可以实现队列又可以实现栈。

本文基于JDK8，java version “1.8.0_251”

ArrayList

基于数组，支持随机访问，非线程安全

实现了RandomAccess接口，支持随机访问，查询元素更快，增加元素（非末尾添加）和删除元素比较慢，因为需要移动后面的元素位置。

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

/**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

底层是数组，默认容量10，最大容量Integer.MAX_VALUE-8（2^31 - 8）

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access
/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;	    
/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

懒加载，使用空参构造方法初始完后，数组容量为0而不是默认容量，添加元素后会扩容至默认容量

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

支持fail-fast机制，继承了AbstactList抽象类，继承自AbstactList的类每次调用新增或者删除等修改方法，属性modCount都会自增，当通过Interactor遍历集合时，只要modCount被其他线程修改，就会抛出ConcurrentModificationException

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];
}
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

非线程安全，可以通过Collections.synchronizedList()方法把它转成线程安全的集合，不过这样性能不是很高

扩容机制：扩容为原来的1.5倍

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
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);
}

相比LinkedList空间占用更小

LinkedList

基于双向链表，增加和删除元素快，非线程安全

实现了Deque接口，表明它是双向链表结构的，没有实现RandomAccess接口，所以不支持随机访问。增加和删除快，查询和修改元素慢。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
/**
 * Returns the (non-null) Node at the specified element 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;
    }
}
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;
    }
}

可以用来实现栈这个数据结构，或者直接把它当成栈来使用，但推荐使用ArrayDeque
支持fail-fast机制，继承了AbstractSequentialList抽象类，而它又继承了AbstactList抽象类，所以每次调用新增或者删除等修改方法，属性modCount都会自增，当通过Interactor遍历集合时，只要modCount被其他线程修改，就会抛出ConcurrentModificationException
非线程安全，可以通过Collections.synchronizedList()方法把它转成线程安全的集合，不过这样性能不是很高
由于每个元素包含next和prov指针，所以相比ArrayList空间占用更大

Vector

和ArrayList非常相似，主要不同：Vector是线程安全，ArrayList非线程安全。

实现了RandomAccess接口，支持随机访问，查询元素更快，增加元素（非末尾添加）和删除元素比较慢，因为需要移动后面的元素位置。
1
2
3
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
底层是数组，默认容量10，最大容量也是Integer.MAX_VALUE-8（没有显式定义这点，但是jvm规定数组的最大长度为Integer.MAX_VALUE-8）

无懒加载，使用空参构造初始化对象后，数组长度为10。

/**
 * Constructs an empty vector so that its internal data array
 * has size {@code 10} and its standard capacity increment is
 * zero.
 */
public Vector() {
    this(10);
}

支持fail-fast机制，继承了AbstactList抽象类，继承自AbstactList的类每次调用新增或者删除等修改方法，属性modCount都会自增，当通过Interactor遍历集合时，只要modCount被其他线程修改，就会抛出ConcurrentModificationException
1
2
3
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
线程安全，方法使用了synchronized修饰保证线程安全，但是效率较低，不推荐使用。

扩容机制：扩容为原来的2倍

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Stack

先进后出，线程安全，效率较低

线程安全，继承至Vector，相当于使用Vector的方法实现的栈，但效率较低，建议使用ConcurrentLinkedDeque代替

CopyOnWriteArrayList

基于数组，随机访问，线程安全，写时复制，读写分离，内存占用大，弱一致性，适合多读场景

实现了RandomAccess接口，支持随机访问，查询元素更快，增加元素（非末尾添加）和删除元素比较慢，因为需要移动后面的元素位置。
1
2
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
底层是数组，默认容量0，最大容量Integer.MAX_VALUE-8（没有显式定义这点，但是jvm规定数组的最大长度为Integer.MAX_VALUE-8）

无懒加载，默认容量就是0

/**
 * Creates an empty list.
 */
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

不支持fail-fast机制，没有继承于AbstractList，仅实现了List接口，Iterator实现类中，没有checkForComodification()，更不会抛出ConcurrentModificationException异常！
1
2
3
4
5
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}

线程安全。通过volatile和互斥锁来实现。增加、删除、修改操作使用ReenTrantLock实现同时只有一个线程能够获取锁。增加、删除、修改操作都是先复制一个新数组，然后对新操作进行操作，操作完之后再将新数组设置为容器，这种策略叫做写时复制，缺点就是内存占用大。但是在写入新数组后，将新数组设置为容器之前，执行查询操作，查询的是旧值，这就是写时复制策略产生的弱一致性问题。

/**
 * {@inheritDoc}
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    return get(getArray(), index);
}

/**
 * Replaces the element at the specified position in this list with the
 * specified element.
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        E oldValue = get(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

无扩容机制，由于每次增加元素都是重新创建新的数组，并且新数组容量为旧数组容量+1

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
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();
    }
}

问题

为什么java.util.concurrent包里没有并发的ArrayList实现

回答：很难去开发一个通用并且没有并发瓶颈的线程安全的List，像ConcurrentHashMap这样的类的真正价值并不是它们保证了线程安全。而在于它们在保证线程安全的同时不存在并发瓶颈。

问题在于，像“Array List”这样的数据结构，你不知道如何去规避并发的瓶颈。拿contains() 这样一个操作来说，当你进行搜索的时候如何避免锁住整个list？

另一方面，Queue 和Deque (基于Linked List)有并发的实现是因为他们的接口相比List的接口有更多的限制，这些限制使得实现并发成为可能。

CopyOnWriteArrayList是一个有趣的例子，它规避了只读操作（如get/contains）并发的瓶颈，但是它为了做到这点，在修改操作中做了很多工作和修改可见性规则。此外，修改操作还会锁住整个List，因此这也是一个并发瓶颈。所以从理论上来说，CopyOnWriteArrayList并不算是一个通用的并发List。