《Java核心技术卷一》第九章

第9章 集合

本章将介绍如何利用 Java 类库帮助我们实现程序设计所需的传统数据结构。

9.1 Java 集合框架

Java 最初的版本只为最常用的数据结构提供了很少的一组类：Vector、Stack、Hashtable、BitSet 与 Enumeration 接口，其中 Enumeration 接口提供了一种抽象机制，用于访问任意容器中的元素。

9.1.1 集合接口与实现分离

Java 集合类库将接口（interface）与实现（implementation）分离。下面利用我们熟悉的一个数据结构——队列（queue）来说明接口与实现如何分离。

**队列接口（queue interface）**指出可以在队尾添加元素，在队头删除元素，并且可以查找队列中元素的个数。当需要收集对象并按照“先进先出”方式获取对象时，就应该使用队列（见图 9-1）。

队列接口的最简形式可能如下所示：

public interface Queue<E> // a simplified form of the interface in the standard library
{
    void add(E element);
    E remove();
    int size();
}

这个接口并没有说明队列是如何实现的。队列通常有两种实现方式：一种是使用循环数组；另一种是使用链表（见图 9-2）。

每个实现都可以用一个实现了 Queue 接口的类表示：

public class CircularArrayQueue<E> implements Queue<E> // not an actual library class
{
    private int head;
    private int tail;
    CircularArrayQueue(int capacity) { ... }
    public void add(E element) { ... }
    public E remove() { ... }
    public int size() { ... }
    private E[] elements;
}

public class LinkedListQueue<E> implements Queue<E> // not an actual library class
{
    private Link head;
    private Link tail;
    LinkedListQueue() { ... }
    public void add(E element) { ... }
    public E remove() { ... }
    public int size() { ... }
}

注释：实际上，Java 类库没有名为 CircularArrayQueue 和 LinkedListQueue 的类。这里只是以这些类为例来解释集合接口与实现在概念上的区分。如果需要一个循环数组队列，可以使用 ArrayDeque 类。如果需要一个链表队列，就直接使用 LinkedList 类，这个类实现了 Queue 接口。

在程序中使用队列时，一旦已经构造了集合，你不需要知道究竟使用了哪种实现。因此，只是在构造集合对象时，才会使用具体的类。可以使用**接口类型（interface type）**存放集合引用。

Queue<Customer> expressLane = new CircularArrayQueue<>(100);
expressLane.add(new Customer("Harry"));

利用这种方法，一旦改变了想法，你可以很轻松地使用另外一种不同的实现。只需要修改程序中的一个地方（即调用构造器的语句）。如果觉得 LinkedListQueue 是个更好的选择，就将代码修改为：

Queue<Customer> expressLane = new LinkedListQueue<>();
expressLane.add(new Customer("Harry"));

为什么选择这种实现，而不选择其他实现呢？接口本身并不能说明一种实现的效率如何。某种程度上讲，循环数组要比链表更高效，因此多数人优先选择循环数组。不过，通常来讲，这样做也需要付出一定的代价。

循环数组是一个有界（bounded）集合，它的容量有限。如果程序中要收集的对象数量没有上限，就最好使用链表实现。

在研究 API 文档时，会发现另外一组名字以 Abstract 开头的类，例如，AbstractQueue。这些类是为类库实现者而设计的。如果想要实现你自己的队列类（也许不太可能），会发现扩展 AbstractQueue 类要比实现 Queue 接口中的所有方法更容易。

9.1.2 Collection 接口

在 Java 类库中，集合类的基本接口是 Collection 接口。这个接口有两个基本方法：

public interface Collection<E> {
    boolean add(E element);
    Iterator<E> iterator();
}

除了这两个方法之外，还有几个方法，稍后将会介绍。

• add 方法用于向集合中添加元素。如果添加元素确实改变了集合就返回 true；如果集合没有发生变化就返回 false。例如，如果试图向集（set）中添加一个对象，而这个对象在集中已经存在，这个 add 请求就没有实效，因为集中不允许有重复的对象。
• iterator 方法用于返回一个实现了 Iterator 接口的对象。可以使用这个迭代器对象依次访问集合中的元素。下一节讨论迭代器。

9.1.3 迭代器

Iterator 接口包含 4 个方法：

public interface Iterator<E> {
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemaining(Consumer<? super E> action);
}

通过反复调用 next 方法，可以逐个访问集合中的每个元素。但是，如果到达了集合的末尾，next 方法将抛出一个 NoSuchElementException。因此，在调用 next 之前需要调用 hasNext 方法。如果迭代器对象还有更多可以访问的元素，这个方法就返回 true。如果想要查看集合中的所有元素，就请求一个迭代器，当 hasNext 返回 true 时就反复地调用 next 方法。例如：

Collection<String> c = ...
Iterator<String> iter = c.iterator();
while (iter.hasNext()) {
    String element = iter.next();
    do something with element
}

可以更加简洁地将这个循环写为“foreach”循环：

for (String element : c)
    do something with element

编译器会把“for each”循环转换为一个带迭代器的循环。

“for each”循环可以处理任何实现了 Iterable 接口的对象，这个接口只有一个抽象方法：

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

Collection 接口扩展了 Iterable 接口。因此，对于标准类库中的任何集合都可以使用“for each”循环。

也可以不写循环，而是调用 forEachRemaining 方法并提供一个 lambda 表达式（它会处理一个元素）。将对迭代器的每一个元素调用这个 lambda 表达式，直到再没有元素为止。

iterator.forEachRemaining(element -> do something with element);

访问元素的顺序取决于集合类型。如果迭代处理一个 ArrayList，迭代器将从索引 0 开始，每迭代一次，索引值加 1。不过，如果访问 HashSet 中的元素，会按照一种基本上随机的顺序获得元素。虽然可以确保在迭代过程中能够遍历到集合中的所有元素，但是无法预知访问各元素的顺序。这通常并不是什么向题，因为对于计算总和或统计匹配之类的计算，顺序并不重要。

注释：编程老手会注意到：Iterator 接口的 next 和 hasNext 方法与 Enumeration 接口的 nextElement 和 hasMoreElements 方法的作用一样。Java 集合类库的设计者本来可以选择使用 Enumeration 接口，但是他们不喜欢这个接口累赘的方法名，于是引入了具有较短方法名的一个新接口。

Java 集合类库中的迭代器与其他类库中的迭代器在概念上有一个重要的区别。在传统的集合类库中，例如，C++ 的标准模板库，迭代器是根据数组索引创建的。如果给定这样一个迭代器，可以查找存储在指定位置上的元素，就像如果知道数组索引 i，就可以查找数组元素 a[i]。不需要查找元素，也可以将迭代器向前移动一个位置。这与不执行查找而通过调用 i++ 向前移动数组索引的操作一样。但是，Java 迭代器并不是这样处理的。查找操作与位置变化紧密耦合。查找一个元素的唯一方法是调用 next，而在执行查找操作的同时，迭代器的位置就会随之向前移动。

因此，可以认为 Java 迭代器位于两个元素之间。当调用 next 时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用（见图 9-3）。

注释：这里还可以做一个有用的对比。可以认为 Iterator.next 等价于 InputStream.read。从数据流中读取一个字节就会自动地“消耗掉”这个字节。下一次调用 read 将会消耗并返回输入中的下一个字节。类似地，反复地调用 next 就可以读取集合中的所有元素。

Iterator 接口的 remove 方法会删除上次调用 next 方法返回的元素。在大多数情况下，这是有道理的——在决定某个元素确实是要删除的元素之前，应该先看一下这个元素。不过，如果想要删除指定位置上的元素，仍然需要越过这个元素。例如，可以如下删除一个字符串集合中的第一个元素：

Iterator<String> it = c.iterator();
it.next();       // skip over the first element
it.remove();     // now remove it

更重要的是，next 方法和 remove 方法调用之间存在依赖性。调用 remove 之前没有调用 next，将是不合法的。 如果这样做，将会抛出一个 IllegalStateException 异常。

如果想删除两个相邻的元素，不能直接这样调用：

it.remove();
it.remove(); // ERROR

实际上，必须先调用 next 越过将要删除的元素。

it.remove();
it.next();
it.remove(); // OK

9.1.4 泛型实用方法

由于 Collection 与 Iterator 都是泛型接口，这意味着你可以编写处理任何集合类型的实用方法。例如，下面是一个检测任意集合是否包含指定元素的泛型方法：

public static <E> boolean contains(Collection<E> c, Object obj) {
    for (E element : c)
        if (element.equals(obj))
            return true;
    return false;
}

Java 类库的设计者认为：这些实用方法中有一些非常有用，应该将它们提供给用户使用。这样一来，类库的使用者就不必自己重新实现这些方法了。contains 就是这样一个实用方法。

事实上，Collection 接口声明了很多有用的方法，所有的实现类都必须提供这些方法。下面列举了其中的一部分：

int size()
boolean isEmpty()
boolean contains(Object obj)
boolean containsAll(Collection<?> c)
boolean equals(Object other)
boolean addAll(Collection<? extends E> from)
boolean remove(Object obj)
boolean removeAll(Collection<?> c)
void clear()
boolean retainAll(Collection<?> c)
Object[] toArray()

在这些方法中，有许多方法的功能非常明确，不需要过多的解释。在本节末尾的 API 注释中可以找到有关它们的完整说明。

当然，如果实现 Collection 接口的每一个类都要提供如此多的例行方法，这将是一件很烦人的事情。为了能够让实现者更轻松一些，Java 类库提供了一个类 AbstractCollection，其中保持基础方法 size 和 iterator 仍为抽象方法，但是为实现者实现了其他例行方法。

例如：

public abstract class AbstractCollection<E> implements Collection<E> {
    public abstract Iterator<E> iterator();

    public boolean contains(Object obj) {
        for (E element : this) // calls iterator()
            if (element.equals(obj))
                return true;
        return false;
    }
    ...
}

这样一来，具体集合类可以扩展 AbstractCollection 类。现在要由具体的集合类提供 iterator 方法，而 contains 方法已由 AbstractCollection 超类提供。不过，如果子类有更加高效的方式实现 contains 方法，也完全可以提供 contains 方法。

这种做法有些过时了。这些方法最好是 Collection 接口的默认方法。但实际上并不是这样。不过，确实已经增加很多默认方法。其中大部分方法都与流的处理有关（有关内容将在卷Ⅱ中讨论）。另外，还有一个很有用的方法：

default boolean removeIf(Predicate<? super E> filter)

这个方法用于删除满足某个条件的元素。

9.2 集合框架中的接口

Java 集合框架为不同类型的集合定义了大量接口，如图 9-4 所示。

集合有两个基本接口：Collection 和 Map。我们已经看到，可以用以下方法在集合中插入元素：

boolean add(E element)

不过，映射包含键/值对，要用 put 方法在映射中插入元素：

V put(K key, V value)

要从集合读取元素，可以用迭代器访问元素。不过，可以使用 get 方法从映射中读取值：

V get(K key)

List 是一个有序集合（ordered collection）。元素会增加到容器中的特定位置。可以采用两种方式访问元素：使用迭代器访问，或者使用一个整数索引来访问。后面这种方法称为随机访问（random access），因为这样可以按任意顺序访问元素。与之不同，使用迭代器访问时，必须顺序地访问元素。

List 接口定义了多个用于随机访问的方法：

void add(int index, E element)
void remove(int index)
E get(int index)
E set(int index, E element)

ListIterator 接口是 Iterator 的一个子接口。它定义了一个方法用于在迭代器位置前面增加一个元素：

void add(E element)

坦率地讲，集合框架的这个方面设计得很不好。实际上有两种有序集合，其性能开销有很大差异：

• 由数组支持的有序集合可以快速地随机访问，因此适合使用 List 方法并提供一个整数索引来访问。
• 与之不同，链表尽管也是有序的，但是随机访问很慢，所以最好使用迭代器来遍历。

如果原先提供两个接口就会容易一些了。

注释：为了避免对链表执行随机访问操作，Java 1.4 引入了一个标记接口 RandomAccess。这个接口不包含任何方法，不过可以用它来测试一个特定的集合是否支持高效的随机访问：

if (c instanceof RandomAccess)
    use random access algorithm
else
    use sequential access algorithm

Set 接口等同于 Collection 接口，不过其方法的行为有更严谨的定义。集（set）的 add 方法不允许增加重复的元素。要适当地定义集的 equals 方法：只要两个集包含同样的元素就认为它们是相等的，而不要求这些元素有同样的顺序。hashCode 方法的定义要保证包含相同元素的两个集会得到相同的散列码。

既然方法签名是一样的，为什么还要建立一个单独的接口呢？从概念上讲，并不是所有集合都是集。建立一个 Set 接口可以允许程序员编写只接受集的方法。

SortedSet 和 SortedMap 接口会提供用于排序的比较器对象，这两个接口定义了可以得到集合子集视图的方法。

最后，Java 6 引入了接口 NavigableSet 和 NavigableMap，其中包含额外的一些用于搜索和遍历有序集和映射的方法。（理想情况下，这些方法本应直接包含在 SortedSet 和 SortedMap 接口中。）TreeSet 和 TreeMap 类实现了这些接口。

9.3 具体集合

表 9-1 展示了 Java 类库中的集合，并简要描述了每个集合类的用途。（为简单起见，这里省略了线程安全集合，那些集合将在第 12 章中介绍。）

在表 9-1 中，除了以 Map 结尾的类之外，其他类都实现了 Collection 接口，而以 Map 结尾的类实现了 Map 接口。

图 9-5 显示了这些类之间的关系。

9.3.1 链表

本书的很多示例中已经使用了数组和它的动态“兄弟”——ArrayList 类。不过，数组和数组列表都有一个重大的缺陷：从数组中间删除一个元素开销很大，其原因是数组中位于被删除元素之后的所有元素都要向数组的前端移动（见图 9-6）。在数组中间插入一个元素也是如此。

大家都知道的另外一个数据结构——链表（linked list）解决了这个问题。数组是在连续的存储位置上存放对象引用，而链表则是将每个对象存放在单独的链接（link）中。每个链接还存放着序列中下一个链接的引用。在 Java 程序设计语言中，所有链表实际上都有双向链接（doubly linked），即每个链接还存储着其前驱的引用（见图 9-7）。

从链表中间删除一个元素是一个很轻松的操作，只需要更新所删除元素周围的链接即可（见图 9-8）。

也许你曾经在数据结构课程中学习过如何实现链表。在链表中添加或删除元素时，绕来绕去的链接可能给你留下了糟糕的印象。如果真是如此的话，你肯定会为 Java 集合类库提供了一个可以直接使用的 LinkedList 类而感到高兴。

在下面的代码示例中，先添加 3 个元素，然后再将第 2 个元素删除：

var staff = new LinkedList<String>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
Iterator<String> iter = staff.iterator();
String first  = iter.next(); // visit first element
String second = iter.next(); // visit second element
iter.remove();               // remove last visited element

不过链表与泛型集合之间有一个重要的区别。链表是一个有序集合（ordered collection），每个对象的位置十分重要。LinkedList.add 方法将对象添加到链表的尾部。但是，常常需要将元素添加到链表的中间。因为迭代器描述了集合中的位置，所以这种依赖于位置的 add 方法将由迭代器负责。不过，只有对自然有序的集合使用迭代器来添加元素才有意义。例如，下一节将要讨论的集（set）数据类型中，元素是完全无序的。因此，Iterator 接口中没有 add 方法。

实际上，集合类库提供了一个子接口 ListIterator，其中包含 add 方法：

interface ListIterator<E> extends Iterator<E> {
    void add(E element);
}

与 Collection.add 不同，这个方法不返回 boolean 类型的值，它假定 add 操作总会改变链表。

另外，ListIterator 接口有两个方法可以用来反向遍历链表。

E previous()
boolean hasPrevious()

与 next 方法一样，previous 方法会返回越过的对象。

LinkedList 类的 listIterator 方法返回一个实现了 ListIterator 接口的迭代器对象。

ListIterator<String> iter = staff.listIterator();

add 方法在迭代器位置之前添加一个新对象。例如，下面的代码将越过链表中的第一个元素，在第二个元素之前添加 "Juliet"（见图 9-9）：

var staff = new LinkedList<String>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
ListIterator<String> iter = staff.listIterator();
iter.next(); // skip past first element
iter.add("Juliet");

如果多次调用 add 方法，将按照提供元素的次序把元素添加到链表中。它们被依次添加到迭代器当前位置之前。

当用一个刚由 listIterator() 方法返回并指向链表表头的迭代器来调用 add 操作时，新添加的元素将变成列表的新表头。当迭代器越过链表的最后一个元素时（即 hasNext() 返回 false 时），添加的元素将成为列表的新表尾。

如果链表有 n 个元素，会有 n+1 个位置可以添加新元素。这些位置与迭代器的 n+1 个可能的位置相对应。例如，如果链表包含 3 个元素 A、B、C，就有 4 个位置（标记为 |）可以插入新元素：

| A B C
A | B C
A B | C
A B C |

注释：在用“光标”做类比时要当心。remove 操作与退格（Backspace）键的工作方式不太一样。在调用 next 之后，remove 方法确实会删除迭代器左侧的元素，这与退格键一样。但是，如果调用了 previous，则会删除迭代器右侧的元素。而且不能连续调用两次 remove。

add 方法只依赖于迭代器的位置，而 remove 方法不同，它依赖于迭代器的状态。

最后需要说明，set 方法会用一个新元素替换调用 next 或 previous 方法返回的上一个元素。例如，下面的代码将用一个新值替换列表的第一个元素：

ListIterator<String> iter = list.listIterator();
String oldValue = iter.next(); // returns first element
iter.set(newValue);            // sets first element to newValue

可以想象，如果在某个迭代器修改集合时，另一个迭代器却在遍历这个集合，可能就会出现混乱。例如，假设一个迭代器指向一个元素前面的位置，而另一个迭代器刚刚删除了这个元素，现在前一个迭代器就是无效的，不能再使用。链表迭代器设计为可以检测到这种修改。如果一个迭代器发现它的集合被另一个迭代器修改了，或是被该集合自身的某个方法修改了，就会抛出一个 ConcurrentModificationException 异常。例如，考虑下面这段代码：

List<String> list = ...
ListIterator<String> iter1 = list.listIterator();
ListIterator<String> iter2 = list.listIterator();
iter1.next();
iter1.remove();
iter2.next(); // throws ConcurrentModificationException

因为 iter2 检测出这个列表被外部修改，所以调用 iter2.next 会抛出一个 ConcurrentModificationException 异常。

为了避免发生并发修改异常，请遵循这样一个简单的规则：可以根据需要为一个集合关联多个迭代器，前提是这些迭代器只能读取集合。或者，可以关联一个能同时读写的迭代器。

检测并发修改的做法很简单。集合会跟踪更改操作（诸如添加或删除元素）的次数。每个迭代器都会为它负责的更改操作维护一个单独的更改操作数。在每个迭代器方法的开始处，迭代器会检查它自己的更改操作数与集合的更改操作数是否相等。如果不一致，就抛出一个 ConcurrentModificationException 异常。

注释：不过，对于并发修改的检测有一个奇怪的例外。链表只跟踪对列表的结构性修改，例如，添加和删除链接。set 方法不被视为结构性修改。可以为一个链表关联多个迭代器，所有迭代器都可以调用 set 方法改变现有链接的内容。本章后面介绍的 Collections 类的许多算法都需要使用这个功能。

现在我们已经了解了 LinkedList 类的基本方法。可以使用 ListIterator 类从前后两个方向遍历链表中的元素，以及添加和删除元素。

在 9.2 节已经看到，Collection 接口还声明了操作链表的很多其他有用的方法。其中大部分方法都是在 LinkedList 类的超类 AbstractCollection 中实现的。例如，toString 方法会调用所有元素的 toString，并生成一个格式为 [A, B, C] 的长字符串。这为调试工作提供了便利。可以使用 contains 方法检测某个元素是否出现在链表中。例如，如果链表中已经包含一个等于 "Harry" 的字符串，调用 staff.contains("Harry") 将会返回 true。

Java 类库还提供了许多理论上存在一定争议的方法。链表不支持快速随机访问。如果要查看链表中的第 n 个元素，就必须从头开始，越过 n-1 个元素。没有捷径可走。鉴于这个理由，需要按整数索引访问元素时，程序员通常不选用链表。

然而，LinkedList 类还是提供了一个 get 方法，用来访问某个特定元素：

LinkedList<String> list = ...;
String obj = list.get(n);

当然，这个方法的效率不太高。如果你发现自己正在使用这个方法，说明对于所要解决的问题，你可能使用了错误的数据结构。

绝对不要使用这个“虚假”的随机访问方法来遍历链表。下面这段代码的效率极低：

for (int i = 0; i < list.size(); i++)
    do something with list.get(i);

每次查找一个元素都要从列表开头重新开始搜索。LinkedList 对象根本不会缓存位置信息。

注释：get 方法做了一个微小的优化：如果索引大于等于 size() / 2，就从列表尾端开始搜索元素。

列表迭代器接口还有一个方法，可以告诉你当前位置的索引。实际上，从概念上讲，因为 Java 迭代器指向两个元素之间的位置，所以可以有两个索引：nextIndex 方法返回下一次调用 next 方法时所返回元素的整数索引；previousIndex 方法返回下一次调用 previous 方法时所返回元素的整数索引。当然，这个索引只比 nextIndex 返回的索引值小 1。这两个方法的效率非常高，因为迭代器会维护当前位置的计数值。最后需要说明一点，如果有一个整数索引 n，list.listIterator(n) 将返回一个迭代器，这个迭代器指向索引为 n 的元素前面的位置。也就是说，调用 next 与调用 list.get(n) 会得到同一个元素，只是获得迭代器的效率比较低。

如果链表中只有很少几个元素，就完全没有必要为 get 方法和 set 方法的开销而烦恼。但是，既然如此，最初为什么要使用链表呢？使用链表的唯一理由是尽可能地减少在列表中间插入或删除元素的开销。如果列表只有很少几个元素，就完全可以使用 ArrayList。

建议一定要远离所有使用整数索引表示链表中位置的方法。如果需要对集合进行随机访问，就使用数组或 ArrayList，而不要使用链表。

程序清单 9-1 中的程序具体使用了链表。它创建了两个列表，将它们合并在一起，然后从第二个列表中每隔一个元素删除一个元素，最后测试 removeAll 方法。建议跟踪一下程序流程，要特别注意迭代器。可以画出迭代器位置示意图，你会发现这很有帮助，如下所示：

A C E B D F G
A C E B D F G
A B | C E B | D F G

注意以下调用：

System.out.println(a);

这会调用 AbstractCollection 类中的 toString 方法，打印链表 a 中的所有元素。

9.3.2 数组列表

在上一节中，我们了解了 List 接口和实现了这个接口的 LinkedList 类。List 接口描述一个有序集合，其中每个元素的位置很重要。有两种访问元素的协议：一种是通过迭代器，另一种是通过 get 和 set 方法随机访问。后者不适用于链表，但当然 get 和 set 方法对数组很有用。

集合类库提供了我们熟悉的 ArrayList 类，这个类也实现了 List 接口。ArrayList 封装了一个动态再分配的对象数组。

注释：对于一个经验丰富的 Java 程序员来说，需要一个动态数组时，可能会使用 Vector 类。为什么要用 ArrayList 而不是 Vector 呢？原因很简单：Vector 类的所有方法都是同步的。可以安全地从两个线程访问一个 Vector 对象。但是，如果只从一个线程访问 Vector（这种情况更为常见），代码就会在同步操作上白白浪费大量的时间。而与之不同，ArrayList 方法不是同步的，因此，不需要同步时建议使用 ArrayList，而不要使用 Vector。

9.3.3 散列集

链表和数组允许你根据意愿指定元素的次序。但是，如果想要查找某个特定的元素，却又不记得它的位置，就需要访问所有元素，直到找到匹配的元素为止。如果集合中包含的元素很多，这就会耗费很长时间。如果不在意元素的顺序，还有几种数据结构允许你更快速地查找元素。缺点是，这些数据结构不允许你控制元素出现的次序，它们会按照对自己最方便的方式组织元素。

有一种众所周知的数据结构，可以用于快速地查找对象，这就是散列表（hash table）。散列表为每个对象计算一个整数，称为散列码（hash code）。散列码是以某种方式由对象的实例字段得出的一个整数，这种方式可以尽可能保证有不同数据的对象将生成不同的散列码。表 9-2 列出了几个散列码的示例，它们是由 String 类的 hashCode 方法得到的。

如果定义你自己的类，你就要负责实现自己的 hashCode 方法。有关 hashCode 方法的详细内容请参见第 5 章。注意，你的实现应该与 equals 方法兼容，即如果 a.equals(b) 为 true，那么 a 与 b 必须有相同的散列码。

现在，重要的是要能够快速地计算出散列码，并且这个计算只与要计算散列的那个对象的状态有关，与散列表中的其他对象无关。

在 Java 中，散列表实现为链表数组。每个列表被称为桶（bucket）（参见图 9-10）。要想查找一个对象在表中的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的数就是保存这个元素的那个桶的索引。例如，如果某个对象的散列码为 76268，总共有 128 个桶，那么这个对象应该保存在第 108 号桶中（因为 76268 % 128 的余数是 108）。或许很幸运，这个桶中没有其他元素，此时将元素直接插入这个桶中就可以了。当然，有时候会遇到桶已经填充了元素的情况。这种现象被称为散列冲突（hash collision）。这时，需要将新对象与那个桶中的所有对象进行比较，查看这个对象是否已经存在。如果散列码合理地随机分布，而且桶的数量足够大，需要比较的次数就会很少。

注释：在 Java 8 中，桶满时会从链表变为平衡二叉树。如果选择的散列函数不好，会产生很多冲突，或者如果有恶意代码试图在散列表中填充多个有相同散列码的值，改为平衡二叉树能提高性能。

提示：散列表的键要尽可能属于一个实现了 Comparable 接口的类。这样一来，就能保证不会由于散列码分布不均匀而导致性能低下。

如果想更多地控制散列表的性能，可以指定一个初始的桶数。桶数是指用于收集有相同散列值的桶的数目。如果要插入到散列表中的元素太多，冲突数就会增加，这会降低检索性能。

如果大致知道最终会有多少个元素要插入散列表中，就可以设置桶数。通常，要将桶数设置为预计元素个数的 75%～150%。有些研究人员认为：将桶数设置为一个素数是一个好主意，以防止键的聚集。不过，对此并没有确凿的证据。标准类库使用的桶数是 2 的幂，默认值为 16（为表大小提供的任何值都将自动调整为 2 的下一个幂值）。

当然，并不总是能够知道需要存储多少个元素，也有可能最初的估计过低。如果散列表太满，就需要再散列（rehashed）。如果要对散列表再散列，就需要创建一个桶数更多的表，并将所有元素插入这个新表中，然后丢弃原来的表。装填因子（load factor） 可以确定何时对散列表进行再散列。例如，如果装填因子为 0.75（默认值），而表中已经填满了 75% 以上，就会自动再散列，新表的桶数是原来的两倍。对于大多数应用来说，装填因子为 0.75 是合理的。

散列表可以用于实现很多重要的数据结构。其中最简单的是集类型。集是没有重复元素的元素集合。集的 add 方法首先尝试在这个集中查找要添加的对象，只有这个元素不存在时才会添加这个对象。

Java 集合类库提供了一个 HashSet 类，它基于散列表实现了一个集。可以用 add 方法添加元素。contains 方法被重新定义，以便可以快速查找一个元素是否已经在集中。它只查看一个桶中的元素，而不必查看集合中的所有元素。

散列集迭代器将依次访问所有的桶。因为散列将元素分散存放在表中，所以会以一种看起来随机的顺序访问元素。只有不关心集合中元素的顺序时才应该使用 HashSet。

警告：在更改集中的元素时要格外小心。 如果元素的散列码发生了改变，这个元素在 数据结构中的位置也会变化。

9.3.4 树集

TreeSet 类与散列集十分类似，不过，它比散列集有所改进。树集是一个有序集合（sorted collection）。可以以任意顺序将元素插入集合中。在对集合进行遍历时，值将自动地按照排序后的顺序出现。例如，假设插入 3 个字符串，然后访问添加的所有元素：

var sorter = new TreeSet<String>();
sorter.add("Bob");
sorter.add("Amy");
sorter.add("Carl");
for (String s : sorter) System.out.println(s);

这时，值将按照有序顺序打印：

Amy
Bob
Carl

正如 TreeSet 类名所示，排序是用一个树数据结构完成的（当前实现使用的是红黑树（red-black tree）。有关红黑树的详细介绍请参见 Introduction to Algorithms，作者是 Thomas Cormen、Charles Leiserson、Ronald Rivest 和 Clifford Stein [The MIT Press, 2009]）。每次将一个元素添加到树中时，都会将其放置在正确的排序位置上。因此，迭代器总是以有序的顺序访问每个元素。

将一个元素添加到树中要比添加到散列表中慢，参见表 9-3 中的比较，但是，与检查数组或链表中的重复元素相比，使用树还是会快得多。如果树中包含 n 个元素，查找新元素的正确位置平均需要 log₂n 次比较。例如，如果一棵树包含了 1000 个元素，添加一个新元素大约需要比较 10 次。

注释：要使用树集，必须能够比较元素。这些元素必须实现 Comparable 接口，或者构造集时必须提供一个 Comparator（Comparable 和 Comparator 接口在第 6 章介绍过）。

回头看表 9-3，你可能很想知道是否应该总是使用树集而不是散列集。毕竟，添加元素所花费的时间看上去并没有增加太多，而且元素会自动排序。答案取决于你所要收集的数据。如果不需要数据有序，就没有必要付出排序的开销。更重要的是，对于某些数据来说，对其进行排序要比给出一个散列函数更加困难。散列函数只需要将对象适当地打乱存放，而比较函数必须精确地区分各个对象。

为了具体地了解它们之间的差异，可以考虑收集一个矩形集的任务。如果使用 TreeSet，就需要提供 Comparator<Rectangle>。如何比较两个矩形呢？按面积比较吗？这行不通。可能会有两个不同的矩形，它们的坐标不同，但面积却相同。树的排序顺序必须是全序（total ordering）。也就是说，任意两个元素都必须是可比较的，只有在两个元素相等时比较结果才为 0。矩形确实有一种排序方式（按照坐标的词典顺序排序），但这很牵强，而且计算很麻烦。相比之下，已经为 Rectangle 类定义了散列函数，它直接对坐标计算散列。

注释：从 Java 6 起，TreeSet 类实现了 NavigableSet 接口。这个接口增加了几个便利方法，用于查找元素以及反向遍历。详细信息请参见 API 注释。

9.3.5 队列与双端队列

前面已经讨论过，队列允许高效地在队尾添加元素，并在队头删除元素。

双端队列（deque）在队头和队尾都能高效地添加或删除元素。不支持在队列中间添加元素。

Java 6 中引入了 Deque 接口，ArrayDeque 和 LinkedList 类实现了这个接口。这两个类都可以提供双端队列，其大小可以根据需要扩展。

9.3.6 优先队列

优先队列（priority queue）中的元素可以按照任意的顺序插入，但会按照有序的顺序获取。也就是说，调用 remove 方法时，总会获得当前优先队列中最小的元素。不过，优先队列并没有对所有元素进行排序。如果迭代处理这些元素，并不需要对它们进行排序。

优先队列使用了一个精巧且高效的数据结构，称为堆（heap）。堆是一个自组织的二叉树，其添加（add）和删除（remove）操作会让最小的元素移动到根，而不必花费时间对元素进行排序。

与 TreeSet 一样，优先队列既可以包含实现了 Comparable 接口的类对象，也可以包含构造器中提供的 Comparator 对象。

优先队列的典型用法是任务调度。每一个任务有一个优先级，任务以随机顺序添加到队列中。每当启动一个新的任务时，将从队列中删除优先级最高的任务（因为习惯将 1 作为“最高”优先级，所以 remove 操作将删除最小的元素）。

9.4 映射

作为一个集合，集允许你快速地查找现有的元素。但是，要查找一个元素，需要有所查找的那个元素的准确副本。这不是一种常见的查找方式。通常，我们知道某些关键信息，希望查找与之关联的元素。映射（map）数据结构就是为此设计的。映射用来存放键/值对。如果提供了键，可以查找一个值。例如，可以存储一个员工记录表，其中键为员工 ID，值为 Employee 对象。在下面的小节中，我们会学习如何使用映射。

9.4.1 基本映射操作

Java 类库为映射提供了两个通用的实现：HashMap 和 TreeMap。这两个类都实现了 Map 接口。

• 散列映射对键进行散列，树映射根据键的顺序将它们组织为一个搜索树。
• 散列或比较函数只应用于键。与键关联的值不进行散列或比较。

应该选择散列映射还是树映射呢？与集一样，散列稍微快一些，如果不需要按照有序的顺序访问键，最好选择散列映射。

可以如下建立一个散列映射来存储员工信息：

var staff = new HashMap<String, Employee>(); // HashMap implements Map
var harry = new Employee("Harry Hacker");
staff.put("987-98-9996", harry);

每当向映射中添加一个对象时，必须同时提供一个键。在这里，键是一个字符串，对应的值是 Employee 对象。

要获取一个对象，必须使用键（因此必须记住键）：

var id = "987-98-9996";
Employee e = staff.get(id); // gets harry

如果映射中没有存储与指定键对应的信息，get 将返回 null。

null 返回值可能并不方便。有时对于没有出现在映射中的键，可以有一个合适的默认值。然后使用 getOrDefault 方法：

Map<String, Integer> scores = ...;
int score = scores.getOrDefault(id, 0); // gets 0 if the id is not present

键必须是唯一的。不能对同一个键存放两个值。如果用同一个键调用两次 put 方法，第二个值就会取代第一个值。实际上，put 将返回与这个键参数关联的上一个值。

remove 方法从映射中删除给定键对应的元素。size 方法返回映射中的元素数。

要迭代处理映射的键和值，最容易的方法是使用 forEach 方法。可以提供一个接收键和值的 lambda 表达式。映射中的每一项会依序调用这个表达式：

scores.forEach((k, v) ->
    System.out.println("key=" + k + ", value=" + v));

程序清单 9-6 显示了映射的具体使用。首先将键/值对添加到映射中。然后，从映射中删除一个键，同时与之关联的值也会删除。接下来，修改与某一个键关联的值，并调用 get 方法查找一个值。最后，迭代处理元素集。

9.4.2 更新映射条目

处理映射的一个难点是更新映射条目。正常情况下，可以得到与一个键关联的旧值，更新这个值，再放回更新后的值。不过，必须考虑一个特殊情况，即键第一次出现。

下面来看一个例子，考虑使用映射来统计一个单词在文件中出现的频度。看到一个单词（word）时，我们将计数器增 1，如下所示：

counts.put(word, counts.get(word) + 1);

这是可以的，不过有一种情况除外：就是第一次看到 word 时。在这种情况下，get 会返回 null，因此会出现一个 NullPointerException 异常。

一种简单的补救是使用 getOrDefault 方法：

counts.put(word, counts.getOrDefault(word, 0) + 1);

另一种方法是首先调用 putIfAbsent 方法。只有当键原先不存在（或者映射到 null）时才放入一个值：

counts.putIfAbsent(word, 0);
counts.put(word, counts.get(word) + 1); // now we know that get will succeed

不过还可以做得更好。merge 方法可以简化这个常见操作。如果键原先不存在，下面的调用：

counts.merge(word, 1, Integer::sum);

将把 word 与 1 关联，否则使用 Integer::sum 函数组合原值和 1（也就是将原值与 1 求和）。

API 注释还描述了另外一些更新映射条目的方法，不过这些方法不太常用。

9.4.3 映射视图

集合框架不认为映射本身是一个集合。（其他数据结构框架则认为映射是一个键/值对集合，或者是按键索引的值集合。）不过，可以得到映射的视图（view）——实现了 Collection 接口或某个子接口的对象。

有 3 种视图：键集、值集合（不是一个集）以及键/值对集。键和键/值对可以构成一个集，因为映射中一个键只能有一个副本。下面的方法：

Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K, V>> entrySet()

会分别返回这 3 个视图。（映射条目集的元素是实现了 Map.Entry 接口的类的对象。）

需要说明的是，keySet 不是 HashSet 或 TreeSet，而是实现了 Set 接口的另外某个类的对象。Set 接口扩展了 Collection 接口。因此，可以像使用任何集合一样使用 keySet。

例如，可以枚举一个映射的所有键：

Set<String> keys = map.keySet();
for (String key : keys)
    do something with key

如果想同时查看键和值，可以通过枚举映射条目来避免查找值。可以使用以下代码：

for (Map.Entry<String, Employee> entry : staff.entrySet()) {
    String k = entry.getKey();
    Employee v = entry.getValue();
    do something with k, v
}

提示：通过使用 var 声明可以避免笨重的 Map.Entry。

for (var entry : map.entrySet()){
 do something with entry.getKey(), entry.getValue()
}

或者直接使用 forEach 方法：

map.forEach((k, v) ->{
 do something with k, v
});

如果在键集视图上调用迭代器的 remove 方法，实际上会从映射中删除这个键和与它关联的值。不过，不能向键集视图中添加元素。另外，如果只添加一个键而没有同时添加值也是没有意义的。如果试图调用 add 方法，它会抛出一个 UnsupportedOperationException。映射条目集视图有同样的限制，尽管理论上好像可以增加新的键/值对，但实际上并不允许。

9.4.4 弱散列映射

在集合类库中有几个专用的映射类，我们将在这一节和后面几节中对它们做简要介绍。

设计 WeakHashMap 类是为了解决一个有趣的问题。如果有一个值，它对应的键已经不再在程序中的任何地方使用，将会出现什么情况？假设对某个键的最后一个引用已经消失，那么再没有任何途径可以引用这个值对象了。但是，由于程序中的任何部分都不再有这个键，因此无法从映射中删除这个键/值对。为什么垃圾回收器不能删除它呢？删除无用的对象不就是垃圾回收器的工作吗？

遗憾的是，事情没有这么简单。垃圾回收器会跟踪活动的对象。只要映射对象是活动的，其中的所有桶就是活动的，它们就不能被回收。因此，需要由程序负责从长期存活的映射中删除那些无用的值。或者，你可以使用 WeakHashMap。当键的唯一引用来自散列表条目时，这个数据结构将与垃圾回收器合作删除键/值对。

下面介绍这种机制的内部工作原理。WeakHashMap 使用弱引用（weak reference）保存键。WeakReference 对象将包含另一个对象的引用，在这里，就是一个散列表键。对于这种类型的对象，垃圾回收器采用一种特殊的方式进行处理。正常情况下，如果垃圾回收器发现某个特定的对象已经没有引用了，就会将其回收。不过，如果这个对象只能由一个 WeakReference 引用，垃圾回收器也会将其回收，但会将引用这个对象的弱引用放入一个队列。WeakHashMap 的操作会定期地检查这个队列，查找新加入的弱引用。一个弱引用进入队列意味着这个键不再由任何人使用，并且已经回收。于是，WeakHashMap 将删除相关联的映射条目。

9.4.5 链接散列集与映射

LinkedHashSet 和 LinkedHashMap 类会记住插入元素项的顺序。这样可以避免散列表中看起来随机的元素顺序。在散列表中插入元素项时，它们会加入一个双向链表中（见图 9-11）。

例如，考虑程序清单 9-6 中的以下映射插入操作：

var staff = new LinkedHashMap<String, Employee>();
staff.put("144-25-5464", new Employee("Amy Lee"));
staff.put("567-24-2546", new Employee("Harry Hacker"));
staff.put("157-62-7935", new Employee("Gary Cooper"));
staff.put("456-62-5527", new Employee("Francesca Cruz"));

然后，staff.keySet().iterator() 会以下面的顺序枚举键：

144-25-5464
567-24-2546
157-62-7935
456-62-5527

然后，staff.keySet().iterator() 会以下面的顺序枚举键：

Amy Lee
Harry Hacker
Gary Cooper
Francesca Cruz

或者，链接散列映射可以使用访问顺序（access order）而不是插入顺序来迭代处理映射条目。每次调用 get 或 put 时，受到影响的条目将从当前位置删除，并放在条目链表的末尾（只影响条目链表中的位置，而不影响散列表的桶）。一个映射条目总是在键散列码对应的桶中）。要构造这样一个散列映射，需要调用

LinkedHashMap<K, V>(initialCapacity, loadFactor, true)

访问顺序对于实现缓存的“最近最少使用”原则十分重要。例如，你可能希望将访问频率高的元素放在内存中，而从数据库读取访问频率低的元素。如果在映射表中没有找到某个元素，而且此时映射表已经很满，可以得到映射表的一个迭代器，并删除它枚举的前几个元素，它们是最近最少使用的几个元素。

甚至可以自动完成这一过程。构造 LinkedHashMap 的一个子类，然后覆盖下面这个方法：

protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > 100;
}

或者，还可以考虑 eldest 映射条目来决定是否将它删除。例如，可以检查随这个映射条目存储的一个时间戳。

9.4.6 枚举集与映射

EnumSet 是一个高效的集实现，其元素属于一个枚举类型。因为枚举类型只有有限个实例，所以 EnumSet 在内部实现为一个位序列。如果对应的值在集中出现，相应的位置为 1。

EnumSet 类没有公共构造器。要使用静态工厂方法构造这个集：

enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY }
EnumSet<Weekday> always = EnumSet.allOf(Weekday.class);
EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class);
EnumSet<Weekday> workday = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY);
EnumSet<Weekday> mf = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);

可以使用 Set 接口的常用方法来修改 EnumSet。

EnumMap 是一个映射，它的键属于一个枚举类型。EnumMap 可以简单高效地实现为一个值数组。需要在构造器中指定键类型：

var personInCharge = new EnumMap<Weekday, Employee>(Weekday.class);

注释：在 EnumSet 的 API 文档中，会看到形如 E extends EnumSet<E> 的奇怪的类型参数。简单地说，它的意思就是 “E 是一个枚举类型。” 所有枚举类型都扩展了这个类型 Enum 类。例如，Weekday 扩展了 Enum<Weekdays>。

9.4.7 标识散列映射

IdentityHashMap 有一个很特殊的用途。在这里，键的散列值不是用 hashCode 函数计算的，而是用 System.identityHashCode 方法计算的。Object.hashCode 根据对象的内存地址计算散列码时，就使用了这个方法。另外，对两个对象进行比较时，IdentityHashMap 使用了 ==，而不是 equals。也就是说，不同的键对象即使内容相同，也被视为不同的对象。在实现对象遍历算法（如对象串行化）时，如果你想跟踪哪些对象已经遍历过，这个类就很有用。

9.5 副本与视图

如果查看图 9-4 和图 9-5，可能会认为用如此多的接口和抽象类来实现数量并不多的具体集合类似乎没有太大必要。不过，这两个图并没有展示出全部。通过使用视图（view），可以得到其他实现了 Collection 接口或 Map 接口的对象。你已经见过使用映射类 keySet 方法的这样一个例子。初看起来，好像这个方法创建了一个新集，并填入映射中的所有键，然后返回这个集。但是，情况并非如此。实际上，keySet 方法返回一个实现了 Set 接口的类对象，这个类的方法可以操纵原映射。这种集合称为视图。

视图技术在集合框架中有许多非常有用的应用。下面几节将讨论这些应用。

9.5.1 小集合

Java 9 引入了一些静态方法，可以生成给定元素的集或列表，以及给定键/值对的映射。例如，

List<String> names = List.of("Peter", "Paul", "Mary");
Set<Integer> numbers = Set.of(2, 3, 5);

会分别生成包含 3 个元素的一个列表和一个集。对于映射，需要指定键和值，如下所示：

Map<String, Integer> scores = Map.of("Peter", 2, "Paul", 3, "Paul", 3, "Mary", 5);

元素、键或值不能为 null。集和映射键不能重复：

numbers = Set.of(13, null); // Error-null element
scores = Map.of("Peter", 4, "Peter", 2); // Error-duplicate key

警告：对于这些集和映射中的迭代顺序，并没有保证。实际上，会有意用每次虚拟机启动时随机得到的一个种子打乱这个顺序。来看看 jshell 的两次运行：

$ jshell> Set.of("Peter", "Paul", "Mary")
$1 => [Peter, Mary, Paul]
jshell> exit
$ jshell> Set.of("Peter", "Paul", "Mary")
$1 => [Paul, Mary, Peter]

有些 Java 程序员编写程序员编写程序时，其程序的正确性依赖于一个假设，即认为实现细节永远不会改变。这样会让实现类的程序员很难对实现很有用的修改。在这里，道理很明显，编写程序时不要对元素顺序做任何假设。

List 和 Set 接口有 11 个方法，分别有 0 到 10 个参数，另外还有一个参数个数可变的方法。提供这种特性是为了提高效率。

对于 Map 接口，则无法提供一个参数可变的版本，因为参数类型会交替为键类型和值类型。不过它有一个静态方法 ofEntries。能接受任意多个 Map.Entry<K, V> 对象（可以用静态方法 entry 创建这些对象）。例如，

import static java.util.Map.*;
Map.*;
Map<String, Integer> scores = ofEntries(
    entry("Peter", 2),
    entry("Paul", 3),
    entry("Mary", 5));

of 和 ofEntries 方法可以生成某些类的对象，这些类对于每个元素会有一个实例变量，或者有一个后备数组提供支持。

这些集合对象是不可修改的（unmodifiable）。如果试图改变它们的内容，会导致一个 UnsupportedOperationException 异常。

如果需要一个可更改的集合，可以把这个不可修改的集合传递到构造器：

var names = new ArrayList<>(list.of("Peter", "Paul", "Mary");

以下方法调用

Collections.nCopies(n, object)

会返回一个实现了 List 接口的不可变对象，给人一种错觉：就像有 n 个元素，每个元素看起来是一个 anObject。

例如，下面的调用将创建一个包含 100 个字符串的 List，每个值都设置为 "DEFAULT"：

List<String> settings = Collections.nCopies(100, "DEFAULT");

这样存储开销很小。对象只存储一次。

注释：of 方法是 Java 9 新引入的。之前有一个静态方法 Arrays.asList，它会返回一个可更改但是大小不可变的列表。也就是说，在这个列表上可以调用 set，但是不能使用 add 或 remove。另外还有遗留方法 Collections.emptySet 和 Collections.singletonList。

注释：Collections 类包含很多实用方法，这些方法的参数或返回值是集合。不要将它们与 Collection 接口混淆。

提示：Java 没有 Pair 类，有些程序员会使用 Map.Entry 作为对（pair），但这种做法并不好。在 Java 9 之前，这会很麻烦，你必须使用 new AbstractMap.SimpleImmutableEntry<first, second> 构造对象。不过现在可以调用 Map.entry(first, second)。

9.5.2 不可修改的副本和视图

为了建立一个集合的不可修改的副本（unmodifiable copy），可以使用集合类型的 copyOf 方法：

ArrayList<String> names = ...;
Set<String> nameSet = Set.copyOf(names); // The names as an unmodifiable set
List.copyOf(names); // The names as an unmodifiable list

每个 copyOf 方法会建立集合的一个副本。如果修改了原集合，这个副本不受影响。如果原集合恰好是不可修改的，而且类型正确，copyOf 则会直接返回原集合：

Set<String> names = Set.of("Peter", "Paul", "Mary");
Set<String> nameSet = Set.copyOf(names); // No need to make a copy: names == nameSet

Collections 类还有一些方法可以生成集合的不可修改的视图（unmodifiable view）。这些视图对现有集合增加了一个运行时检查。如果检测到试图修改不可修改的集合，就抛出一个异常。

可以使用下面 8 个方法来获得不可修改的视图：

Collections.unmodifiableCollection
Collections.unmodifiableList
Collections.unmodifiableSet
Collections.unmodifiableSortedSet
Collections.unmodifiableNavigableSet
Collections.unmodifiableMap
Collections.unmodifiableSortedMap
Collections.unmodifiableList

每个方法都定义为处理一个接口。例如，Collections.unmodifiableList 可以处理 ArrayList、LinkedList 或者实现了 List 接口的任何其他类。

例如，假设想要让你的某些代码查看（但不修改）一个集合的内容，可以如下实现：

var staff = new LinkedList();
// Collections.unmodifiableList(staff);
lookAt(Collections.unmodifiableList(staff));

Collections.unmodifiableList 方法将返回实现了 List 接口的一个类的对象。其访问器方法将从 staff 集合中获取值。当 lookAt 方法可以调用 List 接口中的所有方法，而不只是访问器但是所有的更改器方法（例如，add）已经重新定义为抛出一个 UnsupportedOperationException 异常，而不是将调用传递给底层集合。

不可修改的视图并不会让集合本身变为不可变。仍然可以通过集合的原始引用（在这里就是 staff 修改这个集合，并且仍然可以对集合的元素调用更改器方法。

因为视图只是包装了接口而不是具体的集合对象，所以只能访问图接口中定义的方法。例如，LinkedList 类有一些便利方法，如 addFirst 和 addLast，它们不是 List 接口的方法，不能通过不可修改的视图访问这些方法。

警告：unmodifiableCollection 方法（以及本节稍后讨论的 synchronizedCollection 和 checked Collection 方法）将返回一个集合，它的 equals 方法不调用底层集合的 equals 方法。实际上，它继承了 Object 类的 equals 方法，这个方法只是检测两个对象是否是同一个对象。如果将集或列表转换成集合，就再也无法检测其内容是否相同了。视图采用了这种工作方式，因为这个层次上的相等性检测没有明确定义。视图会以同样的方式处理 hashCode 方法。

不过，unmodifiableSet 和 unmodifiableList 方法会使用底层集合的 equals 方法和 hashCode 方法。

9.5.3 子范围

可以为很多集合建立子范围（subrange）视图。例如，假设有一个列表 staff，想从中取出第 10 个～第 19 个元素。可以使用 subList 方法来获得这个列表子范围的视图。

List<Employee> group2 = staff.subList(10, 20);

第一个索引包含在内，而不包含第二个索引。这与 String 类 substring 操作中的参数类似。可以对子范围应用任何操作，而且这些操作会自动反映到整个列表。例如，可以删除整个子范

group2.clear(); // staff reduction

这些元素会自动地从 staff 列表中清除，并且 group2 变为空。

对于有序集和映射，可以使用排序顺序而不是元素位置建立子范围。SortedSet 接口声明了 3 个方法：

SortedSet<E> subSet(E from, E to)
SortedSet<E to)
SortedSet<E> headSet(E to)
SortedSet<E> tailSet(E from)

这些方法将返回大于等于 from 且小于 to 的所有元素构成的子集。有序映射也有类似的方法：

SortedMap<K,V> subMap(K from, K to)
SortedMap<K,V> headMap(K to)
SortedMap<K,V> tailMap(K from)

这些方法会返回映射的视图，其中包含落在指定范围内的键相应的所有元素。

Java 6 引入的 NavigableSet 接口允许对这些子范围操作有更多控制。可以指定是否包括边界：

NavigableSet<E> subSet(E from, boolean fromInclusive, E to, boolean toInclusive)
NavigableSet<E> headSet(E to, boolean toInclusive)
NavigableSet<E> tailSet(E from, boolean fromInclusive)

9.5.4 检查型视图

检查型视图用来对泛型类型可能出现的问题提供调试支持。如同第 8 章中所述，实际上将错误类型的元素混入泛型集合中的情况极有可能发生。例如：

var strings = new ArrayList<String>();
ArrayList rawList = strings; // warning only, not an error,
rawList.add(new Date()); // now strings contains a Date object

这个错误的 add 命令在运行时检测不到。实际上，只有当另一部分代码调用 get 方法，并将结果强制转换为 String 时，才会出现一个类型转换异常。

检查型视图可以探测这类问题。下面定义了一个安全列表：

List<String> safeStrings = Collections.checkedList(strings, String.class);

这个视图的 add 方法将检查插入的对象是否属于给定的类。如果不属于给定的类，就立即抛出一个 ClassCastException。这样做的好处是会在正确的位置报告错误：

ArrayList rawList strings;
rawList.add(new Date()); // checked list throws a ClassCastException

警告：检查型视图受限于虚拟机可以完成的运行时检查。例如，对于 ArrayList<Pair<String>，就无法阻止插入 Pair<Date>，因为虚拟机有一个“原始” Pair 类。

9.5.5 同步视图

如果从多个线程访问集合，就必须确保集合不会被意外地破坏。例如，如果一个线程试图为散列表增加元素，同时另一个线程正在对元素进行遍历，其结果将是灾难性的。

类库的设计者使用视图机制确保常规集合是线程安全的，而没有实现线程安全的集合类。例如，Collections 类的 synchronizedMap 方法可以将任何一个映射转换成有同步访问方法的 Map：

HashMap<String,Employee>()

现在就可以从多线程访问这个 map 对象了。get 和 put 等方法是同步的，即每个方法调用必须完全结束，另一个线程才能调用另一个方法。

9.5.6 关于可选操作的说明

通常，视图有一些限制：可能只读，可能无法改变大小，或者可能只支持删除而不支持插入（如映射的键视图）。如果试图执行不恰当的操作，受限制的视图就会抛出一个 UnsupportedOperationException。

在集合和迭代器接口的 API 文档中，许多方法被描述为“可选操作”。这看起来与接口的概念有冲突。毕竟，接口的设计目的难道不就是明确一个类必须实现的方法吗？确实，从理论的角度看，这种安排不太令人满意。一个更好的解决方案是为只读视图和不能改变集合大小的视图建立单独的接口。不过，这将会使接口的数量增至原来的三倍，这让类库设计者无法接受。

是否应该将“可选”方法这一技术扩展到你自己的设计中呢？我们认为不应该。尽管集合被频繁地使用，但实现集合的编码方式未必适用于其他问题领域。集合类库的设计者必须解决一组极其严格而且相互冲突的需求。用户希望类库应该易于学习、使用方便、彻底泛型化、具有通用性，同时又与手写算法一样高效。要同时达到所有这些目标，或者甚至尽量兼顾所有目标都是不可能的。但是，在你自己的编程问题中，很少遇到这种极端的约束。你应该能够找到合适的解决方案，而不必依赖“可选”接口操作这种极端做法。

9.6 算法

除了实现集合类，Java 集合框架还提供了一些有用的算法。在下面的小节中，你会了解如何使用这些算法，以及如何编写适用于集合框架的你自己的算法。

9.6.1 为什么使用泛型算法

泛型集合接口有一个很大的优点，即算法只需要实现一次。例如，考虑计算集合中最大元素的一个简单算法。使用传统方式，程序设计人员可能会用循环实现这个算法。可以如下找出数组中最大的元素：

if (a.length == 0) throw new NoSuchElementException();
T largest = a[0];
for (int i = 1; i < a.length; i++)
    if (largest.compareTo(a[i]) < 0)
        largest = a[i];

当然，要找出数组列表中的最大元素，编写的代码会稍有差别：

if (v.size() == 0) throw new NoSuchElementException();
T largest = v.get(0);
for (int i = 1; i < v.size(); i++)
    if (largest.compareTo(v.get(i)) < 0)
        largest = v.get(i);

链表呢？链表没有高效的随机访问操作，不过可以使用迭代器：

if (l.isEmpty()) throw new NoSuchElementException();
Iterator<T> iter = l.iterator();
T largest = iter.next();
while (iter.hasNext()) {
    T next = iter.next();
    if (largest.compareTo(next) < 0)
        largest = next;
}

编写这些循环很烦，而且比较容易出错。是否存在“差 1”错误（off-by-one error）？这些循环对于空容器能正常工作吗？对于只含有一个元素的容器又会发生什么情况呢？我们不希望每次都测试和调试这些代码，也不想实现如下的一系列方法：

static <T extends Comparable> T max(T[] a)
static <T extends Comparable> T max(ArrayList<T> v)
static <T extends Comparable> T max(LinkedList<T> l)

这里就可以使用集合接口。请考虑为了高效地执行这个算法所需要的最小集合接口。使用 get 和 set 方法的随机访问要比直接迭代的层次高。在计算链表中最大元素的过程中已经看到，这项任务并不需要随机访问。可以直接迭代处理元素来得出最大元素。因此，可以将 max 方法实现为能够接收任何实现了 Collection 接口的对象：

public static <T extends Comparable> T max(Collection<T> c) {
    if (c.isEmpty()) throw new NoSuchElementException();
    Iterator<T> iter = c.iterator();
    T largest = iter.next();
    while (iter.hasNext()) {
        T next = iter.next();
        if (largest.compareTo(next) < 0)
            largest = next;
    }
    return largest;
}

现在就可以使用一个方法来计算链表、数组列表或数组中的最大元素了。

这是一个功能很强大的概念。事实上，标准 C++ 类库有几十个有用的算法，每个算法都可以处理泛型集合。Java 类库中的算法没有那么丰富，但是确实包含了一些基本的算法：排序、二分查找和一些实用算法。

9.6.2 排序与混排

计算机行业的前辈们有时会回忆起他们当年不得不使用穿孔卡片以及手动编写排序算法的情形。当然，如今排序算法已经成为大多数编程语言标准库中的一个组成部分，Java 程序设计语言也不例外。

Collections 类中的 sort 方法可以对实现了 List 接口的集合进行排序：

var staff = new LinkedList<String>();
// fill collection
Collections.sort(staff);

这个方法假定列表元素实现了 Comparable 接口。如果想采用其他方式对列表进行排序，可以使用 List 接口的 sort 方法并传入一个 Comparator 对象。可以如下按工资对一个员工列表排序：

staff.sort(Comparator.comparingDouble(Employee::getSalary));

如果想按照降序对列表进行排序，可以使用静态的便利方法 Collections.reverseOrder()。这个方法将返回一个比较器，这个比较器将返回 b.compareTo(a)。例如：

staff.sort(Comparator.reverseOrder());

这个方法将根据元素类型的 compareTo 方法所给定的排序顺序，按逆序对列表 staff 中的元素进行排序。同样地：

staff.sort(Comparator.comparingDouble(Employee::getSalary).reversed());

将按工资逆序排序。

你可能会对 sort 方法如何对列表进行排序感到好奇。通常，在查看有关算法书籍中的排序算法时，会发觉介绍的都是有关数组的排序算法，而且使用的是随机访问方式。但是，链表的随机访问效率很低。实际上，可以使用一种归并排序对链表高效地排序。不过，Java 程序设计语言中的实现并不是这样做的。它只是将所有元素都放在一个数组，对这个数组进行排序，然后再将排序后的序列复制回列表。

集合类库中使用的排序算法比快速排序（QuickSort）要慢一些，快速排序是一种传统的通用排序算法选择。不过，集合类库中使用的排序算法有一个主要的优点：它是稳定的，也就是说，它不会改变相等元素的顺序。为什么要关注相等元素的顺序呢？下面来看一种常见的情况。假设有一个已经按照姓名排序的员工列表。现在，要按照工资再进行排序。如果两个员工的工资相等会发生什么情况？如果采用稳定的排序算法，将会保留按名字排序的顺序。换句话说，排序的结果是得到一个首先按照工资排序再按照姓名排序的列表。

集合不需要实现所有的“可选”方法，因此，所有接受集合参数的方法必须描述什么时候可以安全地将集合传递给算法。例如，显然不能将 unmodifiableList 列表传递给 sort 算法。那么，可以传递什么类型的列表呢？根据文档说明，列表必须是可修改的，但不一定可以改变大小。下面是有关的术语定义：

• 如果列表支持 set 方法，这个列表则是可修改的（modifiable）。
• 如果列表支持 add 和 remove 方法，这个列表则是可改变大小的（resizable）。

Collections 类有一个算法 shuffle，其功能与排序刚好相反，它会随机地混排列表中元素的顺序。例如：

ArrayList<Card> cards = ...;
Collections.shuffle(cards);

如果提供的列表没有实现 RandomAccess 接口，shuffle 方法会将元素复制到数组中，然后打乱数组元素的顺序，最后再将打乱顺序后的元素复制回列表。

程序清单 9-7 中的程序用 1～49 之间的 49 个 Integer 对象填充数组。然后，随机地混排列表，并从混排后的列表中选择前 6 个值。最后再将选择的数值进行排序并打印。

9.6.3 二分查找

要想在数组中查找一个对象，通常要依次访问数组中的每个元素，直到找到匹配的元素。不过，如果数组是有序的，可以检查中间的元素，查看是否大于要查找的元素。如果是，就在数组的前半部分继续查找；否则，在数组的后半部分继续查找。这样就可以将问题规模缩减一半，并以同样的方式继续下去。例如，如果数组中有 1024 个元素，那么 10 步之后就能找到匹配（或者可以确认数组中不存在这个元素），而线性查找平均需要 512 步（如果元素存在）；倘若元素不存在，需要 1024 步才能够确认。

Collections 类的 binarySearch 方法实现了这个算法。注意，集合必须是有序的，否则算法会返回错误的答案。要想查找某个元素，必须提供集合（这个集合要实现 List 接口，下面还会更加详细地介绍这个问题）以及要查找的元素。如果集合没有采用 Comparable 接口的 compareTo 方法进行排序，那么还要提供一个比较器对象。

i = Collections.binarySearch(c, element);
i = Collections.binarySearch(c, element, comparator);

如果 binarySearch 方法返回一个非负的值，这表示匹配对象的索引。也就是说，c.get(i) 等于在这个比较顺序下的 element。如果返回负值，则表示没有匹配的元素。不过，可以利用这个返回值来计算应该将 element 插入集合的哪个位置，以保持集合的有序性。插入的位置是：

insertionPoint = -i - 1;

而不是简单的 i，因为 0 值有二义性。也就是说，下面这个操作：

if (i < 0)
    c.add(-i - 1, element);

将把元素插入正确的位置。

只有采用随机访问方式，二分查找才有意义。如果必须依次查找链表的一半元素来找到中间元素，就会完全失去二分查找的优势。因此，如果为 binarySearch 算法提供了一个链表，它将退化为线性查找。

9.6.4 简单算法

Collections 类中包含几个简单但很有用的算法。这一节最前面介绍的例子就是这样一个算法，即查找集合中的最大元素。其他算法还包括：将一个列表中的元素复制到另外一个列表中；用一个常量值填充容器；逆置一个列表的元素顺序。

为什么在标准类库中提供这些简单算法呢？大多数程序员肯定都能很容易地采用简单的循环实现这些任务。我们之所以喜欢这些算法，是因为它们可以让程序员更轻松地读懂代码。当阅读别人实现的一个循环时，必须揣摩编程者的意图。例如，请看下面这个循环：

for (int i = 0; i < words.size(); i++)
    if (words.get(i).equals("C++")) words.set(i, "Java");

现在将这个循环与以下调用进行比较：

Collections.replaceAll(words, "C++", "Java");

看到这个方法调用时，你马上就能知道这个代码要做什么。

本节最后的 API 注释描述了 Collections 类中的简单算法。

默认方法 Collection.removeIf 和 List.replaceAll 稍有些复杂。要提供一个 lambda 表达式来测试或转换元素。例如，下面的代码将删除所有短单词，并把其余单词改为小写：

words.removeIf(w -> w.length() <= 3);
words.replaceAll(String::toLowerCase);

9.6.5 批操作

很多操作会“成批”复制或删除元素。以下调用：

coll1.removeAll(coll2);

将从 coll1 中删除 coll2 中出现的所有元素。与之相反：

coll1.retainAll(coll2);

会从 coll1 中删除所有未在 coll2 中出现的元素。

下面是一个典型的应用。假设希望找出两个集的交集（intersection），也就是两个集中共有的元素。首先，建立一个新集来存放结果：

var result = new HashSet<String>(firstSet);

在这里，我们利用了一个事实：每一个集合都有这样一个构造器，其参数是包含初始值的另一个集合。

现在来使用 retainAll 方法：

result.retainAll(secondSet);

这会保留两个集中都出现的所有元素。这样就构成了交集，而无须编写循环。

可以按这个思路更进一步，对视图应用一个批操作。例如，假设有一个映射，将员工 ID 映射到员工对象，另外有一个集包含不再聘用的所有员工的 ID：

Map<String, Employee> staffMap = ...;
Set<String> terminatedIDs = ...;

只需要建立一个键集，并删除终止聘用关系的所有员工的 ID：

staffMap.keySet().removeAll(terminatedIDs);

因为键集是映射的一个视图，所以键和相关联的员工名会自动从映射中删除。

通过使用子范围视图，可以限制批操作仅应用于子列表和子集。例如，假设希望把一个列表的前 10 个元素增加到另一个容器，可以建立一个子列表选出前 10 个元素：

relocated.addAll(staff.subList(0, 10));

这个子范围还可以完成更改操作：

staff.subList(0, 10).clear();

9.6.6 集合与数组的转换

因为 Java 平台 API 的大部分内容都是在集合框架创建之前设计的，所以有时候需要在传统数组和更现代的集合之间进行转换。

如果需要把一个数组转换为集合，List.of 包装器可以达到这个目的。例如：

String[] names = ...;
List<String> staff = List.of(names);

从集合得到数组会更困难一些。当然，可以使用 toArray 方法：

Object[] names = staff.toArray();

不过，这样做的结果是一个对象数组。尽管你知道集合中包含的是一个特定类型的对象，但不能使用强制类型转换：

String[] names = (String[]) staff.toArray(); // ERROR

toArray 方法返回的数组创建为一个 Object[] 数组，不能改变它的类型。实际上，要向 toArray 方法传入一个数组构造器表达式。这样一来，返回的数组就会有正确的数组类型：

String[] values = staff.toArray(String[]::new);

自注释：在 JDK 11 之前，必须使用另一种形式的 toArray 方法，要传入有正确类型的数组：

String[] values = staff.toArray(new String[0]);

这个 toArray 方法会构造有相同类型的另一个数组。或者，如果数组足够长，则会重用原数组：

staff.toArray(new String[staff.size()]);

这种情况下，不会创建新数组。

9.6.7 编写自己的算法

如果编写自己的算法（实际上，或者是以一个集合作为参数的任何方法），应该尽可能使用接口，而不要使用具体的实现。例如，假设你想处理集合元素。当然，可以实现类似下面的方法：

public void processItems(ArrayList<Item> items) {
    for (Item item : items)
        do something with item
}

但是，这样会限制方法的调用者，即调用者必须在 ArrayList 中提供元素。如果这些元素正好在另一个集合中，首先必须对它们重新包装，因此，最好接受一个更加通用的集合。

要问自己：完成这项工作的最通用的集合接口是什么？你关心顺序吗？如果顺序很重要，就应当接受 List。不过，如果顺序不重要，那么可以接受任意类型的集合：

public void processItems(Collection<Item> items) {
    for (Item item : items)
        do something with item
}

现在，任何人都可以用 ArrayList 或 LinkedList（甚至用 List.of 方法调用包装的数组）调用这个方法。

提示：在这里，甚至还可以做得更好：可以接受一个 Iterable<Item>。Iterable 接口有一个抽象方法 iterator，增强的 for 循环在底层就使用了这个方法。Collection 接口扩展了 Iterable。

反过来，如果你的方法返回多个元素，你肯定不希望限制将来的改进。例如，考虑下面的代码：

public ArrayList<Item> lookupItems(...) {
    var result = new ArrayList<Item>();
    return result;
}

这个方法承诺返回一个 ArrayList，尽管调用者并不关心它是什么类型的列表。如果你返回一个 List，任何时候都可以增加一个分支，通过调用 List.of 返回一个空列表或单例列表。

注释：既然将集合接口作为方法参数和返回类型是个很好的想法，为什么 Java 类库不一致地遵循这个规则呢？例如，JComboBox 有两个构造器：

JComboBox(Object[] items)
JComboBox(Vector<?> items)

之所以没有这样做，原因很简单：时间问题。Swing 类库是在集合类库之前创建的。

9.7 遗留的集合

从 Java 第 1 版问世以来，在集合框架出现之前已经存在大量“遗留的”容器类。

这些类已经集成到集合框架中，如图 9-12 所示。下面各节将简要介绍这些遗留的集合类。

9.7.1 Hashtable 类

经典的 Hashtable 类与 HashMap 类的作用一样，实际上，接口也基本相同。类似 Vector 类的方法，Hashtable 方法也是同步的。如果不需要与遗留代码的兼容性，就应该使用 HashMap。如果需要并发访问，则要使用 ConcurrentHashMap，参见第 12 章。

9.7.2 枚举

遗留的集合使用 Enumeration 接口遍历元素序列。Enumeration 接口有两个方法：hasMoreElements 和 nextElement。这两个方法完全类似于 Iterator 接口的 hasNext 方法和 next 方法。

如果发现遗留的类实现了这个接口，可以使用 Collections.list 将元素收集到一个 ArrayList 中。例如，LogManager 类只想将登录者的名字提供为一个 Enumeration。可以如下得到所有登录者的名字：

ArrayList<String> loggerNames = Collections.list(LogManager.getLoggerNames());

或者，在 Java 9 中，可以把一个枚举转换为一个迭代器：

LogManager.getLoggerNames().asIterator()
    .forEachRemaining(n -> { ... });

有时还会遇到希望得到一个枚举参数的遗留方法。静态方法 Collections.enumeration 将生成一个枚举对象，它会枚举集合中的元素。例如：

List<InputStream> streams = ...;
var in = new SequenceInputStream(Collections.enumeration(streams));
// the SequenceInputStream constructor expects an enumeration

注释：在 C++ 中，用迭代器作为参数十分普遍。幸好，在 Java 平台上，只有极少的程序员沿用这种习惯。传递集合要比传递迭代器更为明智。集合对象的用途更大。如果需要，接受者总能从集合获得迭代器，而且，还可以随时使用集合的所有方法。不过，你可能会在某些遗留代码中发现枚举，因为在 Java 1.2 的集合框架出现之前，这是唯一可以使用的泛型集合机制。

9.7.3 属性映射

属性映射（property map）是一个特殊类型的映射结构。它有下面 3 个特性：

• 键与值都是字符串。
• 这个映射可以很容易地保存到文件以及从文件加载。
• 有一个二级表存放默认值。

实现属性映射的 Java 平台类名为 Properties。属性映射对于指定程序的配置选项很有用。例如：

var settings = new Properties();
settings.setProperty("width", "600.0");
settings.setProperty("filename", "/home/cay/books/cj12/code/viche9/raven.html");

可以使用 store 方法将属性映射列表保存到一个文件中。在这里，我们将属性映射保存在文件 program.properties 中。第二个参数是包含在这个文件中的一个注释：

var out = new FileWriter("program.properties", StandardCharsets.UTF_8);
settings.store(out, "Program Properties");

这个示例会给出以下输出：

#Program Properties
#Sun Dec 31 12:54:19 PST 2017
top=227.0
left=1286.0
width=423.0
height=547.0
filename=/home/cay/books/cj12/code/v1che9/raven.html

要从文件加载属性，可以使用以下调用：

var in = new FileReader("program.properties", StandardCharsets.UTF_8);
settings.load(in);

警告：如果使用 load 和 store 方法时提供了输入/输出流，则会使用古老的 ISO 8859-1 字符编码。>U+00FF 的字符会保存为 Unicode 转义字符。对于 UTF-8，要像以上代码一样使用读取器/书写器。

System.getProperties() 方法会生成一个 Properties 对象来描述系统信息。例如，主目录包含键 "user.home"。可以用 getProperty() 方法读取这个信息，它将这个键对应的信息作为一个字符串返回：

String userDir = System.getProperty("user.home");

警告：出于历史原因，Properties 类实现了 Map<Object, Object>。因此，可以使用 Map 接口的 get 和 put 方法。不过，get 方法返回类型为 Object，而 put 方法允许插入任意的对象。所以最好坚持使用处理字符串而不是对象的 getProperty 和 setProperty 方法。

要得到虚拟机的 Java 版本，可以查找 "java.version" 属性。你会得到一个诸如 "17.0.1" 的字符串（不过，Java 8 之前的形式为 "1.8.0")。

提示：可以看到，Java 9 中版本编号发生了变化。这个看起来很小的改变却让大量依赖于老版本格式的工具无法正常工作。如果要解析版本字符串，一定要好好看看 JEP 322（http://openjdk.java.net/jeps/322），了解将来（至少是版本编号机制再次改变之前）版本字符串会采用怎样的格式。

Properties 类有两种提供默认值的机制。第一种方法是，只要查找一个字符串的值，可以指定一个默认值，当查找的键不存在时就会自动使用这个默认值：

String filename = settings.getProperty("filename", "");

如果属性映射中有一个 "filename" 属性，filename 就会设置为相应的字符串。否则，filename 会设置为空串。

如果觉得在每个 getProperty 调用中指定默认值太麻烦，可以把所有默认值都放在一个二级属性映射中，并在主属性映射的构造器中提供这个二级映射。

var defaultSettings = new Properties();
defaultSettings.setProperty("width", "600");
defaultSettings.setProperty("height", "400");
defaultSettings.setProperty("filename", "");

var settings = new Properties(defaultSettings);

没错，如果为 defaultSettings 构造器提供另一个属性映射参数，甚至可以为默认值指定默认值，不过一般不会这么做。

本书随附代码提供了一个示例程序，展示了如何使用属性存储和加载程序状态。这个程序使用第 2 章的 ImageViewer 程序，可以记住窗口位置、大小和最后加载的文件。运行这个程序，加载一个文件，然后移动窗口和调整窗口大小。再关闭程序，然后重新打开，看它是否记住了你的文件和你喜欢的窗口配置。还可以手动编辑主目录中的 corejava/ImageViewer.properties 文件。

属性是没有层次结构的简单表格。通常会用类似 window.main.color、window.main.title 等键名引入一个假想的层次结构。不过 Properties 类没有方法来帮助组织这样一个层次结构。如果要存储复杂的配置信息，就应该改为使用 Preferences 类，参见第 10 章的介绍。

9.7.4 栈

从 1.0 版开始，标准类库中就包含了 Stack 类，其中有大家熟悉的 push 方法和 pop 方法。但是，Stack 类扩展了 Vector 类，从理论角度看，Vector 类并不太令人满意，对于 Vector，你甚至可以使用并非栈操作的 insert 和 remove 方法在任何位置插入和删除值，而不只是在栈顶。

9.7.5 位集

Java 平台的 BitSet 类会存储一个位序列（它不是数学意义上的集，如果称为位向量（bit vector）或位数组（bit array）可能更为合适）。如果需要高效地存储一个位序列（例如，标志），就可以使用位集。由于位集将位包装在字节里，因此使用位集要比使用 Boolean 对象的 ArrayList 高效得多。

BitSet 类提供了一个用于读取、设置或重置各个位的很方便的接口。使用这个接口可以避免掩码和其他调整位的操作，如果将位存储在 int 或 long 变量中就必须做这些烦琐的操作。

例如，对于一个名为 bucketOfBits 的 BitSet：

bucketOfBits.get(i)

如果第 i 位处于“开”状态，就返回 true；否则返回 false。类似地：

bucketOfBits.set(i)

将第 i 位置为“开”。最后：

bucketOfBits.clear(i)

将第 i 位置为“关”。

作为位集应用的一个示例，这里给出一个“埃拉托色尼筛选法”算法的实现，这个算法用来查找素数（素数是指只能被 1 和本身整除的数，例如 2、3 或 5，“埃拉托色尼筛选法”是最早发现的用来枚举这些基本素数的方法之一）。这并不是查找素数的一种非常好的方法，但是由于某些原因，它已经成为测试编译器性能的一种流行的基准（这也不是一个很好的测试基准，因为它主要用于测试位操作）。

在此，我们要向传统致敬，给出这个算法的一个实现。这个程序将计算 2～2 000 000 之间的所有素数（一共有 148 933 个素数，所以你可能不希望把它们全部打印出来）。

这里并不想深入程序的细节，关键是要遍历一个包含 200 万个位的位集。首先将所有的位“打开”，然后将已知素数的倍数所对应的位都置为“关”。经过这个操作后保留下来的位对应的就是素数。程序清单 9-8 是用 Java 程序设计语言实现的程序，程序清单 9-9 是用 C++ 实现的代码。

注释：尽管这个筛选法并不是一种好的测试基准，不过我还是利用它测试了这个算法两个实现的运行时间。下面是在 Intel i5-8265U 处理器和 16 GB 内存（运行 Ubuntu 20.04）条件下的运行时间结果：

● C++（g++ 9.3.0）：115 毫秒

● Java（Java 17）：31 毫秒

我们已经对《Java 核心技术》的 11 个版本进行了这项测试，在最近的 7 个版本中，Java 轻松地战胜了 C++。公平地说，如果提高 C++ 编译器的优化级别，会比 Java 快 14 毫秒。只有当程序运行的时间长到触发 HotSpot 即时编译器时，Java 才能与之相当。