8.1　介绍集合API

Java 集合是一系列泛型接口，描述最常见的数据类型格式。Java 为每一种典型的数据结构都提供了多种实现方式，而且这些类型都通过接口实现，因此开发团队可以自行开发专用的实现方式，在自己的项目中使用。

Java 集合定义了两种基本的数据结构，一种是 Collection，表示一组对象的集合；另一种是 Map，表示对象间的一系列映射或关联关系。Java 集合的基本架构如图 8-1 所示。

图 8-1：集合类及其继承关系

在这种架构中，Set 是一种 Collection，不过其中没有重复的对象；List 也是一种 Collection，其中的元素按顺序排列（不过可能有重复）。

SortedSet 和 SortedMap 是特殊的集和映射，其中的元素按顺序排列。

Collection、Set、List、Map、SortedSet 和 SortedMap 都是接口，不过 java.util 包定义了多个具体实现，例如基于数组和链表的列表，基于哈希表或二叉树的映射和集。除此之外，还有两个重要的接口，Iterator 和 Iterable，用于遍历集合中的对象，稍后会介绍。

8.1.1　Collection接口

Collection 是参数化接口，表示由泛型 E 对象组成的集合。这个接口定义了很多方法，用来把对象添加到集合中，把对象从集合中移除，测试对象是否在集合中，以及遍历集合中的所有元素。还有一些方法可以把集合中的元素转换成数组，以及返回集合的大小。

　Collection 集合可以允许其中的元素有重复，也可以禁止有重复；可以强制使用特定的顺序，也可以不强制有顺序。

Java 集合框架之所以提供 Collection 接口，是因为常见的数据结构都会用到这些特性。JDK 提供的 Set、List 和 Queue 都是 Collection 的子接口。下述代码展示了可以在 Collection 对象上执行的操作：

// 创建几个集合，供后面的代码使用
Collection<String> c = new HashSet<>(); // 一个空集
// 稍后会介绍这些实用方法
// 注意，使用时要留意一些细节
Collection<String> d = Arrays.asList("one", "two");
Collection<String> e = Collections.singleton("three");
// 向集合中添加一些元素
// 如果集合的内容变化了，这些方法返回true
// 这种表现对不允许重复的Set类型很有用
c.add("zero");           // 添加单个元素
c.addAll(d);             // 添加d中的所有元素
// 复制集合：多数实现都有副本构造方法
Collection<String> copy = new ArrayList<String>(c);
// 把元素从集合中移除。
// 除了clear()方法之外，如果集合的内容变化了，都返回true
c.remove("zero");        // 移除单个元素
c.removeAll(e);          // 移除一组元素
c.retainAll(d);          // 移除不在集合d中的所有元素
c.clear();               // 移除所有元素
// 获取集合的大小
boolean b = c.isEmpty(); // c是空的，所以返回true
int s = c.size();        // 现在c的大小是0
// 使用前面创建的副本复原集合
c.addAll(copy);
// 测试元素是否在集合中。测试基于equals()方法，而不是==运算符
b = c.contains("zero");  // true
b = c.containsAll(d);    // true
// 多数Collection实现都有toString()方法
System.out.println(c);
// 使用集合中的元素创建一个数组。
// 如果迭代器能保证特定的顺序，数组就有相同的顺序
// 得到的数组是个副本，而不是内部数据结构的引用
Object[] elements = c.toArray();
// 如果想把集合中的元素存入String[]类型的数组，必须在参数中指定这个类型
String[] strings = c.toArray(new String[c.size()]);
// 或者传入一个类型为String[]的空数组，指定所需的类型
// toArray()方法会为这个数组分配空间
strings = c.toArray(new String[0]);

记住，上述各个方法都能用于 Set、List 或 Queue。这几个子接口可能会对集合中的元素做些限制或有顺序上的约束，但都提供了相同的基本方法。

　修改集合的方法，例如 add()、remove()、clear() 和 retainAll()，是可选的 API。不过，这个规则在很久以前就定下了，那时认为如果不提供这些方法，明智的做法是抛出 UnsupportedOperationException 异常。因此，某些实现（尤其是只读方法）可能会抛出未检异常。

Collection 和 Map 及其子接口都没扩展 Cloneable 或 Serializable 接口。不过，在 Java 集合框架中，实现集合和映射的所有类都实现了这两个接口。

有些集合对其可以包含的元素做了限制。例如，有的集合禁止使用 null 作为元素。EnumSet 要求其中的元素只能是特定的枚举类型。

如果尝试把禁止使用的元素添加到集合中，会抛出未检异常，例如 NullPointerException 或 ClassCastException。检查集合中是否包含禁止使用的元素，可能也会抛出这种异常，或者仅仅返回 false。

8.1.2　Set接口

集（set）是无重复对象组成的集合：不能有两个引用指向同一个对象，或两个指向 null 的引用，如果对象 a 和 b 的引用满足条件 a.equals(b)，那么这两个对象也不能同时出现在集中。多数通用的 Set 实现都不会对元素排序，但并不禁止使用有序集（SortedSet 和 LinkedHashSet 就有顺序）。而且集与列表等有序集合不同，一般认为，集的 contains 方法，不论以常数时间还是以对数时间评判 1，运行效率都高。

1常数时间和对数时间是定量描述算法运行时间的两种方式。——译者注

除了 Collection 接口定义的方法之外，Set 没有再定义其他方法，但对这些方法做了额外的限制。Set 接口要求 add() 和 addAll() 方法必须遵守无重复原则：如果集中已经有某个元素，就不能再次添加。前面说过，Collection 接口定义的 add() 和 addAll() 方法，在改变集合时返回 true，否则返回 false。对 Set 对象而言，也会返回 true 或 false，因为不能重复意味着添加元素不一定会修改集。

表 8-1 列出了实现 Set 接口的类，而且总结了各个类的内部表示方式、排序特性、对成员的限制，以及 add()、remove()、contains 等基本操作和迭代的性能。这些类的详细信息，请参见各自的文档。注意，CopyOnWriteArraySet 类在 java.util.concurrent 包中，其他类则在 java.util 包中。还要注意，java.util.BitSet 类没有实现 Set 接口，这个类过时了，用于紧凑而高效地表示布尔值组成的列表，但不是 Java 集合框架的一部分。

表8-1：实现Set接口的类

TreeSet 类使用红黑树数据结构维护集，这个集中的元素按照 Comparable 对象的自然顺序升序迭代，或者按照 Comparator 对象指定的顺序迭代。其实，TreeSet 实现的是 Set 的子接口，SortedSet 接口。

SortedSet 接口提供了多个有趣的方法，这些方法都考虑到了元素是有顺序的，如下述代码所示：

public static void testSortedSet(String[] args) {
    // 创建一个SortedSet对象
    SortedSet<String> s = new TreeSet<>(Arrays.asList(args));
    // 迭代集：元素已经自动排序
    for (String word : s) {
        System.out.println(word);
    }
    // 特定的元素
    String first = s.first(); // 第一个元素
    String last = s.last();   // 最后一个元素
    // 除第一个元素之外的其他所有元素
    SortedSet<String> tail = s.tailSet(first + '\0');
    System.out.println(tail);
    // 除最后一个元素之外的其他所有元素
    SortedSet<String> head = s.headSet(last);
    System.out.println(head);
    SortedSet<String> middle = s.subSet(first+'\0', last);
    System.out.println(middle);
}

　必须加上 \0 字符，因为 tailSet() 等方法要使用某个元素后面的元素，对字符串来说，要在后面加上 NULL 字符（对应于 ASCII 中的 0）。

8.1.3　List接口

List 是一组有序的对象集合。列表中的每个元素都有特定的位置，而且 List 接口定义了一些方法，用于查询或设定特定位置（或叫索引）的元素。从这个角度来看，List 对象和数组类似，不过列表的大小能按需变化，以适应其中元素的数量。和集不同，列表允许出现重复的元素。

除了基于索引的 get() 和 set() 方法之外，List 接口还定义了一些方法，用于把元素添加到特定的索引，把元素从特定的索引移除，或者返回指定值在列表中首次出现或最后出现的索引。从 Collection 接口继承的 add() 和 remove() 方法，前者把元素添加到列表末尾，后者把指定值从列表中首次出现的位置移除。继承的 addAll() 方法把指定集合中的所有元素添加到列表的末尾，或者插入指定的索引。retainAll() 和 removeAll() 方法的表现与其他 Collection 对象一样，如果需要，会保留或删除多个相同的值。

List 接口没有定义操作索引范围的方法，但是定义了一个 subList() 方法。这个方法返回一个 List 对象，表示原列表指定范围内的元素。子列表会回馈父列表，只要修改了子列表，父列表立即就能察觉到变化。下述代码演示了 subList() 方法和其他操作 List 对象的基本方法：

// 创建两个列表，供后面的代码使用
List<String> l = new ArrayList<String>(Arrays.asList(args));
List<String> words = Arrays.asList("hello", "world");
// 通过索引查询和设定元素
String first = l.get(0);        // 列表的第一个元素
String last = l.get(l.size -1); // 列表的最后一个元素
l.set(0, last);                 // 把最后一个元素变成第一个元素
// 添加和插入元素
// add()方法既可以把元素添加到列表末尾，也可以把元素插入指定索引
l.add(first);       // 把第一个词添加到列表末尾
l.add(0, first);    // 再把第一个词添加到列表的开头
l.addAll(words);    // 把一个集合添加到列表末尾
l.addAll(1, words); // 在第一个词之后插入一个集合
// 子列表：回馈原列表
List<String> sub = l.subList(1,3); // 第二个和第三个元素
sub.set(0, "hi");                  // 修改l的第二个元素
// 子列表可以把操作限制在原列表索引的子范围内
String s = Collections.min(l.subList(0,4));
Collections.sort(l.subList(0,4));
// 子列表的独立副本不影响父列表
List<String> subcopy = new ArrayList<String>(l.subList(1,3));
// 搜索列表
int p = l.indexOf(last); // 最后一个词在哪个位置？
p = l.lastIndexOf(last); // 反向搜索
// 打印last在l中出现的所有索引。注意，使用了子列表
int n = l.size();
p = 0;
do {
    // 创建一个列表，只包含尚未搜索的元素
    List<String> list = l.subList(p, n);
    int q = list.indexOf(last);
    if (q == -1) break;
    System.out.printf("Found '%s' at index %d%n", last, p+q);
    p += q+1;
} while(p < n);
// 从列表中删除元素
l.remove(last);         // 把指定元素从首次出现的位置上删除
l.remove(0);            // 删除指定索引对应的元素
l.subList(0,2).clear(); // 使用subList()方法，删除一个范围内的元素
l.retainAll(words);     // 删除所有不在words中的元素
l.removeAll(words);     // 删除所有在words中的元素
l.clear();              // 删除所有元素

1. 遍历循环和迭代

操作集合有种重要的方式：依次处理每个元素，这种方式叫迭代。这种处理数据结构的方式很古老，但时至今日依旧很有用（尤其是用来处理少量数据的集合），而且易于理解。迭代最适合使用 for 循环，而且使用 List 对象演示最简单，如下所示：

ListCollection<String> c = new ArrayList<String>();
// ……把一些字符串添加到c中
for(String word : c) {
    System.out.println(word);
}

这段代码的作用很明显——一次读取 c 中的一个元素，然后把这个元素当成变量传入循环主体。说得更正式一些，这段代码的作用是迭代数组或集合（或者其他实现 java.lang.Iterable 接口的对象）中的元素。每次迭代都会把数组或 Iterable 对象中的一个元素赋值给你声明的循环变量，然后执行循环主体，一般都会处理表示元素的循环变量。迭代的过程中不需要使用循环计数器或 Iterator 对象，遍历循环会自动迭代，你无需担心初始化或终止循环的方式是否正确。

这种 for 循环一般称作遍历循环。我们来看一下它的运作方式。下述代码重写了前面的 for 循环（作用等效），显示了迭代过程中真正会使用的方法：

// 使用for循环迭代
for(Iterator<String> i = c.iterator(); i.hasNext();) {
    System.out.println(i.next());
}

Iterator 对象 i 从集合上获取，用于逐个读取集合中的元素。在 while 循环中也可以使用 Iterator 对象：

// 使用while循环迭代集合中的元素
// 有些集合种类（例如列表）能保障迭代的顺序，有些则不能
Iterator<String> iterator = c.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

关于遍历循环的句法，还有一些注意事项。

• 前面说过，expression 必须是数组或实现 java.lang.Iterable 接口的对象。编译时必须知道 expression 的类型，这样才能生成合适的循环代码。

• 数组或 Iterable 对象中元素的类型必须与 declaration 中声明的变量类型兼容，这样才能赋值。如果使用的 Iterable 对象没有使用元素的类型参数化，那么变量必须声明为 Object 类型。

• declaration 一般只包含变量的类型和名称，不过也可以包含 final 修饰符和任何适当的注解（参见第 4 章）。final 的作用是避免循环变量使用循环赋予它的数组或集合元素之外的值，以此强调不能通过循环变量修改数组或集合。

• 遍历循环的循环变量的声明必须是循环的一部分，变量的类型和名称都要指明。不能像 for 循环那样，使用循环之外声明的变量。

为了深入理解遍历循环处理集合的方式，我们要了解两个接口——java.util.Iterator 和 java.lang.Iterable：

public interface Iterator<E> {
     boolean hasNext();
     E next();
     void remove();
}

Iterator 接口定义了一种迭代集合或其他数据结构中元素的方式。迭代的过程是这样的：只要集合中还有更多的元素（hasNext() 方法返回 true），就调用 next() 方法获取集合中的下一个元素。有序集合（例如列表）的迭代器一般能保证按照顺序返回元素。无序集合（例如 Set）只能保证不断调用 next() 方法返回集中的所有元素，没有遗漏也没有重复，不过没有特定的顺序。

　Iterator 接口中的 next() 方法有两个作用：把集合的游标向前移动，然后返回集合的前一个头值。如果使用不可变的风格编程，这两个操作可能导致问题，因为 next() 其实会修改集合。

引入 Iterable 接口是为了支持遍历循环。类实现这个接口是为了表明它提供了 Iterator 对象，可以迭代：

public interface Iterable<E> {
     java.util.Iterator<E> iterator();
}

如果某个对象是 Iterable 类型，表明它有一个能返回 Iterator 对象的 iterator() 方法，而 Iterator 对象有一个 next() 方法，能返回一个 E 类型的对象。

　注意，如果使用遍历循环迭代 Iterable 对象，循环变量必须是 E 类型，或者是 E 类型的超类或实现的接口。

例如，迭代 List 对象中的元素时，循环变量必须声明为 String 类型或超类 Object 类型，或者 String 实现的某个接口：CharSequence、Comparable 或 Serializable。

2. 随机访问列表中的元素

我们一般期望实现 List 接口的类能高效迭代，而且所用时间和列表的大小成正比。然而，不是所有列表都能高效地随机访问任意索引上的元素。按顺序访问的列表，例如 LinkedList 类，提供了高效的插入和删除操作，但降低了随机访问性能。提供高效随机访问的类都实现了标记接口 RandomAccess，因此，如果需要确定是否能高效处理列表，可以使用 instanceof 运算符测试是否实现了这个接口：

// 随便创建一个列表，供后面的代码处理
List<?> l = ...;
// 测试能否高效随机访问
// 如果不能，先使用副本构造方法创建一个支持高效随机访问的副本，然后再处理
if (!(l instanceof RandomAccess)) l = new ArrayList<?>(l);

在 List 对象上调用 iterator() 方法会得到一个 Iterator 对象，这个对象按照元素在列表中的顺序迭代各元素。List 实现了 Iterable 接口，因此列表可以像其他集合一样使用遍历循环迭代。

如果只想迭代列表中的部分元素，可以使用 subList() 方法创建子列表：

List<String> words = ...; // 创建一个列表，供下面的代码迭代
// 迭代除第一个元素之外的所有元素
for(String word : words.subList(1, words.size ))
    System.out.println(word);

表 8-2 总结了 Java 平台中五种通用的 List 实现。Vector 和 Stack 类已经过时，别再用了。CopyOnWriteArrayList 类在 java.util.concurrent 包中，只适合在多线程环境中使用。

表8-2：实现List接口的类

8.1.4　Map接口

映射（map）是一系列键值对，一个键对应一个值。Map 接口定义了用于定义和查询映射的 API。Map 接口属于 Java 集合框架，但没有扩展 Collection 接口，因此 Map 只是一种集合，而不是 Collection 类型。Map 是参数化类型，有两个类型变量。类型变量 K 表示映射中键的类型，类型变量 V 表示键对应的值的类型。例如，如果有个映射，其键是 String 类型，对应的值是 Integer 类型，那么这个映射可以表示为 Map。

Map 接口定义了几个最有用的方法：put() 方法定义映射中的一个键值对，get() 方法查询指定键对应的值，remove() 方法把指定的键及对应的值从映射中删除。一般来说，实现 Map 接口的类都要能高效执行这三个基本方法：一般应该运行在常数时间中，而且绝不能比在对数时间中运行的性能差。

Map 的重要特性之一是，可以视作集合。虽然 Map 对象不是 Collection 类型，但映射的键可以看成 Set 对象，映射的值可以看成 Collection 对象，而映射的键值对可以看成由 Map.Entry 对象组成的 Set 对象。（Map.Entry 是 Map 接口中定义的嵌套接口，表示一个键值对。）

下述示例代码展示了如何使用 get()、put() 和 remove() 等方法操作 Map 对象，还演示了把 Map 对象视作集合后的一些常见用法：

// 新建一个空映射
Map<String,Integer> m = new HashMap();
// 不可变的映射，只包含一个键值对
Map<String,Integer> singleton = Collections.singletonMap("test", -1);
// 注意，极少使用下述句法显式指定通用方法emptyMap()的参数类型
// 得到的映射不可变
Map<String,Integer> empty = Collections.<String,Integer>emptyMap();
// 使用put()方法填充映射，把数组中的元素映射到元素的索引上
String[] words = { "this", "is", "a", "test" };
for(int i = 0; i < words.length; i++) {
    m.put(words[i], i); // 注意，int会自动装包成Integer
}
// 一个键只能映射一个值
// 不过，多个键可以映射同一个值
for(int i = 0; i < words.length; i++) {
    m.put(words[i].toUpperCase(), i);
}
// putAll()方法从其他映射中复制键值对
m.putAll(singleton);
// 使用get()方法查询映射
for(int i = 0; i < words.length; i++) {
    if (m.get(words[i]) != i) throw new AssertionError();
}
// 测试映射中是否有指定的键和值
m.containsKey(words[0]);       // true
m.containsValue(words.length); // false
// 映射的键、值和键值对都可以看成集合
Set<String> keys = m.keySet();
Collection<Integer> values = m.values();
Set<Map.Entry<String,Integer>> entries = m.entrySet();
// 映射和上述几个集合都有有用的toString()方法
System.out.printf("Map: %s%nKeys: %s%nValues: %s%nEntries: %s%n",
                  m, keys, values, entries);
// 可以迭代这些集合
// 多数映射都没定义迭代的顺序（不过SortedMap定义了）
for(String key : m.keySet()) System.out.println(key);
for(Integer value: m.values()) System.out.println(value);
// Map.Entry<K,V>类型表示映射中的一个键值对
for(Map.Entry<String,Integer> pair : m.entrySet()) {
    // 打印键值对
    System.out.printf("'%s' ==> %d%n", pair.getKey(), pair.getValue());
    // 然后把每个Entry对象的值增加1
    pair.setValue(pair.getValue() + 1);
}
// 删除键值对
m.put("testing", null);   // 映射到null上可以“擦除”一个键值对
m.get("testing");         // 返回null
m.containsKey("testing"); // 返回true：键值对仍然存在
m.remove("testing");      // 删除键值对
m.get("testing");         // 还是返回null
m.containsKey("testing"); // 这次返回false
// 也可以把映射视作集合，然后再删除
// 不过，向集合中添加键值对时不能这么做
m.keySet().remove(words[0]); // 等同于m.remove(words[0]);
// 删除一个值为2的键值对——这种方式一般效率不高，用途有限
m.values().remove(2);
// 删除所有值为4的键值对
m.values().removeAll(Collections.singleton(4));
// 只保留值为2和3的键值对
m.values().retainAll(Arrays.asList(2, 3));
// 还可以通过迭代器删除
Iterator<Map.Entry<String,Integer>> iter = m.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry<String,Integer> e = iter.next();
    if (e.getValue() == 2) iter.remove();
}
// 找出两个映射中都有的值
// 一般来说，addAll()和retainAll()配合keySet()和values()使用，可以获取交集和并集
Set<Integer> v = new HashSet<Integer>(m.values());
v.retainAll(singleton.values());
// 其他方法
m.clear();                // 删除所有键值对
m.size();                 // 返回键值对的数量：目前为0
m.isEmpty();              // 返回true
m.equals(empty);          // true：实现Map接口的类覆盖了equals()方法

Map 接口有一些通用和专用的实现，表 8-3 对此做了总结。和之前一样，完整的细节参见 JDK 文档和 javadoc。在表 8-3 中，除了 ConcurrentHashMap 和 ConcurrentSkipListMap 两个类在 java.util.concurrent 包中，其他类都在 java.util 包中。

表8-3：实现Map接口的类

java.util.concurrent 包中的 ConcurrentHashMap 和 ConcurrentSkipListMap 两个类实现了同一个包中的 ConcurrentMap 接口。ConcurrentMap 接口扩展 Map 接口，而且定义了一些对多线程编程很重要的原子操作方法。例如，putIfAbsent() 方法，它的作用和 put() 方法类似，不过，仅当指定的键没有映射到其他值上时，才会把键值对添加到映射中。

TreeMap 类实现 SortedMap 接口。这个接口扩展 Map 接口，添加了一些方法，利用这种映射的有序特性。SortedMap 接口和 SortedSet 接口非常相似。firstKey() 和 lastKey() 方法分别返回 keySet() 所得集的第一个和最后一个键。而 headMap()、tailMap() 和 subMap() 方法都返回一个新映射，由原映射特定范围内的键值对组成。

8.1.5　Queue接口和BlockingQueue接口

队列（queue）是一组有序的元素，提取元素时按顺序从队头读取。队列一般按照插入元素的顺序实现，因此分成两类：先进先出（first-in, first-out，FIFO）队列和后进先出（last-in, first-out，LIFO）队列。

　LIFO 队列也叫栈（stack），Java 提供了 Stack 类，但强烈不建议使用——应该使用实现 Deque 接口的类。

队列也可以使用其他顺序：优先队列（priority queue）根据外部 Comparator 对象或 Comparable 类型元素的自然顺序排序元素。与 Set 不同的是，Queue 的实现往往允许出现重复的元素。而与 List 不同的是，Queue 接口没有定义处理任意索引位元素的方法，只有队列的头一个元素能访问。Queue 的所有实现都要具有一个固定的容量：队列已满时，不能再添加元素。类似地，队列为空时，不能再删除元素。很多基于队列的算法都会用到满和空这两个状态，所以 Queue 接口定义的方法通过返回值表明这两个状态，而不会抛出异常。具体而言，peek() 和 poll() 方法返回 null 表示队列为空。因此，多数 Queue 接口的实现不允许用 null 作元素。

阻塞式队列（blocking queue）是一种定义了阻塞式 put() 和 take() 方法的队列。put() 方法的作用是把元素添加到队列中，如果需要，这个方法会一直等待，直到队列中有存储元素的空间为止。而 take() 方法的作用是从队头移除元素，如果需要，这个方法会一直等待，直到队列中有元素可供移除为止。阻塞式队列是很多多线程算法的重要组成部分，因此 BlockingQueue 接口（扩展 Queue 接口）在 java.util.concurrent 包中定义。

队列不像集、列表和映射那么常用，只在特定的多线程编程风格中会用到。这里，我们不举实例，而是试着厘清一些令人困惑的队列插入和移除操作。

1. 把元素添加到队列中

• add()方法

这个方法在 Collection 接口中定义，只是使用常规的方式添加元素。对有界的队列来说，如果队列已满，这个方法可能会抛出异常。

• offer()方法

这个方法在 Queue 接口中定义，但是由于有界的队列已满而无法添加元素时，这个方法返回 false，而不会抛出异常。

BlockingQueue 接口定义了一个超时版 offer() 方法，如果队列已满，会在指定的时间内等待空间。这个版本和基本版一样，成功插入元素时返回 true，否则返回 false。

• put()方法

这个方法在 BlockingQueue 接口中定义，会阻塞操作：如果因为队列已满而无法插入元素，put() 方法会一直等待，直到其他线程从队列中移除元素，有空间插入新元素为止。

2. 把元素从队列中移除

• remove()方法

Collection 接口中定义了 remove() 方法，把指定的元素从队列中移除。除此之外，Queue 接口还定义了一个没有参数的 remove() 方法，移除并返回队头的元素。如果队列为空，这个方法会抛出 NoSuchElementException 异常。

• poll()方法

这个方法在 Queue 接口中定义，作用和 remove() 方法类似，移除并返回队头的元素，不过，如果队列为空，这个方法会返回 null，而不抛出异常。

BlockingQueue 接口定义了一个超时版 poll() 方法，在指定的时间内等待元素添加到空队列中。

• take()方法

这个方法在 BlockingQueue 接口中定义，用于删除并返回队头的元素。如果队列为空，这个方法会等待，直到其他线程把元素添加到队列中为止。

• drainTo()方法

这个方法在 BlockingQueue 接口中定义，作用是把队列中的所有元素都移除，然后把这些元素添加到指定的 Collection 对象中。这个方法不会阻塞操作，等待有元素添加到队列中。这个方法有个变体，接受一个参数，指定最多移除多少个元素。

3. 查询

就队列而言，“查询”的意思是访问队头的元素，但不将其从队列中移除。

• element()方法

这个方法在 Queue 接口中定义，其作用是返回队头的元素，但不将其从队列中移除。如果队列为空，这个方法抛出 NoSuchElementException 异常。

• peek()方法

这个方法在 Queue 接口中定义，作用和 element() 方法类似，但队列为空时，返回 null。

　使用队列时，最好选定一种处理失败的方式。例如，如果想在操作成功之前一直阻塞，应该选择 put() 和 take() 方法；如果想检查方法的返回值，判断操作是否成功，应该选择 offer() 和 poll() 方法。

LinkedList 类也实现了 Queue 接口，提供的是无界 FIFO 顺序，插入和移除操作需要常数时间。LinkedList 对象可以使用 null 作元素，不过，当列表用作队列时不建议使用 null。

java.util 包中还有另外两个 Queue 接口的实现。一个是 PriorityQueue 类，这种队列根据Comparator 对象排序元素，或者根据 Comparable 类型元素的 compareTo() 方法排序元素。PriorityQueue 对象的队头始终是根据指定排序方式得到的最小值。另外一个是 ArrayDeque 类，实现的是双端队列，一般在需要用到栈的情况下使用。

java.util.concurrent 包中也包含一些 BlockingQueue 接口的实现，目的是在多线程编程环境中使用。有些实现很高级，甚至无需使用同步方法。

8.1.6　实用方法

java.util.Collections 类定义了一些静态实用方法，用于处理集合。其中有一类方法很重要，是集合的包装方法：这些方法包装指定的集合，返回特殊的集合。包装集合的目的是把集合本身没有提供的功能绑定到集合上。包装集合能提供的功能有：线程安全性、写保护和运行时类型检查。包装集合都以原来的集合为后盾，因此，在包装集合上调用的方法其实会分派给原集合的等效方法完成。这意味着，通过包装集合修改集合后，改动也会体现在原集合身上；反之亦然。

第一种包装方法为包装的集合提供线程安全性。java.util 包中的集合实现，除了过时的 Vector 和 Hashtable 类之外，都没有 synchronized 方法，不能禁止多个线程并发访问。如果需要使用线程安全的集合，而且不介意同步带来的额外开销，可以像下面这样创建集合：

List<String> list =
    Collections.synchronizedList(new ArrayList<String>());
Set<Integer> set =
    Collections.synchronizedSet(new HashSet<Integer>());
Map<String,Integer> map =
    Collections.synchronizedMap(new HashMap<String,Integer>());

第二种包装方法创建的集合对象不能修改底层集合，得到的集合是只读的，只要试图修改集合的内容，就会抛出 UnsupportedOperationException 异常。如果要把集合传入方法，但不允许修改集合，也不允许使用任何方式改变集合的内容，就可以使用这种包装集合：

List<Integer> primes = new ArrayList<Integer>();
List<Integer> readonly = Collections.unmodifiableList(primes);
// 可以修改primes列表
primes.addAll(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19));
// 但不能修改只读的包装集合
readonly.add(23); // 抛出UnsupportedOperationException异常

java.util.Collections 类还定义了用来操作集合的方法。其中最值得关注的是排序和搜索集合元素的方法：

Collections.sort(list);
// 必须先排序列表中的元素
int pos = Collections.binarySearch(list, "key");

Collections 类中还有些方法值得关注：

// 把list2中的元素复制到list1中，覆盖list1
Collections.copy(list1, list2);
// 使用对象o填充list
Collections.fill(list, o);
// 找出集合c中最大的元素
Collections.max(c);
// 找出集合c中最小的元素
Collections.min(c);
Collections.reverse(list); // 反转列表
Collections.shuffle(list); // 打乱列表

你最好全面熟悉 Collections 和 Arrays 类中的实用方法，这样遇到常见任务时就不用自己动手实现了。

特殊的集合

除了包装方法之外，java.util.Collections 类还定义了其他实用方法，一些用于创建只包含一个元素的不可变集合实例，一些用于创建空集合。singleton()、singletonList() 和 singletonMap() 方法分别返回不可变的 Set、List 和 Map 对象，而且只包含一个指定的对象或键值对。如果要把单个对象当成集合传入方法，可以使用这些方法。

Collections 类还定义了一些返回空集合的方法。如果你编写的方法要返回一个集合，遇到没有返回值的情况时，一般最好返回空集合，而不要返回 null 等特殊的值：

Set<Integer> si = Collections.emptySet();
List<String> ss = Collections.emptyList();
Map<String,Integer> m = Collections.emptyMap();

最后还有个 nCopies() 方法。这个方法返回一个不可变的 List 对象，包含指定数量个指定对象的副本：

List<Integer> tenzeros = Collections.nCopies(10, 0);

8.1.7　数组和辅助方法

由对象组成的数组和集合的作用类似，而且二者之间可以相互转换：

String[] a ={ "this", "is", "a", "test" }; // 一个数组
// 把数组当成大小不可变的列表
List<String> l = Arrays.asList(a);
// 创建一个大小可变的副本
List<String> m = new ArrayList<String>(l);
// asList()是个变长参数方法，所以也可以这么做：
Set<Character> abc = new HashSet<Character>(Arrays.asList('a', 'b', 'c'));
// Collection接口定义了toArray()方法。不传入参数时，这个方法创建
// Object[]类型的数组，把集合中的元素复制到数组中，然后返回这个数组
// 把set中的元素存入数组
Object[] members = set.toArray();
// 把list中的元素存入数组
Object[] items = list.toArray();
// 把map的键存入数组
Object[] keys = map.keySet().toArray();
// 把map的值存入数组
Object[] values = map.values().toArray();
// 如果不想返回Object[]类型的值，可以把一个所需类型的数组传入toArray()方法
// 如果传入的数组不够大，会再创建一个相同类型的数组
// 如果传入的数组太大，复制集合元素后剩余的位置使用null填充
String[] c = l.toArray(new String[0]);

除此之外，还有一些有用的辅助方法，用于处理 Java 数组。为了完整性，这里也会介绍。

java.lang.System 类定义了一个 arraycopy() 方法，作用是把一个数组中的指定元素复制到另一个数组的指定位置。这两个数组的类型必须相同，甚至可以是同一个数组：

char[] text = "Now is the time".toCharArray();
char[] copy = new char[100];
// 从text的第4个元素开始，复制10个字符到copy中
// 这10个字符的位置从copy[0]开始
System.arraycopy(text, 4, copy, 0, 10);
// 把一些元素向后移，留出位置插入其他元素
System.arraycopy(copy, 3, copy, 6, 7);

Arrays 类还定义了一些有用的静态方法：

int[] intarray = new int[] { 10, 5, 7, -3 }; // 由整数组成的数组
Arrays.sort(intarray);                       // 原地排序数组
// 在索引2找到值7
int pos = Arrays.binarySearch(intarray, 7);
// 未找到：返回负数
pos = Arrays.binarySearch(intarray, 12);
// 由对象组成的数组也能排序和搜索
String[] strarray = new String[] { "now", "is", "the", "time" };
Arrays.sort(strarray);  // 排序的结果：{ "is", "now", "the", "time" }
// Arrays.equals()方法比较两个数组中的所有元素
String[] clone = (String[]) strarray.clone();
boolean b1 = Arrays.equals(strarray, clone); // 是的，两个数组相等
// Arrays.fill()方法用于初始化数组的元素
// 一个空数组，所有元素都是0
byte[] data = new byte[100];
// 把元素都设为-1
Arrays.fill(data, (byte) -1);
// 把第5-9个元素设为-2
Arrays.fill(data, 5, 10, (byte) -2);

在 Java 中，数组可以视作对象，也可以按照对象的方法处理。假如有个对象 o，可以使用类似下面的代码判断这个对象是否为数组。如果是，则判断是什么类型的数组：

Class type = o.getClass();
if (type.isArray()) {
  Class elementType = type.getComponentType();
}