[Java]集合框架，

来源： javaer 分享于 2025-06-20 点击 9263 次点评：162

[Java]集合框架，

集合框架（Map部分未完成，过长要拆分，1.Collection；2.List；3.Queue 4.Set; 5.Map 6.Collections；7.数组和Arrays类 8.再看同步集合；9.集合框架中相关设计模式）

集合框架所有接口、抽象类和实体类

1.Collection 接口

public interface Collection<E> extends Iterable<E>

Collection 层次结构中的概念上的根接口。实际上继承自Iterable<T> 集合框架中所有的List Queue和Set都是可以获得迭代器的。

Collection 表示一组对象，这些对象也称为 collection 的元素。

一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。

包括通用的操作

增

    boolean add(E e);
    boolean addAll(Collection<? extends E> c);

删

    boolean remove(Object o);
    boolean removeAll(Collection<?> c);

    boolean retainAll(Collection<?> c);// 取交集

    void clear();

查

    boolean contains(Object o);
    boolean containsAll(Collection<?> c);

    int size();

    boolean isEmpty();

遍历

    Iterator<E> iterator();

比较

    boolean equals(Object o);

    int hashCode();

生成数组

    Object[] toArray();
    <T> T[] toArray(T[] a);

1.1 List

public interface List<E> extends Collection<E>

有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

与 set 不同，列表通常允许重复的元素。更确切地讲，列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2，并且如果列表本身允许 null 元素的话，通常它们允许多个 null 元素。

List 接口提供了特殊的迭代器，称为 ListIterator，除了允许 Iterator 接口提供的正常操作外，该迭代器还允许元素插入和替换，以及双向访问。还提供了一个方法来获取从列表中指定位置开始的列表迭代器。

列表提供了索引访问元素的的方式，列表（像 Java 数组一样）是基于 0 的。注意，这些操作可能在和某些实现（例如 LinkedList 类）的索引值成比例的时间内执行。

因此，如果调用者不知道实现，那么在列表元素上迭代通常优于用索引遍历列表。

List增加了相关index的操作

void add(int index,E element)
在列表的指定位置插入指定元素（可选操作）。

`E`	`get(int index)` 返回列表中指定位置的元素。

int indexOf(Object o)
返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1。

int lastIndexOf(Object o)
返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1。

`ListIterator<E>`	`listIterator()` 返回此列表元素的列表迭代器（按适当顺序）。
`ListIterator<E>`	`listIterator(int index)` 返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始。

`E`	`remove(int index)` 移除列表中指定位置的元素（可选操作）。

`E`	`set(int index,E element)` 用指定元素替换列表中指定位置的元素（可选操作）。

List<E> subList(int fromIndex, int toIndex)
返回列表中指定的 fromIndex（包括）和 toIndex（不包括）之间的部分视图。

1.1.1 ArrayList

底层数组存储

    private transient Object[] elementData;

AndroidSDK和JDK大同小异，AndroidSDK中默认是0个元素，jdk默认10个元素的数组。

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this(10);
    }

当容量不够时候会，jdk通过Arrays.copyOf()生成新的数组，AndroidSDK用这个System.arraycopy(a, 0, newArray, 0, s);

Arrays.copyOf()最终也是会调System.arraycopy

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //原长度的1.5倍
        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);
    }

JDK中，扩容后的长度是原来的1.5倍， newCapacity = oldCapacity + (oldCapacity >> 1);

下面是Android SDK中看到的ArrayList代码

      if (s == a.length) {
            Object[] newArray = new Object[s +
                    (s < (MIN_CAPACITY_INCREMENT / 2) ?  MIN_CAPACITY_INCREMENT : s >> 1)]; // size小于6则等于12，大于6则乘以2
            System.arraycopy(a, 0, newArray, 0, s);
            array = a = newArray;
        }

ensureCapacity会copy底层的数组，生成一个新的数组长度为arraylist的size()

LinkedList中没有这个方法，Vector中有。

1.1.2 LinkedList

public class LinkedList<E> extends AbstractSequentialList<E> implements
        List<E>, Deque<E>, Queue<E>, Cloneable, Serializable {

双向不循环链表

    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

Iterator<E> descendingIterator()
返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。

从接口 Deque

返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。元素将按从最后一个（尾部）到第一个（头部）的顺序返回。

Deque是1.6引入的，是作者Doug Lea和Josh Bloch

不是快速失败的not fail-fast

ListIterator<E> listIterator(int index)
返回此列表中的元素的列表迭代器（按适当顺序），从列表中指定位置开始

void push(E e) <=> void addFirst(E object) <~> boolean offerFirst(E e) 仅返回值不同

void addLast(E object) <~> boolean add(E object) <=> boolean offerLast(E e) <=>boolean offer(E o) 仅返回值不同

get(i) getFirst() getLast() 获得但不删元素 NoSuchElementException

E element() <=> getFirst()

peek() <=> peekFirst() peekLast() 获得但不删元素不抛异常返回null

pop() <=> remove <=>removeFirst removeLast 返回并且删除当没有元素时候抛出异常 NoSuchElementException （pop没有popFirst popLast）

poll() <=> pollFirst() pollLast() 返回并且删除不抛异常返回null

public E remove(int location) IndexOutOfBoundsException

public void add(int location, E object) IndexOutOfBoundsException

public boolean remove(Object object) <=> public boolean removeFirstOccurrence(Object o) 删除集合中第一次出现的o对象
public boolean removeLastOccurrence(Object o) 删除集合中最后一次出现的o对象

总结一下 LinkedList 的push element peek pop poll remove 默认操作都是对first的， add和offer添加操作是对last的，

push是为了和Stack的push概念上一致都是入栈操作，但LinkedList

1.1.3 Vector

    protected Object[] elementData;

    private static final int DEFAULT_SIZE = 10;

Enumeration和Iterator功能重复，新的实现应该优先考虑使用 Iterator 接口而不是 Enumeration 接口。

值得注意的是Vector中操作数据的方法都是同步的方法

Vector是JDK1.0时候的产物，引入集合框架后为了向后兼容保留了接口，但继承关系改变了，增加了新的方法，内部实现也都不一样了。

下面方法是原来的为向下兼容保留的老的方法

void addElement(E obj)
将指定的组件添加到此向量的末尾，将其大小增加 1。

int capacity()
返回此向量的当前容量。数组的长度

void copyInto(Object[] anArray)
将此向量的组件复制到指定的数组中。

`E`	`elementAt(int index)` 返回指定索引处的组件。
`Enumeration<E>`	`elements()` 返回此向量的组件的枚举。

void ensureCapacity(int minCapacity)
增加此向量的容量（如有必要），以确保其至少能够保存最小容量参数指定的组件数。

`E`	`firstElement()` 返回此向量的第一个组件（位于索引 `0`) 处的项）。

void insertElementAt(E obj, int index)
将指定对象作为此向量中的组件插入到指定的 index 处。

`E`	`lastElement()` 返回此向量的最后一个组件。

void removeAllElements()
从此向量中移除全部组件，并将其大小设置为零。

boolean removeElement(Object obj)
从此向量中移除变量的第一个（索引最小的）匹配项。

`void`	`removeElementAt(int index)` 删除指定索引处的组件。
`protected void`	`removeRange(int fromIndex, int toIndex)` 从此 List 中移除其索引位于 fromIndex（包括）与 toIndex（不包括）之间的所有元素。

void setElementAt(E obj, int index)
将此向量指定 index 处的组件设置为指定的对象。

void trimToSize()
对此向量的容量进行微调，使其等于向量的当前大小。

1.1.4 Stack

public class Stack<E> extends Vector<E>

public E push(E item) 非同步放入参数直接返回里面是同步的 addElement()

public synchronized E pop()

    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    public synchronized int search(Object o)    --> lastIndexOf
    public synchronized E peek()       --> return elementAt(len - 1);
    public boolean empty()

Stack和Vector都是JDK1.0时候的产物，都是同步的，引入集合框架后为了向后兼容保留了接口，但继承关系改变了，增加了新的方法，内部实现也都不一样了。

java.lang.Object
  java.util.Dictionary<K,V>
      java.util.Hashtable<Object,Object>
          java.util.Properties

这几个集合也是古老的，后面都会介绍到。

1.1.5 RandomAccess

的实现类Vector，ArrayList使用index访问比迭代器访问要快速。

RandomAccess接口是List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。

在对List特别的遍历算法中，要尽量来判断是属于RandomAccess(如ArrayList)还是SequenceAccess(如LinkedList），因为适合RandomAccess List的遍历算法，用在SequenceAccess List上就差别很大，即对于实现了RandomAccess接口的类实例而言，此循环

     for (int i=0, i<list.size(); i++)
list.get(i);

的运行速度要快于以下循环：

     for (Iterator i=list.iterator(); i.hasNext(); )
        i.next();

1.1.6 CopyOnWriteArrayList

ArrayList 的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。

允许使用所有元素，包括 null。

这一般需要很大的开销，但是当遍历操作的数量大大超过可变操作的数量时，这种方法可能比其他替代方法更有效。

在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时，它也很有用。

“快照”风格的迭代器方法在创建迭代器时使用了对数组的引用，

此数组在迭代器的生存期内不会更改，因此不可能发生冲突，并且迭代器保证不会抛出 ConcurrentModificationException。

其迭代器对数据是只读的。创建迭代器以后，迭代器就不会反映列表的添加、移除或者更改。

在迭代器上进行的元素更改操作（remove、set 和 add）不受支持。这些方法将抛出UnsupportedOperationException。

内存一致性效果：当存在其他并发 collection 时，将对象放入 CopyOnWriteArrayList 之前的线程中的操作happen-before 随后通过另一线程从CopyOnWriteArrayList 中访问或移除该元素的操作。

`int`	`addAllAbsent(Collection<? extends E> c)` 按照指定 collection 的迭代器返回元素的顺序，将指定 collection 中尚未包含在此列表中的所有元素添加列表的尾部。
`boolean`	`addIfAbsent(E e)` 添加元素（如果不存在）。

1.1.7迭代器

Iterator

public interface Iterator<E> 
   
    boolean hasNext();
    
    E next();

    void remove();

ListIterator

public interface ListIterator<E> extends Iterator<E> 

    boolean hasNext();

    E next();

    void remove();

    boolean hasPrevious();

    E previous();

    int nextIndex();

    int previousIndex();

    void set(E e);

    void add(E e);

1.1.8 快速失败

这种机制提供迭代过程中集合的安全性

ArrayList是快速失败的

LinkedList 不是快速失败的好像也只有LinkedList不是快速失败的

ArrayDeque 不允许null 快速失败

LinkedList 允许null 不是快速失败 Queue一般不允许null

HashSet 允许使用 null 元素 快速失败

LinkedHashSet 允许 null 元素。 快速失败

Hashtable key不允许null 快速失败

1.2 Queue

1.2.1 Queue接口

1.2.2 PriorityQueue

1.2.3 ConcurrentLinkedQueue

1.2.4 BlockingQueue

1.2.5 PriorityBlockingQueue

1.2.6 SynchronousQueue

1.2.7 LinkedBlockingQueue

1.2.8 ArrayBlockingQueue

1.2.9 DelayQueue Delayed

1.2.10 Deque

1.2.11 ArrayDeque

1.2.12 BlockingDeque

1.2.13 LinkedBlockingDeque

1.2.1 Queue接口

在处理元素前用于保存元素的 Collection。除了基本的 Collection操作外，队列还提供其他的插入、提取和检查操作。

一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。

插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的；在大多数实现中，插入操作不会失败。

	抛出异常	返回特殊值
插入	`add(e)`	`offer(e)`
移除	`remove()`	`poll()`
检查	`element()`	`peek()`

队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头都是调用remove() 或poll() 所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个Queue 实现必须指定其顺序属性。

如果可能，offer 方法可插入一个元素，否则返回false。这与Collection.add 方法不同，该方法只能通过抛出未经检查的异常使添加元素失败。offer 方法设计用于正常的失败情况，而不是出现异常的情况，例如在容量固定（有界）的队列中。

remove() 和poll() 方法可移除和返回队列的头。到底从队列中移除哪个元素是队列排序策略的功能，而该策略在各种实现中是不同的。remove() 和poll() 方法仅在队列为空时其行为有所不同：remove() 方法抛出一个异常，而poll() 方法则返回null。

element() 和peek() 返回，但不移除，队列的头。

Queue 接口并未定义阻塞队列的方法，而这在并发编程中是很常见的。BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法，这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入null。即使在允许 null 的实现中，也不应该将null 插入到Queue 中，因为null 也用作poll 方法的一个特殊返回值，表明队列不包含元素。

Queue 实现通常未定义 equals 和 hashCode 方法的基于元素的版本，而是从 Object 类继承了基于身份的版本，因为对于具有相同元素但有不同排序属性的队列而言，基于元素的相等性并非总是定义良好的。

1.2.2 PriorityQueue

  public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
        if (initialCapacity < 1) {
            throw new IllegalArgumentException();
        }
        elements = newElementArray(initialCapacity);
        this.comparator = comparator;
    }
    @SuppressWarnings("unchecked")
    private E[] newElementArray(int capacity) {
        return (E[]) new Object[capacity];
    }

一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的Comparator 进行排序，具体取决于所使用的构造方法。

优先级队列不允许使用 null 元素。有排序的集合一般不能存null

依靠自然顺序的优先级队列还不允许插入不可比较的对象（这样做可能导致ClassCastException）。

    private int compare(E o1, E o2) {
        if (comparator != null) {
            return comparator.compare(o1, o2);
        }
        return ((Comparable<? super E>) o1).compareTo(o2);
    }

底层是数组

注意，此实现不是同步的。如果多个线程中的任意线程修改了队列，则这些线程不应同时访问 PriorityQueue 实例。相反，请使用线程安全的PriorityBlockingQueue 类。

1.2.2.1 Comparator和Comparable

public interface Comparator<T> {
    public int compare(T lhs, T rhs);
    public boolean equals(Object object);
}

public interface Comparable<T> {
    int compareTo(T another);
}

Comparator位于包java.util下，而Comparable位于包 java.lang下

Comparable 是一个对象本身就已经支持自比较所需要实现的接口（

可以说一个是自已完成比较，一个是外部程序实现比较的差别而已。

用 Comparator 是策略模式（strategy design pattern），就是不改变对象自身，而用一个策略对象（strategy object）来改变它的行为。

Comparable与Comparator的区别

1.2.2.2策略模式

见设计模式相关文章

1.2.3 ConcurrentLinkedQueue

一个基于链接节点的无界线程安全队列。

此队列按照 FIFO（先进先出）原则对元素进行排序。队列的头部是队列中时间最长的元素。队列的尾部是队列中时间最短的元素。新的元素插入到队列的尾部，队列获取操作从队列头部获得元素。

当多个线程共享访问一个公共 collection 时，ConcurrentLinkedQueue 是一个恰当的选择。

此队列不允许使用 null 元素。

需要小心的是，与大多数 collection 不同，size 方法不是一个固定时间操作。由于这些队列的异步特性，确定当前元素的数量需要遍历这些元素。

ConcurrentLinkedQueue的size() 是要遍历一遍集合的，所以尽量要避免用size而改用isEmpty().

此实现采用了有效的“无等待 (wait-free)”算法，该算法基于 Maged M. Michael 和 Michael L. Scott 合著的 Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms 中描述的算法。

使用了这个ConcurrentLinkedQueue 类之后是否意味着我们不需要自己进行任何同步或加锁操作了呢？

也就是说，如果直接使用它提供的函数，比如：queue.add(obj); 或者 queue.poll(obj);，这样我们自己不需要做任何同步。

但如果是非原子操作，比如：

if(!queue.isEmpty()) {

queue.poll(obj);

}

我们很难保证，在调用了isEmpty()之后，poll()之前，这个queue没有被其他线程修改。

所以对于这种情况，我们还是需要自己同步：

synchronized(queue) {

if(!queue.isEmpty()) {

queue.poll(obj);

}

1.2.3.1无等待？？

演进条件分为四个主要类别，阻塞（blocking），无干扰（obstruction-free），无锁（lock-free），和无等待（wait-free）‘

什么是演进条件？？

1.2.4 BlockingQueue

BlockingQueue就是这样的队列：

如果BlockingQueue是空的，从BlockingQueue取东西的操作将会被阻断进入等待状态，直到BlockingQueue进了东西才会被唤醒，同样，如果BlockingQueue是满的，任何试图往里存东西的操作也会被阻断进入等待状态，直到BlockingQueue里有空间时才会被唤醒继续操作。

支持两个附加操作的 Queue，这两个操作是：获取元素时等待队列变为非空，以及存储元素时等待空间变得可用。

public interface BlockingQueue<E> extends Queue<E>

	抛出异常	特殊值	阻塞	超时
插入	`add(e)`	`offer(e)`	`put(e)`	`offer(e, time, unit)`
移除	`remove()`	`poll()`	`take()`	`poll(time, unit)`
检查	`element()`	`peek()`	不可用	不可用

BlockingQueue 不接受 null 元素。试图add、put 或offer 一个null 元素时，某些实现会抛出NullPointerException。null 被用作指示poll 操作失败的警戒值。

BlockingQueue 可以是限定容量的。它在任意给定时间都可以有一个 remainingCapacity，超出此容量，便无法无阻塞地put 附加元素。没有任何内部容量约束的BlockingQueue 总是报告Integer.MAX_VALUE 的剩余容量。

BlockingQueue 实现主要用于生产者-使用者队列，但它另外还支持 Collection 接口。因此，举例来说，使用remove(x) 从队列中移除任意一个元素是有可能的。然而，这种操作通常不会有效执行，只能有计划地偶尔使用，比如在取消排队信息时。

BlockingQueue 实现是线程安全的。所有排队方法都可以使用内部锁或其他形式的并发控制来自动达到它们的目的。然而，大量的 Collection 操作（addAll、containsAll、retainAll 和removeAll）没有必要自动执行，除非在实现中特别说明。因此，举例来说，在只添加了c 中的一些元素后，addAll(c) 有可能失败（抛出一个异常）。

BlockingQueue 实质上不支持使用任何一种“close”或“shutdown”操作来指示不再添加任何项。这种功能的需求和使用有依赖于实现的倾向。例如，一种常用的策略是：对于生产者，插入特殊的end-of-stream 或poison 对象，并根据使用者获取这些对象的时间来对它们进行解释。

int remainingCapacity()
返回在无阻塞的理想情况下（不存在内存或资源约束）此队列能接受的附加元素数量；如果没有内部限制，则返回 Integer.MAX_VALUE。

`int`	`drainTo(Collection<? super E> c)` 移除此队列中所有可用的元素，并将它们添加到给定 collection 中。
`int`	`drainTo(Collection<? super E> c, int maxElements)` 最多从此队列中移除给定数量的可用元素，并将这些元素添加到给定 collection 中。

1.2.5 PriorityBlockingQueue

一个无界阻塞队列，它使用与类 PriorityQueue 相同的顺序规则，并且提供了阻塞获取操作。

虽然此队列逻辑上是无界的，但是资源被耗尽时试图执行 add 操作也将失败（导致 OutOfMemoryError）。

此类不允许使用 null 元素。

依赖自然顺序的优先级队列也不允许插入不可比较的对象（这样做会导致抛出 ClassCastException）。

底层是数组

此类及其迭代器可以实现 Collection 和 Iterator 接口的所有可选方法。

iterator() 方法中提供的迭代器并不保证以特定的顺序遍历 PriorityBlockingQueue 的元素。

如果需要有序地进行遍历，则应考虑使用 Arrays.sort(pq.toArray())。此外，可以使用方法 drainTo 按优先级顺序移除全部或部分元素，并将它们放在另一个 collection 中。

？？？

在此类上进行的操作不保证具有同等优先级的元素的顺序。如果需要实施某一排序，那么可以定义自定义类或者比较器，比较器可使用修改键断开主优先级值之间的联系。例如，以下是应用先进先出 (first-in-first-out) 规则断开可比较元素之间联系的一个类。要使用该类，则需要插入一个新的FIFOEntry(anEntry) 来替换普通的条目对象。

 class FIFOEntry<E extends Comparable<? super E>>
     implements Comparable<FIFOEntry<E>> {
   final static AtomicLong seq = new AtomicLong();
   final long seqNum;
   final E entry;
   public FIFOEntry(E entry) {
     seqNum = seq.getAndIncrement();
     this.entry = entry;
   }
   public E getEntry() { return entry; }
   public int compareTo(FIFOEntry<E> other) {
     int res = entry.compareTo(other.entry);
     if (res == 0 && other.entry != this.entry)
       res = (seqNum < other.seqNum ? -1 : 1);
     return res;
   }
 }

1.2.6 SynchronousQueue

一种阻塞队列，其中每个插入操作必须等待另一个线程的对应移除操作，反之亦然。

同步队列没有任何内部容量，甚至连一个队列的容量都没有。

不能在同步队列上进行 peek，因为仅在试图要移除元素时，该元素才存在；

除非另一个线程试图移除某个元素，否则也不能（使用任何方法）插入元素；

也不能迭代队列，因为其中没有元素可用于迭代。

队列的头是尝试添加到队列中的首个已排队插入线程的元素；

如果没有这样的已排队线程，则没有可用于移除的元素并且 poll() 将会返回 null。

对于其他 Collection 方法（例如 contains），SynchronousQueue 作为一个空 collection。

此队列不允许 null 元素。

同步队列类似于 CSP 和 Ada 中使用的 rendezvous 信道。它非常适合于传递性设计，在这种设计中，在一个线程中运行的对象要将某些信息、事件或任务传递给在另一个线程中运行的对象，它就必须与该对象同步。

对于正在等待的生产者和使用者线程而言，此类支持可选的公平排序策略。默认情况下不保证这种排序。但是，使用公平设置为 true 所构造的队列可保证线程以 FIFO 的顺序进行访问

这是一个很有意思的阻塞队列，其中每个插入操作必须等待另一个线程的移除操作，同样任何一个移除操作都等待另一个线程的插入操作。因此此队列内部其实没有任何一个元素，或者说容量是0，严格说并不是一种容器。由于队列没有容量，因此不能调用peek操作，因为只有移除元素时才有元素。

一个没有容量的并发队列有什么用了？或者说存在的意义是什么？

SynchronousQueue 的实现非常复杂，当然了如果真要去分析还是能够得到一些经验的，但是前面分析了过多的结构后，发现越来越陷于数据结构与算法里面了。我的初衷是通过研究并发实现的原理来更好的利用并发来最大限度的利用可用资源。所以在后面的章节中尽可能的少研究数据结构和算法，但是为了弄清楚里面的原理，必不可免的会涉及到一些这方面的知识，希望后面能够适可而止。

再回到话题。SynchronousQueue 内部没有容量，但是由于一个插入操作总是对应一个移除操作，反过来同样需要满足。那么一个元素就不会再SynchronousQueue 里面长时间停留，一旦有了插入线程和移除线程，元素很快就从插入线程移交给移除线程。也就是说这更像是一种信道（管道），资源从一个方向快速传递到另一方向。

需要特别说明的是，尽管元素在SynchronousQueue 内部不会“停留”，但是并不意味之SynchronousQueue 内部没有队列。实际上SynchronousQueue 维护着线程队列，也就是插入线程或者移除线程在不同时存在的时候就会有线程队列。既然有队列，同样就有公平性和非公平性特性，公平性保证正在等待的插入线程或者移除线程以FIFO的顺序传递资源。

显然这是一种快速传递元素的方式，也就是说在这种情况下元素总是以最快的方式从插入着（生产者）传递给移除着（消费者），这在多任务队列中是最快处理任务的方式。在线程池的相关章节中还会更多的提到此特性。

1.2.7 LinkedBlockingQueue

一个基于已链接节点的、范围任意的阻塞队列。

此队列按 FIFO（先进先出）排序元素。队列的头部是在队列中时间最长的元素。队列的尾部是在队列中时间最短的元素。新元素插入到队列的尾部，并且队列获取操作会获得位于队列头部的元素。

链接队列的吞吐量通常要高于基于数组的队列，但是在大多数并发应用程序中，其可预知的性能要低。

可选的容量范围构造方法参数作为防止队列过度扩展的一种方法。如果未指定容量，则它等于 Integer.MAX_VALUE。除非插入节点会使队列超出容量，否则每次插入后会动态地创建链接节点。

此队列不允许 null 元素。

1.2.8 ArrayBlockingQueue

一个由数组支持的有界阻塞队列。

此队列按 FIFO（先进先出）原则对元素进行排序。队列的头部是在队列中存在时间最长的元素。队列的尾部是在队列中存在时间最短的元素。新元素插入到队列的尾部，队列获取操作则是从队列头部开始获得元素。

此队列不允许 null 元素。

这是一个典型的“有界缓存区”，固定大小的数组在其中保持生产者插入的元素和使用者提取的元素。

一旦创建了这样的缓存区，就不能再增加其容量。试图向已满队列中放入元素会导致操作受阻塞；试图从空队列中提取元素将导致类似阻塞。

此类支持对等待的生产者线程和使用者线程进行排序的可选公平策略。默认情况下，不保证是这种排序。然而，通过将公平性 (fairness) 设置为true 而构造的队列允许按照 FIFO 顺序访问线程。公平性通常会降低吞吐量，但也减少了可变性和避免了“不平衡性”。

公平性

想到了锁是有公平性如new ReentrantLock(true) new ReentrantReadWriteLock(true)

吞吐量

LinkedBlockingQueue和ArrayBlockingQueue比较起来，它们背后所用的数据结构不一样，导致LinkedBlockingQueue的数据吞吐量要大于ArrayBlockingQueue，但在线程数量很大时其性能的可预见性低于ArrayBlockingQueue。

1.2.9 DelayQueue Delayed

Delayed 元素的一个无界阻塞队列，只有在延迟期满时才能从中提取元素。

该队列的头部是延迟期满后保存时间最长的 Delayed 元素。

如果延迟都还没有期满，则队列没有头部，并且 poll 将返回 null。

当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于等于 0 的值时，将发生到期。

即使无法使用 take 或 poll 移除未到期的元素，也不会将这些元素作为正常元素对待。例如，size 方法同时返回到期和未到期元素的计数。

此队列不允许使用 null 元素。

底层是一个PriorityQueue对象

private final PriorityQueue<E> q = new PriorityQueue<E>();

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {

DelayQueue = BlockingQueue + PriorityQueue + Delayed

DelayQueue是一个使用优先队列（PriorityQueue）实现的BlockingQueue，优先队列的比较是依据时间。

缓存对象的清除，任务超时处理等都可以使用QelayQueue

当调用DelayQueue的offer方法时，把Delayed对象加入到优先队列q中

public boolean offer(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        E first = q.peek();
        q.offer(e);
        if (first == null || e.compareTo(first) < 0)
            available.signalAll();
        return true;
    } finally {
        lock.unlock();
    }
}

DelayQueue的take方法，先peek优先队列q的first ，获得first的delay，如果没有达到延时阀值，则进行await处理，如果delay<=0了就 return q.poll();

  public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            for (;;) {
                E first = q.peek();
                if (first == null)
                    available.await();
                else {
                    long delay = first.getDelay(NANOSECONDS);
                    if (delay <= 0)
                        return q.poll();
                    else if (leader != null)
                        available.await();
                    else {
                        Thread thisThread = Thread.currentThread();
                        leader = thisThread;
                        try {
                            available.awaitNanos(delay);
                        } finally {
                            if (leader == thisThread)
                                leader = null;
                        }
                    }
                }
            }
        } finally {
            if (leader == null && q.peek() != null)
                available.signal();
            lock.unlock();
        }
    }

1.2.10 Deque

public interface Deque<E> extends Queue<E>

一个线性 collection，支持在两端插入和移除元素。

名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。

大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的Deque 实现设计的；在大多数实现中，插入操作不能失败。

下表总结了上述 12 种方法：

	第一个元素（头部）		最后一个元素（尾部）
	抛出异常	特殊值	抛出异常	特殊值
插入	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
移除	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
检查	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

此接口扩展了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从Queue 接口继承的方法完全等效于Deque 方法，如下表所示：

`Queue` 方法	等效 `Deque` 方法
`add(e)`	`addLast(e)`
`offer(e)`	`offerLast(e)`
`remove()`	`removeFirst()`
`poll()`	`pollFirst()`
`element()`	`getFirst()`
`peek()`	`peekFirst()`

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于Deque 方法，如下表所示：

堆栈方法	等效 `Deque` 方法
`push(e)`	`addFirst(e)`
`pop()`	`removeFirst()`
`peek()`	`peekFirst()`

注意，在将双端队列用作队列或堆栈时，peek 方法同样正常工作；无论哪种情况下，都从双端队列的开头抽取元素。

此接口提供了两种移除内部元素的方法：removeFirstOccurrence 和 removeLastOccurrence。

与 List 接口不同，此接口不支持通过索引访问元素。

虽然 Deque 实现没有严格要求禁止插入 null 元素，但建议最好这样做。建议任何事实上允许 null 元素的 Deque 实现用户最好不要利用插入 null 的功能。这是因为各种方法会将 null 用作特殊的返回值来指示双端队列为空。

Deque 实现通常不定义基于元素的 equals 和 hashCode 方法，而是从Object 类继承基于身份的equals 和hashCode 方法。

1.2.11 ArrayDeque

Deque 接口的大小可变数组的实现。

数组双端队列没有容量限制；它们可根据需要增加以支持使用。

它们不是线程安全的；

在没有外部同步时，它们不支持多个线程的并发访问。

禁止 null 元素。

此类很可能在用作堆栈时快于 Stack，在用作队列时快于 LinkedList。

大多数 ArrayDeque 操作以摊销的固定时间运行。异常包括 remove、removeFirstOccurrence、removeLastOccurrence、contains、iterator.remove() 以及批量操作，它们均以线性时间运行。

快速失败

此类的 iterator 方法返回的迭代器是快速失败 的：如果在创建迭代器后的任意时间通过除迭代器本身的remove 方法之外的任何其他方式修改了双端队列，则迭代器通常将抛出ConcurrentModificationException。因此，面对并发修改，迭代器很快就会完全失败，而不是冒着在将来不确定的时刻任意发生不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在不同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出ConcurrentModificationException。因此，编写依赖于此异常的程序是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测 bug。

正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

快速失败：对于非并发集合来说，在其进行迭代时，例如iterator迭代时，iterator是另起一个线程，若有其他线程（如Collection）进行结构修改（修改了增减了集合中的内容），这个迭代会马上感知到，并且立即抛出 ConcurrentModificationException 异常，而不是迭代完成后才告诉你出错了，引起快速失败。若用iterator进行修改则不会出现这个问题，如iterator.move();也就是说涉及到了多个线程间的同步问题

为了实现快速失败需要保存修改次数迭代器中进行比较

       final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

1.2.12 BlockingDeque

1.2.13 LinkedBlockingDeque

for-each循环需要实现

Iterable

/**
 * Instances of classes that implement this interface can be used with
 * the enhanced for loop.
 *
 * @since 1.5
 */
public interface Iterable<T> {

    /**
     * Returns an {@link Iterator} for the elements in this object.
     *
     * @return An {@code Iterator} instance.
     */
    Iterator<T> iterator();
}

http://standalone.iteye.com/blog/1876771

http://wsmajunfeng.iteye.com/blog/1629352/

http://www.cnblogs.com/jobs/archive/2007/04/27/730255.html

.........................]

1.3 Set

一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和e2，并且最多包含一个 null 元素。

正如其名称所暗示的，此接口模仿了数学上的 set 抽象。

在所有构造方法以及 add、equals 和 hashCode 方法的协定上，Set 接口还加入了其他规定，这些规定超出了从Collection 接口所继承的内容。出于方便考虑，它还包括了其他继承方法的声明（这些声明的规范已经专门针对Set 接口进行了修改，但是没有包含任何其他的规定）。

注：如果将可变对象用作 set 元素，那么必须极其小心。如果对象是 set 中某个元素，以一种影响equals 比较的方式改变对象的值，那么 set 的行为就是不确定的。此项禁止的一个特殊情况是不允许某个 set 包含其自身作为元素。

某些 set 实现对其所包含的元素有所限制。例如，某些实现禁止 null 元素，而某些则对其元素的类型所有限制。试图添加不合格的元素会抛出未经检查的异常，通常是NullPointerException 或ClassCastException。试图查询不合格的元素是否存在可能会抛出异常，也可能简单地返回 false；某些实现会采用前一种行为，而某些则采用后者。概括地说，试图对不合格元素执行操作时，如果完成该操作后不会导致在 set 中插入不合格的元素，则该操作可能抛出一个异常，也可能成功，这取决于实现的选择。此接口的规范中将这样的异常标记为“可选”。

1.3.1 SortedSet

public interface SortedSet<E> extends Set<E> {

进一步提供关于元素的总体排序 的 Set。

这些元素使用其自然顺序进行排序，或者根据通常在创建有序 set 时提供的 Comparator 进行排序。

该 set 的迭代器将按元素升序遍历 set。

提供了一些附加的操作来利用这种排序。（此接口是 SortedMap 的 set 对应接口）。

插入有序 set 的所有元素都必须实现 Comparable 接口（或者被指定的比较器所接受）。另外，所有这些元素都必须是可互相比较的：对于有序 set 中的任意两个元素e1 和e2，执行e1.compareTo(e2)（或comparator.compare(e1, e2)）都不得抛出ClassCastException。试图违反此限制将导致违反规则的方法或者构造方法调用抛出ClassCastException。

注意，如果有序 set 要正确实现 Set 接口，则有序 set 所维持的顺序（无论是否提供了明确的比较器）都必须与 equals 一致。（有关与 equals 一致 的精确定义，请参阅Comparable 接口或Comparator 接口。）这是因为Set 接口是按照equals 操作定义的，但有序 set 使用它的compareTo（或compare）方法对所有元素进行比较，因此从有序 set 的角度来看，此方法认为相等的两个元素就是相等的。即使顺序与 equals 不一致，有序 set 的行为仍然是定义良好的，只不过没有遵守Set 接口的常规协定。

所有通用有序 set 实现类都应该提供 4 个“标准”构造方法：

1) void（无参数）构造方法，它创建一个空的有序 set，按照元素的自然顺序进行排序。

2) 带有一个 Comparator 类型参数的构造方法，它创建一个空的有序 set，根据指定的比较器进行排序。

3) 带有一个 Collection 类型参数的构造方法，它创建一个新的有序 set，其元素与参数相同，按照元素的自然顺序进行排序。

4) 带有一个 SortedSet 类型参数的构造方法，它创建一个新的有序 set，其元素和排序方法与输入的有序 set 相同。无法保证强制实施此建议，因为接口不能包含构造方法。

注：一些方法返回具有受限范围的子集。这些范围区间是半开的，也就是说，它们包括低端点，但不包括高端点（如果适用）。如果需要一个闭区间（同时包含两个端点），且元素类型允许计算给定值的后继值，则只需要请求从lowEndpoint 到successor(highEndpoint) 的子区间。例如，假设s 是一个字符串有序 set。下面的语句将得到一个包含s 中从low 到high（包括）所有字符串的视图：

   SortedSet<String> sub = s.subSet(low, high+"\0");

可使用类似的技术生成开区间（两个端点都不包括）。下面的语句得到包含 s 中从 low 到 high（不包括）所有字符串的视图：

   SortedSet<String> sub = s.subSet(low+"\0", high);

1.3.2 NavigableSet 接口

public interface NavigableSet<E> extends SortedSet<E> {

扩展的 SortedSet，具有了为给定搜索目标报告最接近匹配项的导航方法。

方法 lower、floor、ceiling 和higher 分别返回小于、小于等于、大于等于、大于给定元素的元素，如果不存在这样的元素，则返回null。

可以按升序或降序访问和遍历 NavigableSet。

descendingSet 方法返回 set 的一个视图，该视图表示的所有关系方法和方向方法都是逆向的。

升序操作和视图的性能很可能比降序操作和视图的性能要好。

此外，此接口还定义了 pollFirst 和 pollLast 方法，它们返回并移除最小和最大的元素（如果存在），否则返回null。

subSet、headSet 和 tailSet 方法与名称相似的 SortedSet 方法的不同之处在于：可以接受用于描述是否包括（或不包括）下边界和上边界的附加参数。

任何 NavigableSet 的 Subset 必须实现 NavigableSet 接口。

导航方法的返回值在允许 null 元素的实现中可能是不确定的。不过，即使在这种情况下，也可以通过检查 contains(null) 来明确结果。为了避免这样的问题，建议在此接口的实现中不允许插入 null 元素。（注意，Comparable 元素的有序集本身不允许null。）

subSet(E, E)、headSet(E) 和 tailSet(E) 方法被指定为返回SortedSet，以允许现有SortedSet 实现能相容地改进为实现NavigableMap，但鼓励此接口的扩展和实现重写这些方法以返回NavigableSet。

descendingIterator

1.3.3 TreeSet

基于 TreeMap 的 NavigableSet 实现。

继承自NavigableSet<E>，底层通过 private transient NavigableMap<E,Object> m;

使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。

此实现为基本操作（add、remove 和contains）提供受保证的 log(n) 时间开销。

注意，如果要正确实现 Set 接口，则 set 维护的顺序（无论是否提供了显式比较器）必须与 equals 一致。（关于与 equals 一致 的精确定义，请参阅Comparable 或Comparator。）这是因为Set 接口是按照equals 操作定义的，但TreeSet 实例使用它的compareTo（或compare）方法对所有元素进行比较，因此从 set 的观点来看，此方法认为相等的两个元素就是相等的。即使 set 的顺序与 equals 不一致，其行为也是定义良好的；它只是违背了Set 接口的常规协定。

注意，此实现不是同步的。如果多个线程同时访问一个 TreeSet，而其中至少一个线程修改了该 set，那么它必须外部同步。这一般是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用Collections.synchronizedSortedSet 方法来“包装”该 set。此操作最好在创建时进行，以防止对 set 的意外非同步访问：

   SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

此类的 iterator 方法返回的迭代器是快速失败 的：在创建迭代器之后，如果从结构上对 set 进行修改，除非通过迭代器自身的remove 方法，否则在其他任何时间以任何方式进行修改都将导致迭代器抛出ConcurrentModificationException。因此，对于并发的修改，迭代器很快就完全失败，而不会冒着在将来不确定的时间发生不确定行为的风险。

注意，迭代器的快速失败行为无法得到保证，一般来说，存在不同步的并发修改时，不可能作出任何肯定的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测 bug。

1.3.3.1 Tree相关数据结构和算法

1.3.4 HashSet

此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。

底层是个HashMap对象

它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null 元素。

此类为基本操作提供了稳定性能，这些基本操作包括 add、remove、contains 和 size，假定哈希函数将这些元素正确地分布在桶中。

对此 set 进行迭代所需的时间与 HashSet 实例的大小（元素的数量）和底层 HashMap 实例（桶的数量）的“容量”的和成比例。

因此，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

为什么初始容量设置得太高，或将加载因子设置得太低会影响性能?

注意，此实现不是同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：

   Set s = Collections.synchronizedSet(new HashSet(...));

此类的 iterator 方法返回的迭代器是快速失败 的：在创建迭代器之后，如果对 set 进行修改，除非通过迭代器自身的remove 方法，否则在任何时间以任何方式对其进行修改，Iterator 都将抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来在某个不确定时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器在尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法：迭代器的快速失败行为应该仅用于检测 bug。

1.3.4.1 Hash算法原理

1.3.5 LinkedHashSet

具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。

此实现与 HashSet 的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，即按照将元素插入到 set 中的顺序（插入顺序）进行迭代。注意，插入顺序不受在 set 中重新插入的 元素的影响。（如果在s.contains(e) 返回true 后立即调用s.add(e)，则元素e 会被重新插入到 sets 中。）

此实现可以让客户免遭未指定的、由 HashSet 提供的通常杂乱无章的排序工作，而又不致引起与 TreeSet 关联的成本增加。使用它可以生成一个与原来顺序相同的 set 副本，并且与原 set 的实现无关：

     void foo(Set s) {
         Set copy = new LinkedHashSet(s);
         ...
     }

如果模块通过输入得到一个 set，复制这个 set，然后返回由此副本决定了顺序的结果，这种情况下这项技术特别有用。（客户通常期望内容返回的顺序与它们出现的顺序相同。）

此类提供所有可选的 Set 操作，并且允许 null 元素。

与 HashSet 一样，它可以为基本操作（add、contains 和 remove）提供稳定的性能，假定哈希函数将元素正确地分布到存储段中。

由于增加了维护链接列表的开支，其性能很可能会比 HashSet 稍逊一筹，不过，这一点例外：LinkedHashSet 迭代所需时间与 set 的大小成正比，而与容量无关。

HashSet 迭代很可能支出较大，因为它所需迭代时间与其容量成正比。

链接的哈希 set 有两个影响其性能的参数：初始容量 和加载因子。它们与 HashSet 中的定义极其相同。注意，为初始容量选择非常高的值对此类的影响比对HashSet 要小，因为此类的迭代时间不受容量的影响。（HashSet底层是HashMap、而LinkedHashSet 底层是LinkedHashMap）

这里分析源码的时候，很容易发现LinkedHashSet 继承自HashSet<E>，没有增加新的方法只有4个构造方法，那既然HashSet使用HashMap的，为什么说LinkedHashSet 底层是LinkedHashMap呢？因为HashSet有个包访问权限的构造方法，不是public的，LinkedHashSet的构造都是使用的这个super构造方法

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

注意，此实现不是同步的。如果多个线程同时访问链接的哈希 set，而其中至少一个线程修改了该 set，则它必须保持外部同步。这一般通过对自然封装该 set 的对象进行同步操作来完成。如果不存在这样的对象，则应该使用Collections.synchronizedSet 方法来“包装”该 set。最好在创建时完成这一操作，以防止意外的非同步访问：

     Set s = Collections.synchronizedSet(new LinkedHashSet(...));

此类的 iterator 方法返回的迭代器是快速失败 的：在迭代器创建之后，如果对 set 进行修改，除非通过迭代器自身的remove 方法，其他任何时间任何方式的修改，迭代器都将抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来不确定的时间任意发生不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在不同步的并发修改时，不可能作出任何强有力的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的方式是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

1.3.6 ConcurrentSkipListSet

一个基于 ConcurrentSkipListMap 的可缩放并发NavigableSet 实现。

set 的元素可以根据它们的自然顺序进行排序，也可以根据创建 set 时所提供的 Comparator 进行排序，具体取决于使用的构造方法。

此实现为 contains、add、remove 操作及其变体提供预期平均 log(n) 时间开销。多个线程可以安全地并发执行插入、移除和访问操作。迭代器是弱一致 的，返回的元素将反映迭代器创建时或创建后某一时刻的 set 状态。它们不抛出ConcurrentModificationException，可以并发处理其他操作。升序排序视图及其迭代器比降序排序视图及其迭代器更快。

请注意，与在大多数 collection 中不同，这里的size 方法不是一个固定时间 (constant-time) 操作。

ConcurrentLinkedQueue也是size不是固定时间的

由于这些 set 的异步特性，确定元素的当前数目需要遍历元素。此外，批量操作 addAll、removeAll、retainAll 和containsAll并不保证能以原子方式 (atomically) 执行。例如，与addAll 操作一起并发操作的迭代器只能查看某些附加元素。

此类及其迭代器实现 Set 和 Iterator 接口的所有可选方法。与大多数其他并发 collection 实现一样，此类不允许使用null 元素，因为无法可靠地将null 参数及返回值与不存在的元素区分开来。

1.3.7 CopyOnWriteArraySet

对其所有操作使用内部 CopyOnWriteArrayList 的 Set。因此，它共享以下相同的基本属性：

它最适合于具有以下特征的应用程序：set 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
它是线程安全的。
因为通常需要复制整个基础数组，所以可变操作（add、set 和 remove 等等）的开销很大。
迭代器不支持可变 remove 操作。
使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。

示例用法。 以下代码使用一个写时复制（copy-on-write）的 set，以维护在状态更新时执行某项操作的一组 Handler 对象。

 class Handler { void handle(); ... }

 class X {
    private final CopyOnWriteArraySet<Handler> handlers = new CopyOnWriteArraySet<Handler>();
    public void addHandler(Handler h) { handlers.add(h); }

    private long internalState;
    private synchronized void changeState() { internalState = ...; }

    public void update() {
       changeState();
       for (Handler handler : handlers)
           handler.handle();
    }
 }

1.3.8 EnumSet

与枚举类型一起使用的专用 Set 实现。

枚举 set 中所有键都必须来自单个枚举类型，该枚举类型在创建 set 时显式或隐式地指定。

枚举 set 在内部表示为位向量。此表示形式非常紧凑且高效。此类的空间和时间性能应该很好，足以用作传统上基于 int 的“位标志”的替换形式，具有高品质、类型安全的优势。如果其参数也是一个枚举 set，则批量操作（如containsAll 和retainAll）也应运行得非常快。

由 iterator 方法返回的迭代器按其自然顺序 遍历这些元素（该顺序是声明枚举常量的顺序）。返回的迭代器是弱一致的：它从不抛出ConcurrentModificationException，也不一定显示在迭代进行时发生的任何 set 修改的效果。

不允许使用 null 元素。试图插入 null 元素将抛出 NullPointerException。但是，试图测试是否出现 null 元素或移除 null 元素将不会抛出异常。

像大多数 collection 实现一样，EnumSet 是不同步的。如果多个线程同时访问一个枚举 set，并且至少有一个线程修改该 set，则此枚举 set 在外部应该是同步的。这通常是通过对自然封装该枚举 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用Collections.synchronizedSet(java.util.Set) 方法来“包装”该 set。最好在创建时完成这一操作，以防止意外的非同步访问：

 Set<MyEnum> s = Collections.synchronizedSet(EnumSet.noneOf(MyEnum.class));

实现注意事项：所有基本操作都在固定时间内执行。虽然并不保证，但它们很可能比其 HashSet 副本更快。如果其参数也是一个枚举 set ，则批量操作会在固定时间内执行。

1.3.9 RegularEnumSet

1.3.10 JumboEnumSet

1.3.11 Enum

1.4 Map

为了成功地在哈希表中存储和获取对象，用作键的对象必须实现 hashCode 方法和 equals 方法。

Map.Entry<K,V>

将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。

此接口取代 Dictionary 类，后者完全是一个抽象类，而不是一个接口。

Map 接口提供三种collection 视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。映射顺序定义为迭代器在映射的 collection 视图上返回其元素的顺序。某些映射实现可明确保证其顺序，如TreeMap 类；另一些映射实现则不保证顺序，如HashMap 类。

注：将可变对象用作映射键时必须格外小心。当对象是映射中某个键时，如果以影响equals 比较的方式更改了对象的值，则映射的行为将是不确定的。此项禁止的一种特殊情况是不允许某个映射将自身作为一个键包含。虽然允许某个映射将自身作为值包含，但请格外小心：在这样的映射上equals 和hashCode 方法的定义将不再是明确的。

所有通用的映射实现类应该提供两个“标准的”构造方法：一个 void（无参数）构造方法，用于创建空映射；一个是带有单个 Map 类型参数的构造方法，用于创建一个与其参数具有相同键-值映射关系的新映射。实际上，后一个构造方法允许用户复制任意映射，生成所需类的一个等价映射。尽管无法强制执行此建议（因为接口不能包含构造方法），但是 JDK 中所有通用的映射实现都遵从它。

此接口中包含的“破坏”方法可修改其操作的映射，如果此映射不支持该操作，这些方法将抛出 UnsupportedOperationException。如果是这样，那么在调用对映射无效时，这些方法可以（但不要求）抛出UnsupportedOperationException。例如，如果某个不可修改的映射（其映射关系是“重叠”的）为空，则对该映射调用putAll(Map) 方法时，可以（但不要求）抛出异常。

某些映射实现对可能包含的键和值有所限制。例如，某些实现禁止 null 键和值，另一些则对其键的类型有限制。尝试插入不合格的键或值将抛出一个未经检查的异常，通常是NullPointerException 或ClassCastException。试图查询是否存在不合格的键或值可能抛出异常，或者返回 false；某些实现将表现出前一种行为，而另一些则表现后一种。一般来说，试图对不合格的键或值执行操作且该操作的完成不会导致不合格的元素被插入映射中时，将可能抛出一个异常，也可能操作成功，这取决于实现本身。这样的异常在此接口的规范中标记为“可选”。

Collections Framework 接口中的很多方法是根据 equals 方法定义的。例如，containsKey(Object key) 方法的规范中写道：“当且仅当此映射包含针对满足(key==null ? k==null : key.equals(k)) 的键k 的映射关系时，返回true”。不应将此规范解释为：调用具有非空参数key 的Map.containsKey 将导致对任意的键k 调用 key.equals(k)。实现可随意进行优化，以避免调用equals，例如，可首先比较两个键的哈希码（Object.hashCode() 规范保证哈希码不相等的两个对象不会相等）。一般来说，只要实现者认为合适，各种 Collections Framework 接口的实现可随意利用底层Object 方法的指定行为。

1.4.1 SortedMap

1.4.2 NavigableMap

1.4.3 TreeMap

1.4.4 HashMap

1.4.5 LinkedHashMap

1.4.6 WeakHashMap

1.4.7 IdentityHashMap

1.4.8 ConcurrentMap

1.4.9 ConcurrentNavigableMap

1.4.10 ConcurrentHashMap

1.4.11 ConcurrentSkipListMap

可缩放的并发 ConcurrentNavigableMap 实现。映射可以根据键的自然顺序进行排序，也可以根据创建映射时所提供的 Comparator 进行排序，具体取决于使用的构造方法。

此类实现 SkipLists 的并发变体，为 containsKey、get、put、remove 操作及其变体提供预期平均log(n) 时间开销。多个线程可以安全地并发执行插入、移除、更新和访问操作。迭代器是弱一致 的，返回的元素将反映迭代器创建时或创建后某一时刻的映射状态。它们不抛出ConcurrentModificationException，可以并发处理其他操作。升序键排序视图及其迭代器比降序键排序视图及其迭代器更快。

此类及此类视图中的方法返回的所有 Map.Entry 对，表示他们产生时的映射关系快照。它们不支持 Entry.setValue 方法。（注意，根据所需效果，可以使用put、putIfAbsent 或replace 更改关联映射中的映射关系。）

请注意，与在大多数 collection 中不同，这里的 size 方法不是一个固定时间 (constant-time) 操作。因为这些映射的异步特性，确定元素的当前数目需要遍历元素。此外，批量操作putAll、equals 和clear并不保证能以原子方式 (atomically) 执行。例如，与putAll 操作一起并发操作的迭代器只能查看某些附加元素。

此类及其视图和迭代器实现 Map 和 Iterator 接口的所有可选方法。与大多数其他并发 collection 一样，此类不允许使用null 键或值，因为无法可靠地区分 null 返回值与不存在的元素值。

ConcurrentSkipListMap，ConcurrentSkipListSet，ConcurrentLinkedQueue这三个集合的size不是固定时间的

1.4.12 Dictionary

Dictionary 类是任何可将键映射到相应值的类（如 Hashtable）的抽象父类。每个键和每个值都是一个对象。在任何一个Dictionary 对象中，每个键至多与一个值相关联。给定一个Dictionary 和一个键，就可以查找所关联的元素。任何非null 对象都可以用作键或值。

通常，应该在此类的实现中使用 equals 方法，以决定两个键是否相同。

注：此类已过时。新的实现应该实现 Map 接口，而不是扩展此类。

抽象类
键值不能null

1.4.13 Hashtable

此类实现一个哈希表，该哈希表将键映射到相应的值。任何非 null 对象都可以用作键或值。

Hashtable 的实例有两个参数影响其性能：初始容量 和加载因子。

容量是哈希表中桶的数量，初始容量 就是哈希表创建时的容量。

注意，哈希表的状态为 open：在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。加载因子 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。

通常，默认加载因子(.75)在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间（在大多数 Hashtable 操作中，包括get 和 put 操作，都反映了这一点）。

初始容量主要控制空间消耗与执行 rehash 操作所需要的时间损耗之间的平衡。如果初始容量大于 Hashtable 所包含的最大条目数除以加载因子，则永远不会发生rehash 操作。但是，将初始容量设置太高可能会浪费空间。

如果很多条目要存储在一个 Hashtable 中，那么与根据需要执行自动 rehashing 操作来增大表的容量的做法相比，使用足够大的初始容量创建哈希表或许可以更有效地插入条目。

下面这个示例创建了一个数字的哈希表。它将数字的名称用作键：

   Hashtable<String, Integer> numbers
     = new Hashtable<String, Integer>();
   numbers.put("one", 1);
   numbers.put("two", 2);
   numbers.put("three", 3);

要获取一个数字，可以使用以下代码：

   Integer n = numbers.get("two");
     if (n != null) {
         System.out.println("two = " + n);
     }
   }

由所有类的“collection 视图方法”返回的 collection 的 iterator 方法返回的迭代器都是快速失败 的：在创建 Iterator 之后，如果从结构上对 Hashtable 进行修改，除非通过 Iterator 自身的remove 方法，否则在任何时间以任何方式对其进行修改，Iterator 都将抛出ConcurrentModificationException。因此，面对并发的修改，Iterator 很快就会完全失败，而不冒在将来某个不确定的时间发生任意不确定行为的风险。由 Hashtable 的键和元素方法返回的 Enumeration不是快速失败的。

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法：迭代器的快速失败行为应该仅用于检测程序错误。

从Java 2 平台 v1.2起，此类就被改进以实现 Map 接口，使它成为 Java Collections Framework 中的一个成员。不像新的 collection 实现，Hashtable 是同步的