Java 的集合

Java 集合的基础接口分为两个，分别是 Collection 和 Map。其中对于 Collection 又分为三类接口：List、Set、Queue。下图能够比较好的说明它们之间的关系（仅列出了比较常用的类）

下边分别对其进行介绍

Collection

Collection 又分为三个基础接口：List、Set、Queue

List

List 下有几个常用的数据结构：

ArrayList，线性列表（动态数组）
LinkedList，链表
Vector（同步数组） => Stack，栈
CopyOnWriteArrayList，线程安全的列表

ArrayList

ArrayList 是一个线性列表，也可以称为动态数组，它是线程不安全的。元素的增加与移除都是建立在一个数组上的，如下为几个常规操作：

add: 默认创建 10 长度的数组，并动态扩充其 size
remove: 使用 Native 方法 System.arraycopy() 拷贝数组，并将数组最后一位设置为 Null
get: 获取数组对应位置的值

当出现以下情况时，抛出 ConcurrentModifiedException

List<String> list = new ArrayList<>(100);
list.add("1");
list.add("2");
list.add("3");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    iterator.next();
    list.remove("1");
}

上述代码可以改写为：

List<String> list = new ArrayList<>(100);
list.add("1");
list.add("2");
list.add("3");

for (String aList : list) {
    list.remove("1");
}

for…in 其实就是 Iterator，只是一个语法糖。注意，此时会抛出异常

为什么会抛出异常？

我们可以看下 ArrayList 类的 Itr 内部类，其实现了 Iterator 接口。在其中，next 和 remove 方法都会检查 modcount 值是否一致。

为什么 Iterator 会检查 modcount 的值？

因为 iterator 的遍历是基于游标（cursor）的，当数组的值发生了变化（增加、删除），就会出现并发安全的问题。

LinkedList

LinkedList 是一个双向链表，其数据结构是基于 Node（节点）的。其元素的增加、移除均基于链表。

如下是 Node 的数据结构：

// 包含上一个元素和下一个元素
private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
}

Vector(Stack)

Stack 是一个栈，其数据结构基于动态扩容的数组，与 ArrayList 基本相同。其是线程安全的，基于 Synchronized，性能较差。

peek()，返回栈顶的值，线程安全
pop()，出栈操作，线程安全
push()，入栈操作，线程安全

CopyOnWriteArrayList

CopyOnWriteArrayList 可以认为是一个线程安全的 ArrayList，同是基于数组的。在其代码中引入了 ReentrantLock 的机制，并在迭代的时候使用快照(snapshot)的方式来遍历。

其有几个基本方法：

add，使用 ReentrantLock 加锁，底层调用 System.arraycopy() 建立新数组并填充最后一位元素
set，使用 ReentrantLock 加锁，底层调用 System.arraycopy() 建立新数组，并修改相应索引对应的元素
remove，加锁，创建新数组，并调用 System.arraycopy() 来移除某一个元素

从上述可以看出来，CopyOnWriteArrayList 是线程安全的

接下来我们看下使用迭代器来遍历 CopyOnWriteArrayList

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("1");
list.add("2");
list.add("3");

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
    String value = iterator.next();
    if (value.equals("1")) {
        list.remove(0);
    }
}
System.out.println(list.size());

CopyOnWriteArrayList 的迭代是用创建快照（副本）的方式来进行迭代，即迭代的是数据的一份副本。我们看一下 CopyOnWriteArrayList.COWIterator 的代码：

static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

     public boolean hasNext() {
         return cursor < snapshot.length;
     }

     public E next() {
         if (! hasNext())
             throw new NoSuchElementException();
         return (E) snapshot[cursor++];
     }

可以看出来，hasNext 和 next 均是基于快照(snapshot) 的。所以在迭代的时候，我们可以对源列表做修改而不用担心并发修改的问题。

Set

Set 里边的元素是不能相同的。

CopyOnWriteArraySet

底层的数据结构是 CopyOnWriteArrayList，即基于 CopyOnWriteArrayList 做了扩展。

add、remove 等操作均是基于 CopyOnWriteArrayList

HashSet

基于 HashMap ，其 add 方法代码如下：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

对于 HasSet 的元素值作为 key 来 Put 进 HashMap 中，以此来确保唯一性。

penglongli / blog

Java 集合 #117