九、探索集合框架

应用通常必须管理对象集合。尽管您可以为此使用数组，但它们并不总是一个好的选择。例如，数组有固定的大小，当您需要存储可变数量的对象时，很难确定最佳大小。此外，数组只能由整数索引，这使得它们不适合将任意对象映射到其他对象。

标准类库提供了集合框架和遗留工具 API 来代表应用管理集合。在第 9 章中，我首先介绍这个框架，然后向你介绍这些遗留 API(以防你在遗留代码中遇到它们)。您会发现，一些遗留的 API 仍然有用。

注意 Java 的并发工具 API 套件(在第 10 章中讨论)扩展了集合框架。

探索集合框架基础

集合框架是一组类型(主要位于 java.util 包中)，提供了一个标准架构来表示和操作集合，集合是存储在为此目的而设计的类实例中的对象组。该框架的架构分为三个部分:

• 核心接口 :框架提供了核心接口，用于独立于集合的实现来操作集合。
• 实现类 :框架提供了提供不同核心接口实现的类，以解决性能和其他需求。
• 工具类 :框架为工具类提供了排序数组、获得同步集合等方法。

核心接口包括 java.lang.Iterable 、集合、列表、集合、分类集合、导航集合、队列、队列、地图、分类地图、导航地图。集合扩展可迭代；列表、集合，以及队列各自扩展集合；分类设置扩展设置；可导航集合扩展分类集合；队列延伸队列； SortedMap 扩展 Map；导航地图扩展分类地图。

图 9-1 展示了核心接口的层次结构(箭头指向父接口)。

图 9-1 集合框架基于核心接口的层次结构

框架的实现类包括 ArrayList ， LinkedList ， TreeSet ， HashSet ， LinkedHashSet ， EnumSet ， PriorityQueue ， ArrayDeque ， TreeMap ， HashMap ，linked has 每个具体类的名称都以核心接口名称结尾，标识它所基于的核心接口。

注意额外的实现类是并发工具的一部分。

框架的实现类还包括抽象的 AbstractCollection 、 AbstractList 、 AbstractSequentialList 、 AbstractSet 、 AbstractQueue 和 AbstractMap 类。这些类提供了核心接口的框架实现，以便于创建具体的实现类。

最后，框架提供了两个工具类:数组和集合。

可比与比较

集合实现以某种顺序(排列)存储其元素。这个顺序可能是无序的，也可能是根据某种标准(如字母、数字或时间)排序的。

一个排序的集合实现默认按照它们的自然排序 来存储它的元素。比如 java.lang.String 对象的自然排序是字典序或者字典序(也称字母顺序)。

集合不能依靠 equals() 来指定自然排序，因为这种方法只能确定两个元素是否等价。相反，元素类必须实现 Java . lang . comparable接口及其 int compareTo(T o) 方法。

注意根据可比的基于 Oracle 的 Java 文档，这个接口被认为是集合框架的一部分，尽管它是 java.lang 包的成员。

已排序的集合使用 compareTo() 来确定该方法的元素参数 o 在集合中的自然排序。 compareTo() 将参数 o 与当前元素(调用了 compareTo() 的元素)进行比较，并执行以下操作:

• 当当前元素应该在或之前时，它返回一个负值。
• 当当前元素和 o 相同时，返回零值。
• 当当前元素应该在或之后时，它返回一个正值。

当你需要实现 Comparable 的 compareTo() 方法时，有一些规则你必须遵守。下面列出的这些规则类似于第 4 章中所示的用于实现 equals() 方法的规则:

• compareTo() 必须是自反的:对于任何非空的参考值 x ， x 。compare to(x)必须返回 0。
• compareTo() 必须对称:对于任何非空参考值 x 和 y ， x 。compare to(y)= =-y。compare to(x)必须持有。
• compareTo() 必须是可传递的:对于任何非空的参考值 x 、 y 、 z ，如果 x 。compare to(y)>0 为真，若 y 。compare to(z)>0 为真，则 x 。compare to(z)>0 也必须为真。

另外， compareTo() 应该在将空引用传递给这个方法时抛出 Java . lang . nullpointerexception。但是，您不需要检查 null，因为当这个方法试图访问一个 null 引用的不存在的成员时，它会抛出 NullPointerException 。

注意在 Java 5 及其引入泛型之前， compareTo() 的参数是类型 java.lang.Object 的，在进行比较之前必须转换成适当的类型。当参数的类型与转换不兼容时，转换操作符将抛出一个 Java . lang . classcastexception 实例。

您可能偶尔需要在集合中存储以不同于自然顺序的某种顺序排序的对象。在这种情况下，您需要提供一个比较器来提供这种排序。一个比较器是一个对象，它的类实现了比较器接口。该接口的泛型类型为比较器T5】，提供了以下一对方法:

• int compare(T o1，T o2) 比较两个参数的顺序。该方法在 o1 等于 o2 时返回 0，在 o1 小于 o2 时返回负值，在 o1 大于 o2 时返回正值。
• boolean equals(Object o) 当 o “等于”这个比较器时返回 true，因为 o 也是一个比较器，并采用相同的排序。否则，此方法返回 false。

注意 比较器声明等于()，因为这个接口在这个方法的契约上加了一个额外的条件。此外，只有当指定的对象也是一个比较器，并且与该比较器采用相同的排序时，该方法才能返回 true。您不必覆盖 equals() ，但是这样做可以通过允许程序确定两个不同的比较器施加相同的顺序来提高性能。

第 6 章提供了一个说明实现可比的例子，在本章的后面你会发现另一个例子。此外，在这一章中，我将介绍实现比较器的例子。

可迭代和集合

大部分核心接口都植根于 Iterable 及其集合子接口。它们的泛型分别是 IterableT5】和 CollectionT7】。

Iterable 描述了能够以某种顺序 e 返回其包含对象的任何对象。该接口声明了一个迭代器< T >迭代器()方法，该方法返回一个迭代器实例，用于迭代所有包含对象。

集合表示被称为元素的对象集合。该接口提供了许多集合所基于的集合子接口所共有的方法。表 9-1 描述了这些方法。

表 9-1 。收集方法

表 9-1 揭示了各种收集方法的三个例外。首先，一些方法可以抛出 UnsupportedOperationException 类的实例。例如，当您试图将一个对象添加到一个不可变(不可修改)集合中时， add() 抛出 UnsupportedOperationException(将在本章后面讨论)。

其次，集合的一些方法可以抛出类的实例。例如， remove() 抛出 ClassCastException 当您试图从一个基于树的映射中删除一个条目(也称为映射)时，该映射的键是 String s，但却指定了一个非 String 键。

最后，集合的 add() 和 addAll() 方法抛出 IllegalArgumentException 实例，当要添加的元素的某个属性 (attribute)阻止它被添加到这个集合时。例如，第三方集合类的 add() 和 addAll() 方法可能会在检测到负的整数值时抛出这个异常。

注意也许你想知道为什么 remove() 被声明为接受任何对象参数，而不是只接受那些类型是集合类型的对象。换句话说，为什么 remove() 没有声明为布尔 remove(E e) ？另外，为什么 containsAll() 、 removeAll() 和 retainAll() 没有用类型为集合<的参数声明？扩展 E > 以确保集合参数只包含与调用这些方法的集合相同类型的元素。这些问题的答案是需要保持向后兼容性。集合框架是在 Java 5 及其泛型引入之前引入的。为了让版本 5 之前编写的遗留代码继续编译，这四个方法被声明为具有较弱的类型约束。

迭代器和增强的 For 循环语句

通过扩展 Iterable , 集合继承了该接口的 iterator() 方法，这使得迭代集合成为可能。 iterator() 返回一个类的实例，该类实现了 Iterator 接口，其泛型类型表示为 Iterator < E > ，并声明了以下三个方法:

• 布尔 hasNext() 当这个迭代器实例有更多元素要返回时，返回 true 否则，此方法返回 false。
• E next() 返回集合中与这个迭代器实例相关联的下一个元素，或者当没有更多的元素要返回时抛出 NoSuchElementException 。
• void remove() 从与此迭代器实例关联的集合中删除 next() 返回的最后一个元素。每次调用 next() 时，该方法只能被调用一次。当在迭代过程中以除调用 remove() 之外的任何方式修改底层集合时，未指定迭代器实例的行为。当此迭代器不支持此方法时，此方法抛出 UnsupportedOperationException，当 remove() 已被调用而之前没有调用 next() 时，或者当多个 remove() 调用发生而中间没有 next() 调用时，此方法抛出 IllegalStateException 。

以下示例向您展示了如何在调用迭代器()返回一个迭代器实例后迭代一个集合:

Collection<String> col = . . . // This code doesn't compile because of the . . .
// Add elements to col.
Iterator iter = col.iterator();
while (iter.hasNext())
   System.out.println(iter.next());

while 循环反复调用迭代器的 hasNext() 方法来确定迭代是否应该继续，以及(如果应该继续)调用 next() 方法来返回相关集合中的下一个元素。

因为这种习惯用法很常用，所以 Java 5 在 for 循环语句中引入了语法糖，以简化这种习惯用法的迭代。这种糖使该语句看起来像在 Perl 等语言中发现的 foreach 语句，并在下面简化的上一个示例中显示出来:

Collection<String> col = . . . // This code doesn't compile because of the . . .
// Add elements to col.
for (String s: col)
   System.out.println(s);

这个 sugar 隐藏了 col.iterator() ，这个方法调用返回一个迭代器实例，用于迭代 col 的元素。它还隐藏了对这个实例上的迭代器的 hasNext() 和 next() 方法的调用。您将该糖解释为如下内容:“对于列中的每个字符串对象，在循环迭代开始时将该对象分配给 s ”

注意增强的 for 循环语句在隐藏数组索引变量的数组上下文中也很有用。考虑以下示例:

String[]动词= {“跑”、“走”、“跳”}；for(字符串动词:verbs) System.out.println(动词)；

该示例的内容为“对于动词数组中的每个字符串对象，在循环迭代开始时将该对象分配给动词”,该示例相当于以下示例:

String[]动词= {“跑”、“走”、“跳”}；for(int I = 0；我<动词不定式；i++) System.out.println(动词[I])；

增强的 for 循环语句的局限性在于，在需要访问迭代器来从集合中移除元素的情况下，不能使用该语句。此外，在遍历过程中必须替换集合/数组中的元素时，它是不可用的；它不能用于必须并行迭代多个集合或数组的情况。

汽车尾气与无毒〔t0〕

认为 Java 应该只支持引用类型的开发人员抱怨过 Java 对基本类型的支持。Java 类型系统二分法的一个明显体现是集合框架:可以在集合中存储对象，但不能存储基于原始类型的值。

虽然您不能在集合中直接存储基于基元类型的值，但是您可以通过首先将该值包装在从基元类型包装类(如 Integer )创建的对象中，然后将该基元类型包装类实例存储在集合中来间接存储该值——参见以下示例:

Collection<Integer> col = . . .; // This code doesn't compile because of the . . .
int x = 27;
col.add(new Integer(x)); // Indirectly store int value 27 via an Integer object.

反过来的情况也是繁琐的。当您想要从列中检索 int 时，您必须调用 Integer 的 intValue() 方法(如果您还记得的话，该方法是从 Integer 的 java.lang.Number 超类继承而来的)。继续这个例子，您可以指定 int y = col.iterator()。下一个()。int value()；将存储的 32 位整数赋值给 y 。

为了减轻这种乏味，Java 5 引入了自动装箱和取消装箱，这是一对互补的基于糖的语法语言特性，使原始类型的值看起来更像对象。(这个“戏法”并不完整，因为您不能指定像 27.doubleValue() 这样的表达式。)

自动装箱自动装箱(包装)适当的原始类型包装类的对象中的原始类型值，只要指定了原始类型值但需要引用。例如，您可以将示例的第三行改为 col . add(x)；并让编译器将 box x 转换成一个整数对象。

取消装箱自动取消装箱(展开)每当指定了引用但需要原始类型值时，从其包装对象中取消原始类型值。例如，您可以指定 int y = col.iterator()。next()；并让编译器在赋值前将返回的整数对象解装箱为 int 值 27。

虽然引入自动装箱和取消装箱是为了简化在集合上下文中使用基元类型值，但是这些语言特性也可以在其他上下文中使用；这种任意使用会导致一个问题，如果不知道幕后发生了什么，这个问题就很难理解。考虑以下示例:

Integer i1 = 127;
Integer i2 = 127;
System.out.println(i1 == i2); // Output: true
System.out.println(i1 < i2); // Output: false
System.out.println(i1 > i2); // Output: false
System.out.println(i1 + i2); // Output: 254
i1 = 30000;
i2 = 30000;
System.out.println( i1 == i2 ); // Output: false
System.out.println(i1 < i2); // Output: false
System.out.println(i1 > i2); // Output: false
i2 = 30001;
System.out.println(i1 < i2); // Output: true
System.out.println(i1 + i2); // Output: 60001

除了一个例外，这个例子的输出和预期的一样。例外情况是 i1 == i2 比较，其中 i1 和 i2 都包含 30000。不像 i1 和 i2 都包含 127 的情况那样返回 true， i1 == i2 返回 false。是什么导致了这个问题？

检查生成的代码，你会发现整数 i1 = 127 转换为整数 i1 = Integer . value of(127)；和整数 i2 = 127 转换为整数 I2 = Integer . value of(127)；。根据 valueOf() 的 Java 文档，这种方法利用缓存来提高性能。

注意 valueOf() 在向集合中添加原始类型值时也会用到。例如， col.add(27) 转换为 col . add(integer . value of(27))。

Integer 在一个小范围的值上维护唯一的 Integer 对象的内部缓存。此范围的下限是-128，上限默认为 127。但是，您可以通过为系统属性 Java . lang . integer . integer cache . high 分配不同的值来更改上限(通过 java.lang.System 类的 String set property(String name，String value) 方法—我在第 8 章中演示了该方法的 String getProperty(String name)对应项)。

注意Java . lang . Byte、 java.lang.Long 和 java.lang.Short 中的每一个还分别维护唯一的字节、长和短对象的内部缓存。

因为有缓存，每个 Integer.valueOf(127) 调用都返回相同的 Integer 对象引用，这也是为什么 i1 == i2 (比较引用)求值为 true 的原因。因为 30000 位于默认范围之外，所以每个 Integer.valueOf(30000) 调用都返回对新的 Integer 对象的引用，这就是为什么 i1 == i2 计算为 false。

对比 == 和！= ，在比较之前不会对装箱后的值进行拆箱，运算符如 < 、 > 、 + 在执行运算之前会对这些值进行拆箱。结果， i1 < i2 转换为 i1 . int value()<I2 . int value()i1+I2 转换为 i1 . int value()+I2 . int value()。

注意不要假设自动装箱和取消装箱是在 == 和的上下文中使用的！= 运算符。

浏览列表

一个列表是一个有序集合，也称为序列。元素可以通过整数索引存储在特定的位置，也可以从特定的位置访问。其中一些元素可能是重复的或空的(当列表的实现允许空元素时)。列表由列表接口描述，其类属类型为列表< E > 。

List 扩展了集合并重新声明了它继承的方法，部分是为了方便。它还重新声明了迭代器()、 add() 、 remove() 、 equals() 和 hashCode() ，以便在它们的契约上放置额外的条件。例如， List 对 add() 的约定指定它将一个元素追加到列表的末尾，而不是将该元素添加到集合中。

List 也声明了表 9-2 的特定于列表的方法。

表 9-2 。列表特定的方法

表 9-2 引用了列表迭代器接口，它比它的迭代器超级接口更加灵活，因为列表迭代器提供了在任意方向上迭代列表、在迭代过程中修改列表以及获取迭代器在列表中的当前位置的方法。

注意ArrayList 和 LinkedList List 实现类中的 iterator() 和 listIterator() 方法返回的迭代器和 ListIterator 实例是 fail-fast :当一个列表被结构性修改(通过调用实现的 add() 方法添加一个新元素时因此，面对并发修改，迭代器会快速而干净地失败，而不是冒着在未来某个不确定的时间出现任意的、不确定的行为的风险。

ListIterator 声明如下方法:

• void add(E e) 将 e 插入到被迭代的列表中。这个元素被直接插入到由 next() 返回的下一个元素之前(如果有的话)，以及由 previous() 返回的下一个元素之后(如果有的话)。当这个列表迭代器不支持 add() 时，这个方法抛出 UnsupportedOperationException，当 e 的类不适合列表时抛出 ClassCastException ，当 e 的某个属性阻止它添加到列表中时抛出 IllegalArgumentException。
• 布尔 hasNext() 正向遍历列表时，当该列表迭代器有更多元素时，返回 true。
• 布尔 hasPrevious() 当这个列表迭代器在反向遍历列表时有更多元素时返回 true。
• E next() 返回列表中的下一个元素，并移动光标位置。当没有下一个元素时，这个方法抛出 NoSuchElementException 。
• int nextIndex() 返回对 next() 的后续调用将返回的元素的索引，或者在列表末尾时返回列表的大小。
• E previous() 返回列表中的前一个元素，并将光标位置向后移动。当没有前一个元素时，这个方法抛出 NoSuchElementException 。
• int previousIndex() 返回元素的索引，该元素将由对 previous() 的后续调用返回，或者在列表开始时返回-1。
• void remove() 从列表中删除由 next() 或 previous() 返回的最后一个元素。每次调用 next() 或 previous() 时，只能进行一次调用。此外，只有在最后一次调用 next() 或 previous() 后，还没有调用 add() 时，才能进行。当这个列表迭代器不支持 remove() 和 IllegalStateException 时，当 next() 和 previous() 都没有被调用，或者在最后一次调用 next() 或 previous()之后已经调用了 remove() 或 add() 时，这个方法抛出 UnsupportedOperationException
• void set(E e) 用元素 e 替换 next() 或 previous() 返回的最后一个元素。只有在最后一次调用 next() 或 previous() 后，既没有调用 remove() 也没有调用 add() 时，才能进行该调用。当这个列表迭代器不支持 set() 时，这个方法抛出 UnsupportedOperationException，当 e 的类不适合列表时抛出 ClassCastException ，当 e 的某个属性阻止它被添加到列表中时抛出 IllegalArgumentException，当【T30

一个 ListIterator 实例没有当前元素的概念。相反，它有一个用于浏览列表的光标的概念。 nextIndex() 和 previousIndex() 方法返回光标位置，该位置总是位于调用 previous() 返回的元素和调用 next() 返回的元素之间。长度为 n 的列表的列表迭代器有 n +1 个可能的光标位置，如下面每个脱字符号( ^ )所示:

                    Element(0)   Element(1)   Element(2)   . . . Element(n-1)
cursor positions:  ^            ^            ^            ^                  ^

注意只要小心，你可以混合呼叫 next() 和 previous() 。请记住，第一次调用 previous() 会返回与最后一次调用 next() 相同的元素。此外，在对 previous() 的一系列调用之后，对 next() 的第一次调用返回与对 previous() 的最后一次调用相同的元素。

表 9-2 对子列表()方法的描述指的是视图的概念，是一个由另一个列表支持的列表。对视图所做的更改会反映在此支持列表中。视图可以覆盖整个列表，或者，正如 subList() 的名字所暗示的，只覆盖列表的一部分。

subList() 方法对于以紧凑的方式在列表上执行范围视图操作非常有用。例如， list.subList(fromIndex，toIndex)。clear()；从列表中删除一系列元素，其中第一个元素位于索引的处，最后一个元素位于索引的处。

注意当后备列表发生变化时，视图的含义变得不明确。因此，只要需要在后备列表上执行一系列范围操作，就应该临时使用 subList() 。

数组列表

ArrayList 类提供了一个基于内部数组的列表实现。因此，对列表元素的访问很快。但是，因为必须移动元素以打开插入空间或在删除后关闭空间，所以元素的插入和删除很慢。

ArrayList 提供了三个构造函数:

• ArrayList() 创建一个空数组列表，初始容量(存储空间)为 10 个元素。一旦达到这个容量，就分配一个更大的数组，将当前数组中的元素复制到更大的数组中，该更大的数组成为新的当前数组。随着附加元素被添加到数组列表中，该过程重复进行。
• ArrayList(收藏<？extends E > c) 创建一个数组列表，包含 c 的元素，按照它们被 c 的迭代器返回的顺序排列。当 c 包含空引用时，抛出 NullPointerException 。
• ArrayList(int initial capacity)创建一个空数组列表，初始容量为 initialCapacity 个元素。当 initialCapacity 为负时抛出 IllegalArgumentException 。

清单 9-1 展示了一个数组列表。

清单 9-1 。基于数组的列表演示

import java.util.ArrayList;
import java.util.List;

public class ArrayListDemo
{
   public static void main(String[] args)
   {
      List<String> ls = new ArrayList<String>();
      String[] weekDays = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
      for (String weekDay: weekDays)
         ls.add(weekDay);
      dump("ls:", ls);
      ls.set(ls.indexOf("Wed"), "Wednesday");
      dump("ls:", ls);
      ls.remove(ls.lastIndexOf("Fri"));
      dump("ls:", ls);
   }

   static void dump(String title, List<String> ls)
   {
      System.out.print(title + " ");
      for (String s: ls)
         System.out.print(s + " ");
      System.out.println();
   }
}

创建一个数组列表和一个星期名称的数组。然后用这些名称填充这个列表，将列表转储到标准输出，更改其中一个列表条目，再次转储列表，删除一个列表条目，最后一次转储列表。 dump() 方法的增强 for 循环语句在幕后使用了迭代器()、 hasNext() 、 next() 。

当您运行此应用时，它会生成以下输出:

ls: Sun Mon Tue Wed Thu Fri Sat
ls: Sun Mon Tue Wednesday Thu Fri Sat
ls: Sun Mon Tue Wednesday Thu Sat

链接列表

LinkedList 类提供了基于链接节点的列表实现。因为必须遍历链接，所以对列表元素的访问很慢。但是，因为只需要更改节点引用，所以元素的插入和删除很快。

什么是节点？

一个节点是一个固定的值和链接存储器位置序列。与数组不同，在数组中，每个槽存储同一基元类型或引用超类型的单个值，节点可以存储不同类型的多个值。它还可以存储链接(对其他节点的引用)。

考虑下面这个简单的节点类:

类节点

{

字符串名称；//值字段

下一个节点；//链接字段

}

节点描述简单节点，其中每个节点由单个名称值字段和单个下一个链接字段组成。请注意，下一个的与声明它的类类型相同。这种安排让一个节点实例在这个字段中存储对另一个节点实例(即下一个节点)的引用。产生的节点被链接在一起。

下面的代码片段创建了两个节点对象，并将第二个节点对象链接到第一个节点对象。这个片段还演示了如何通过跟踪每个节点对象的下一个字段来遍历这个链表。当遍历代码发现下一个包含空引用时，节点遍历停止，这表示列表结束:

节点优先=新节点()；

first.name = "第一个节点"；//您通常会提供 getter 和 setter 方法。

节点 last =新节点()；

last.name = "最后一个节点"；

last.next = null

first.next = last

节点 temp = first

while (temp！=空)

{

system . out . println(temp . name)；

temp = temp.next

}

代码首先构建两个节点的链表，然后将 first 赋值给局部变量 temp 来遍历列表，而不会丢失对存储在 first 中的第一个节点的引用。当 temp 不为 null 时，循环输出 name 字段。它还通过 temp = temp.next 导航到列表中的下一个节点对象；声明。

如果您将此代码转换为应用并运行该应用，您将发现以下输出:

第一节点

最后一个音符

LinkedList 提供了两个构造函数:

• 创建一个空的链表。
• LinkedList(收藏<？extends E > c) 创建一个链表，包含 c 的元素，按照它们被 c 的迭代器返回的顺序排列。当 c 包含空引用时，抛出 NullPointerException 。

清单 9-2 展示了一个链表。

清单 9-2 。链接节点列表的演示

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class LinkedListDemo
{
   public static void main(String[] args)
   {
      List<String> ls = new LinkedList<String>();
      String[] weekDays = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
      for (String weekDay: weekDays)
         ls.add(weekDay);
      dump("ls:", ls);
      ls.add(1, "Sunday");
      ls.add(3, "Monday");
      ls.add(5, "Tuesday");
      ls.add(7, "Wednesday");
      ls.add(9, "Thursday");
      ls.add(11, "Friday");
      ls.add(13, "Saturday");
      dump("ls:", ls);
      ListIterator<String> li = ls.listIterator(ls.size());
      while (li.hasPrevious())
         System.out.print(li.previous() + " ");
      System.out.println();
   }

   static void dump(String title, List<String> ls)
   {
      System.out.print(title + " ");
      for (String s: ls)
         System.out.print(s + " ");
      System.out.println();
   }
}

创建一个链表和一个星期名称的数组。然后用这些名字填充这个列表，将列表转储到标准输出，在较短的名字后面插入较长的工作日名字，再次转储列表，并通过使用一个列表迭代器以相反的顺序输出列表，该列表迭代器的光标在列表末尾初始化，并重复调用它的 previous() 方法。

当您运行此应用时，它会生成以下输出:

ls: Sun Mon Tue Wed Thu Fri Sat
ls: Sun Sunday Mon Monday Tue Tuesday Wed Wednesday Thu Thursday Fri Friday Sat Saturday
Saturday Sat Friday Fri Thursday Thu Wednesday Wed Tuesday Tue Monday Mon Sunday Sun

探索集

一个集合是一个不包含重复元素的集合。换句话说，一个集合不包含元素对 e1 和 e2 使得E1T8】。equals(E2)返回 true。此外，一个集合最多可以包含一个空元素。集合由 Set 接口描述，其泛型类型为 SetT17】。

Set 扩展了集合并重新声明了其继承的方法，为了方便起见，也为了给 add() 、 equals() 和 hashCode() 的契约添加规定，以解决它们在 Set 上下文中的行为。另外， Set 的文档声明所有实现类的构造函数必须创建不包含重复元素的集合。

Set 没有引入新的方法。

tree set〔t0〕

TreeSet 类提供了一个基于树数据结构的集合实现。因此，元素按排序顺序存储。然而，访问这些元素比使用其他 Set 实现(没有排序)要慢一些，因为必须遍历链接。

注查看维基百科的“树(数据结构)”词条(http://en . Wikipedia . org/wiki/Tree _(数据)了解树。

TreeSet 提供了四个构造函数:

• TreeSet() 创建一个新的空树集合，根据其元素的自然排序进行排序。插入到集合中的所有元素必须实现可比的接口。
• TreeSet(收藏<？extends E > c) 创建一个新的树集合，包含按照元素的自然排序排序的 c 的元素。插入到新集合中的所有元素必须实现可比接口。当 c 的元素没有实现 Comparable 或者不能相互比较时，这个构造函数抛出 ClassCastException ，当 c 包含空引用时，抛出 NullPointerException 。
• TreeSet(比较器<？super E > comparator) 创建一个新的空树集合，根据指定的比较器进行排序。将 null 传递给比较器意味着将使用自然排序。
• TreeSet(sorted setss)创建一个新的树集合，它包含与 ss 相同的元素并使用相同的排序。(我将在本章后面讨论有序集合。)当 ss 包含空引用时，这个构造函数抛出 NullPointerException 。

清单 9-3 展示了一个树集合。

清单 9-3 。一个树集合的演示，其中的字符串元素按照它们的自然顺序排序

import java.util.Set;
import java.util.TreeSet;

public class TreeSetDemo
{
   public static void main(String[] args)
   {
      Set<String> ss = new TreeSet<String>();
      String[] fruits = {"apples", "pears", "grapes", "bananas", "kiwis"};
      for (String fruit: fruits)
         ss.add(fruit);
      dump("ss:", ss);
   }

   static void dump(String title, Set<String> ss)
   {
      System.out.print(title + " ");
      for (String s: ss)
         System.out.print(s + " ");
      System.out.println();
   }
}

创建一个树集合和一个水果名称数组。然后，它用这些名称填充该集合，并将该集合转储到标准输出。因为字符串实现了可比，所以这个应用将水果数组的内容插入到通过 TreeSet() 构造函数创建的树集中是合法的。

当您运行此应用时，它会生成以下输出:

ss: apples bananas grapes kiwis pears

哈希集

HashSet 类提供了一个由散列表数据结构支持的 Set 实现(实现为一个 HashMap 实例，稍后讨论，它提供了一种快速确定元素是否已经存储在该结构中的方法)。尽管这个类没有为它的元素提供排序保证，但是 HashSet 比 TreeSet 要快得多。此外， HashSet 允许空引用存储在其实例中。

注意查看维基百科的“哈希表”条目()了解哈希表。

HashSet 提供四个构造器:

• HashSet() 创建一个新的空 HashSet，其中后台 HashMap 实例的初始容量为 16，负载系数为 0.75。当我在本章后面讨论散列表时，你会了解到这些项目的含义。
• HashSet(收藏<？扩展 E > c) 创建一个包含 c 元素的新哈希表。后台散列表的初始容量足以容纳 c 的元素，装载系数为 0.75。当 c 包含空引用时，该构造函数抛出 NullPointerException 。
• HashSet(int initial capacity)创建一个新的空 HashSet，其中后台 HashMap 实例具有由 initialCapacity 指定的容量和 0.75 的负载系数。当 initialCapacity 的值小于 0 时，该构造函数抛出 IllegalArgumentException 。
• HashSet(int initialCapacity，float loadFactor) 创建一个新的空 HashSet，其中后台 HashMap 实例具有由 initialCapacity 指定的容量和由 loadFactor 指定的加载因子。当 initialCapacity 小于 0 或 loadFactor 小于或等于 0 时，该构造函数抛出 IllegalArgumentException 。

清单 9-4 展示了一个 hashset。

清单 9-4 。演示一个字符串元素无序的 Hashset

import java.util.HashSet;
import java.util.Set;

public class HashSetDemo
{
   public static void main(String[] args)
   {
      Set<String> ss = new HashSet<String>();
      String[] fruits = {"apples", "pears", "grapes", "bananas", "kiwis",
                         "pears", null};
      for (String fruit: fruits)
         ss.add(fruit);
      dump("ss:", ss);
   }

   static void dump(String title, Set<String> ss)
   {
      System.out.print(title + " ");
      for (String s: ss)
         System.out.print(s + " ");
      System.out.println();
   }
}

HashSetDemo 创建一个 hashset 和一个水果名称数组。然后，它用这些名称填充该集合，并将该集合转储到标准输出。与 TreeSet 不同， HashSet 允许添加 null (不抛出 NullPointerException )，这就是为什么清单 9-4 在 HashSetDemo 的水果数组中包含了 null 。

当您运行此应用时，它会生成如下所示的无序输出:

ss: null grapes bananas kiwis pears apples

假设您想将类的实例添加到一个 hashset 中。与字符串一样，您的类必须覆盖 equals() 和 hashCode()；否则，可能会在 hashset 中存储重复的类实例。例如，清单 9-5 给出了一个应用的源代码，该应用的 Planet 类覆盖了 equals() ，但是没有覆盖 hashCode() 。

清单 9-5 。一个自定义的行星类没有覆盖 hashCode()

import java.util.HashSet;
import java.util.Set;

public class CustomClassAndHashSet
{
   public static void main(String[] args)
   {
      Set<Planet> sp = new HashSet<Planet>();
      sp.add(new Planet("Mercury"));
      sp.add(new Planet("Venus"));
      sp.add(new Planet("Earth"));
      sp.add(new Planet("Mars"));
      sp.add(new Planet("Jupiter"));
      sp.add(new Planet("Saturn"));
      sp.add(new Planet("Uranus"));
      sp.add(new Planet("Neptune"));
      sp.add(new Planet("Fomalhaut b"));
      Planet p1 = new Planet("51 Pegasi b");
      sp.add(p1);
      Planet p2 = new Planet("51 Pegasi b");
      sp.add(p2);
      System.out.println(p1.equals(p2));
      System.out.println(sp);
   }
}

class Planet
{
   private String name;

   Planet(String name)
   {
      this.name = name;
   }

   @Override
   public boolean equals(Object o)
   {
      if (!(o instanceof Planet))
         return false;
      Planet p = (Planet) o;
      return p.name.equals(name);
   }

   String getName()
   {
      return name;
   }

   @Override
   public String toString()
   {
      return name;
   }
}

清单 9-5 的星球类声明了一个类型为字符串的名称字段。虽然用单个字符串字段声明行星似乎没有意义，因为我可以重构这个清单来删除行星并使用字符串，但我可能希望在将来为行星引入额外的字段(也许是为了存储行星的质量和其他特征)。

当您运行此应用时，它会生成如下所示的无序输出:

true
[Neptune, Mars, Mercury, Fomalhaut b, Venus, 51 Pegasi b, 51 Pegasi b, Jupiter, Saturn, Earth, Uranus]

这个输出揭示了 hashset 中的两个 51 Pegasi b 元素。尽管从覆盖的 equals() 方法的角度来看，这些元素是相等的(第一个输出行 true 证明了这一点)，但是覆盖 equals() 并不足以避免在 hashset 中存储重复的元素:还必须覆盖 hashCode() 。

覆盖清单 9-5 的星球类中的 hashCode() 的最简单方法是让覆盖方法调用 name 字段的 hashCode() 方法并返回其值。(这种技术只适用于单个引用字段的类提供有效的 hashCode() 方法的类。)清单 9-6 展示了这个覆盖的 hashCode() 方法。

清单 9-6 。覆盖 hashCode()的自定义 Planet 类

import java.util.HashSet;
import java.util.Set;

public class CustomClassAndHashSet
{
   public static void main(String[] args)
   {
      Set<Planet> sp = new HashSet<Planet>();
      sp.add(new Planet("Mercury"));
      sp.add(new Planet("Venus"));
      sp.add(new Planet("Earth"));
      sp.add(new Planet("Mars"));
      sp.add(new Planet("Jupiter"));
      sp.add(new Planet("Saturn"));
      sp.add(new Planet("Uranus"));
      sp.add(new Planet("Neptune"));
      sp.add(new Planet("Fomalhaut b"));
      Planet p1 = new Planet("51 Pegasi b");
      sp.add(p1);
      Planet p2 = new Planet("51 Pegasi b");
      sp.add(p2);
      System.out.println(p1.equals(p2));
      System.out.println(sp);
   }
}

class Planet
{
   private String name;

   Planet(String name)
   {
      this.name = name;
   }

   @Override
   public boolean equals(Object o)
   {
      if (!(o instanceof Planet))
         return false;
      Planet p = (Planet) o;
      return p.name.equals(name);
   }

   String getName()
   {
      return name;
   }

   @Override
   public int hashCode()
   {
      return name.hashCode();
   }

   @Override
   public String toString()
   {
      return name;
   }
}

编译 清单 9-6(javac CustomClassAndHashSet.java)并运行应用(Java customclassandhasset)。您将观察到没有重复元素的输出(类似于下图所示):

true
[Saturn, Earth, Uranus, Fomalhaut b, 51 Pegasi b, Venus, Jupiter, Mercury, Mars, Neptune]

注意 LinkedHashSet 是 HashSet 的子类，它使用链表来存储其元素。因此， LinkedHashSet 的迭代器按照元素插入的顺序返回元素。例如，如果清单 9-4 已经指定设置<字符串> ss = new LinkedHashSet <字符串>()；，应用的输出应该是 ss:苹果梨葡萄香蕉猕猴桃 null 。另外， LinkedHashSet 比 HashSet 提供更慢的性能，比 TreeSet 提供更快的性能。

枚举集〔t0〕

在第 6 章中，我向你介绍了传统的枚举类型和它们的枚举替换。(一个枚举是通过保留字枚举表示的枚举类型。)下面的例子演示了传统的枚举类型:

static final int SUNDAY = 1;
static final int MONDAY = 2;
static final int TUESDAY = 4;
static final int WEDNESDAY = 8;
static final int THURSDAY = 16;
static final int FRIDAY = 32;
static final int SATURDAY = 64;

虽然 enum 与传统的枚举类型相比有很多优点，但是当将常量组合成一个集合时，传统的枚举类型使用起来不那么笨拙，例如，static final int DAYS _ OFF = SUNDAY | MONDAY；。

DAYS_OFF

注意一个基于 int 的位集不能包含超过 32 个成员，因为 int 的大小是 32 位。类似地，基于长的位集不能包含超过 64 个成员，因为长具有 64 位的大小。

这个位集是通过按位异或运算符( | )对传统枚举类型的整数常量进行按位异或运算而形成的:您也可以使用 + 。每个常数必须是 2 的唯一幂(从 1 开始)，因为否则就不可能区分这个位集的成员。

要确定某个常数是否属于位集，请创建一个包含位 AND 运算符( & )的表达式。例如，((DAYS _ OFF&MONDAY)= = MONDAY)与 MONDAY (2)按位 andDAYS _ OFF(3)，结果为 2。这个值通过 == 与星期一 (2)进行比较，表达式的结果为真:星期一是 DAYS_OFF 位集的成员。

通过实例化一个适当的 Set 实现类并多次调用 add() 方法来存储集合中的常量，可以用 enum 完成同样的任务。清单 9-7 展示了这个更尴尬的选择。

清单 9-7 。创建相当于 DAYS_OFF 的集合

import java.util.Set;
import java.util.TreeSet;

enum Weekday
{
   SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY
}

public class DaysOff
{
   public static void main(String[] args)
   {
      Set<Weekday> daysOff = new TreeSet<Weekday>();
      daysOff.add(Weekday.SUNDAY);
      daysOff.add(Weekday.MONDAY);
      System.out.println(daysOff);
   }
}

当您运行此应用时，它会生成以下输出:

[SUNDAY, MONDAY]

注意存储在树集中的是常量的序数，而不是它们的名字，这就是为什么名字看起来是无序的( S 在 M 之前)，尽管常量是按照它们序数的排序顺序存储的。

除了比 bitset 更难使用(也更冗长)之外， Set 替代方案需要更多内存来存储每个常量，而且速度也不够快。因为这些问题， EnumSet 被引入。

枚举集类 提供了基于位集的集实现。它的元素是常量，必须来自同一个枚举，该枚举是在创建枚举集时指定的。不允许空元素；任何存储空元素的尝试都会导致抛出 NullPointerException 。

清单 9-8 演示了枚举集。

清单 9-8 。创建相当于 DAYS_OFF 的枚举集

import java.util.EnumSet;
import java.util.Iterator;
import java.util.Set;

enum Weekday
{
   SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY
}

public class EnumSetDemo
{
   public static void main(String[] args)
   {
      Set<Weekday> daysOff = EnumSet.of(Weekday.SUNDAY, Weekday.MONDAY);
      Iterator<Weekday> iter = daysOff.iterator();
      while (iter.hasNext())
         System.out.println(iter.next());
   }
}

EnumSetDemo 利用了 EnumSet 的泛型 EnumSet < E 扩展 Enum < E > > 的特性，提供了各种类方法来方便地构造 Enum 集合。例如， < E 扩展 Enum>Enum setof(E E1，E e2) 返回一个由元素 e1 和 e2 组成的 EnumSet 实例。在这个例子中，那些元素是工作日。周日和工作日。周一。

当您运行此应用时，它会生成以下输出:

SUNDAY
MONDAY

注意除了提供()方法的几个重载的， EnumSet 还提供了其他方便创建枚举集的方法。例如， allOf() 返回一个包含所有枚举常量的 EnumSet 实例，其中该方法的唯一参数是一个标识枚举的类文字 (一个表达式，包含一个类名，后面跟一个点，后面跟一个保留字 class ):

设置<工作日>all weekdays = enum Set . allof(Weekday . class)；

类似地， range() 返回一个 EnumSet 实例，该实例包含一个枚举元素范围(该范围的限制由该方法的两个参数指定):

for(WeekDay wd:enum set . range(WeekDay。周一，工作日。星期五))system . out . println(wd)；

探索有序集合

TreeSet 是排序集合的一个例子，它是一个以升序维护其元素的集合，根据它们的自然排序或根据创建排序集合时提供的比较器进行排序。排序集合由 SortedSet 接口描述。

SortedSet ，其类属类型为 SortedSet < E > ，扩展 Set 。除了两个例外，它从集合继承的方法在排序集合上的行为与在其他集合上的行为相同:

• 从迭代器()返回的迭代器实例按照元素升序遍历排序后的集合。
• 由 toArray() 返回的数组包含有序集合的元素。

注意尽管没有得到保证，集合框架中 SortedSet 实现的 toString() 方法(例如 TreeSet )返回一个包含所有有序集合元素的字符串。

分类树集的文档要求一个实现提供我在讨论树集时提出的四个标准构造函数。此外，该接口的实现必须实现表 9-3 中描述的方法。

表 9-3。 排序的具体方法

从 headSet() 、 subSet() 和 tailSet() 返回的基于集合的范围视图类似于从 List 的 subList() 方法返回的基于列表的范围视图，除了基于集合的范围视图即使在后台排序集合被修改时仍然有效。因此，基于集合的范围视图可以使用很长一段时间。

注意与端点是后备列表中的元素的基于列表的范围视图不同，基于集合的范围视图的端点是元素空间中的绝对点，允许基于集合的范围视图充当集合的元素空间的一部分的窗口。对基于集合的范围视图所做的任何更改都被写回到后备排序集合，反之亦然。

由耳机()、子集()或 tailSet() 返回的每个范围视图都是半开，因为它不包括其高端点(耳机()和子集())或其低端点( tailSet() )。对于前两种方法，高端点由参数指定给元素；对于最后一种方法，低端点由元素的参数指定。

注意你也可以把返回的范围视图看作是半封闭的，因为它只包括它的一个端点。

清单 9-9 展示了一个基于树集合的有序集合。

清单 9-9 。一组经过排序的水果和蔬菜名称

import java.util.SortedSet;
import java.util.TreeSet;

public class SortedSetDemo
{
   public static void main(String[] args)
   {
      SortedSet<String> sss = new TreeSet<String>();
      String[] fruitAndVeg =
      {
         "apple", "potato", "turnip", "banana", "corn", "carrot", "cherry",
         "pear", "mango", "strawberry", "cucumber", "grape", "banana",
         "kiwi", "radish", "blueberry", "tomato", "onion", "raspberry",
         "lemon", "pepper", "squash", "melon", "zucchini", "peach", "plum",
         "turnip", "onion", "nectarine"
      };
      System.out.println("Array size = " + fruitAndVeg.length);
      for (String fruitVeg: fruitAndVeg)
         sss.add(fruitVeg);
      dump("sss:", sss);
      System.out.println("Sorted set size = " + sss.size());
      System.out.println("First element = " + sss.first());
      System.out.println("Last element = " + sss.last());
      System.out.println("Comparator = " + sss.comparator());
      dump("hs:", sss.headSet("n"));
      dump("ts:", sss.tailSet("n"));
      System.out.println("Count of p-named fruits & vegetables = " +
                         sss.subSet("p", "q").size());
      System.out.println("Incorrect count of c-named fruits & vegetables = " +
                         sss.subSet("carrot", "cucumber").size());
      System.out.println("Correct count of c-named fruits & vegetables = " +
                         sss.subSet("carrot", "cucumber\0").size());
   }

   static void dump(String title, SortedSet<String> sss)
   {
      System.out.print(title + " ");
      for (String s: sss)
         System.out.print(s + " ");
      System.out.println();
   }
}

SortedSetDemo 创建一个有序集合和一个水果和蔬菜名称的数组，然后从这个数组开始填充集合。在转储集合的内容之后，它输出关于集合的信息，包括集合各部分的头部和尾部视图。

当您运行此应用时，它会生成以下输出:

Array size = 29
sss: apple banana blueberry carrot cherry corn cucumber grape kiwi lemon mango melon nectarine onion peach pear pepper plum potato radish raspberry squash strawberry tomato turnip zucchini
Sorted set size = 26
First element = apple
Last element = zucchini
Comparator = null
hs: apple banana blueberry carrot cherry corn cucumber grape kiwi lemon mango melon
ts: nectarine onion peach pear pepper plum potato radish raspberry squash strawberry tomato turnip zucchini
Count of p-named fruits & vegetables = 5
Incorrect count of c-named fruits & vegetables = 3
Correct count of c-named fruits & vegetables = 4

该输出显示，排序后的集合的大小小于数组的大小，因为集合不能包含重复的元素:重复的香蕉、芜菁和洋葱元素没有存储在排序后的集合中。

comparator() 方法 返回 null，因为排序集不是用比较器创建的。相反，有序集依赖于字符串元素的自然排序，以有序的顺序存储它们。

使用参数 "n" 调用 headSet() 和 tailSet() 方法，以分别返回一组元素，这些元素的名称以严格小于 n 的字母和大于或等于 n 的字母开头。

最后，输出告诉您，在向 subSet() 传递上限时必须小心。可以看到， ss.subSet("胡萝卜"，"黄瓜")在返回的范围视图中不包括黄瓜，因为黄瓜是 subSet() 的高端点。

要将黄瓜包含在范围视图中，需要形成一个闭合范围或闭合区间 l (两个端点都包含在内)。使用字符串对象，您可以通过将 \0 附加到字符串来完成这项任务。比如 ss.subSet("胡萝卜"，"黄瓜\0") 包含黄瓜，因为它小于黄瓜\0 。

同样的技术可以应用于任何需要形成开放范围或开放区间 (不包括端点)的地方。比如 ss.subSet("胡萝卜\0 "，"黄瓜")不包含胡萝卜，因为它小于胡萝卜\0 。此外，它不包括高端点黄瓜。

注意当您想要为从您自己的类中创建的元素创建封闭和开放的范围时，您需要提供某种形式的 predecessor() 和 successor() 方法，它们返回一个元素的前任和继任者。

在设计使用有序集合的类时，您需要非常小心。例如，当您计划将该类的实例存储在一个有序集合中时，该类必须实现 Comparable ，在该集合中，这些元素根据它们的自然顺序进行排序。考虑清单 9-10 中的。

清单 9-10 。自定义雇员类没有实现可比性

import java.util.SortedSet;
import java.util.TreeSet;

public class CustomClassAndSortedSet
{
   public static void main(String[] args)
   {
      SortedSet<Employee> sse = new TreeSet<Employee>();
      sse.add(new Employee("Sally Doe"));
      sse.add(new Employee("Bob Doe")); // ClassCastException thrown here
      sse.add(new Employee("John Doe"));
      System.out.println(sse);
   }
}

class Employee
{
   private String name;

   Employee(String name)
   {
      this.name = name;
   }

   @Override
   public String toString()
   {
      return name;
   }
}

当您运行此应用时，它会生成以下输出:

线程“main”Java . lang . classcastexception 中出现异常:Employee 不能转换为 java.lang.Comparable

at java.util.TreeMap.compare(Unknown Source)
 at java.util.TreeMap.put(Unknown Source)
 at java.util.TreeSet.add(Unknown Source)
 at CustomClassAndSortedSet.main(CustomClassAndSortedSet.java:9)

在第二个 add() 方法调用期间抛出了 ClassCastException 实例，因为排序集实现 TreeSet 的实例无法调用第二个 Employee 元素的 compareTo() 方法，因为 Employee 没有实现 Comparable 。

这个问题的解决方案是让类实现可比的 ，这正是清单 9-11 中的所揭示的。

清单 9-11 。使员工要素具有可比性

import java.util.SortedSet;
import java.util.TreeSet;

public class CustomClassAndSortedSet
{
   public static void main(String[] args)
   {
      SortedSet<Employee> sse = new TreeSet<Employee>();
      sse.add(new Employee("Sally Doe"));
      sse.add(new Employee("Bob Doe"));
      Employee e1 = new Employee("John Doe");
      Employee e2 = new Employee("John Doe");
      sse.add(e1);
      sse.add(e2);
      System.out.println(sse);
      System.out.println(e1.equals(e2));
   }
}

class Employee implements Comparable<Employee>
{
   private String name;

   Employee(String name)
   {
      this.name = name;
   }

   @Override
   public int compareTo(Employee e)
   {
      return name.compareTo(e.name);
   }

   @Override
   public String toString()
   {
      return name;
   }
}

清单 9-11 的 main() 方法与清单 9-10 的不同之处在于，它还创建了两个 Employee 对象，初始化为 "John Doe" ，将这些对象添加到排序后的集合中，并通过 equals() 比较这些对象是否相等。此外，清单 9-11 声明雇员实现可比，将 compareTo() 方法引入雇员。

当您运行此应用时，它会生成以下输出:

[Bob Doe, John Doe, Sally Doe]
false

该输出显示只有一个“John Doe”雇员对象存储在排序后的集合中。毕竟，一个集合不能包含重复的元素。然而， false 值(由 equals() 比较得出)也表明排序集合的自然排序与 equals() 不一致，这违反了 SortedSet 的契约 :

排序集维护的排序 (无论是否提供显式比较器)必须与【equals()一致，排序集才能正确实现 集 接口。这是因为 集合 接口是根据【equals()操作定义的，但是排序后的集合使用其compare to()(或 compare() )方法执行所有元素比较，因此从排序后的集合的角度来看，被该方法视为相等的两个元素是相等的。

因为应用工作正常，为什么 SortedSet 的合同有关系？尽管契约似乎与 SortedSet 的 TreeSet 实现无关，但在实现该接口的第三方类的上下文中可能会有关系。

清单 9-12 向您展示了如何纠正这个问题，并让雇员实例与一个有序集合的任何实现一起工作。

清单 9-12 。遵守合同的雇员阶层

import java.util.SortedSet;
import java.util.TreeSet;

public class CustomClassAndSortedSet
{
   public static void main(String[] args)
   {
      SortedSet<Employee> sse = new TreeSet<Employee>();
      sse.add(new Employee("Sally Doe"));
      sse.add(new Employee("Bob Doe"));
      Employee e1 = new Employee("John Doe");
      Employee e2 = new Employee("John Doe");
      sse.add(e1);
      sse.add(e2);
      System.out.println(sse);
      System.out.println(e1.equals(e2));
   }
}

class Employee implements Comparable<Employee>
{
   private String name;

   Employee(String name)
   {
      this.name = name;
   }

   @Override
   public int compareTo(Employee e)
   {
      return name.compareTo(e.name);
   }

   @Override
   public boolean equals(Object o)
   {
      if (!(o instanceof Employee))
         return false;
      Employee e = (Employee) o;
      return e.name.equals(name);
   }

   @Override
   public String toString()
   {
      return name;
   }
}

清单 9-12 通过覆盖 equals() 纠正了 SortedSet 契约违反。运行生成的应用，您会看到第一行输出是【Bob Doe，John Doe，Sally Doe】，第二行是 true :排序后的集合的自然排序现在与 equals() 一致。

注意尽管每当你覆盖 equals() 时覆盖 hashCode() 是很重要的，但我没有覆盖 hashCode() (尽管我覆盖了清单 9-12 的 Employee 类中的 equals() ，以强调基于树的排序集合忽略 hashCode() 。

探索可导航集合

TreeSet 是可导航集合的一个例子，它是一个排序集合，可以以降序和升序迭代，并且可以报告给定搜索目标的最接近匹配。导航集由 NavigableSet 接口描述，其泛型为 navigable setT9】，扩展了 SortedSet ，在表 9-4 中有描述。

表 9-4 。可导航的特定集合方法

清单 9-13 展示了一个基于树集合的可导航集合。

清单 9-13 。导航一组整数

import java.util.Iterator;
import java.util.NavigableSet;
import java.util.TreeSet;

public class NavigableSetDemo
{
   public static void main(String[] args)
   {
      NavigableSet<Integer> ns = new TreeSet<Integer>();
      int[] ints = { 82, -13, 4, 0, 11, -6, 9 };
      for (int i: ints)
         ns.add(i);
      System.out.print("Ascending order: ");
      Iterator iter = ns.iterator();
      while (iter.hasNext())
         System.out.print(iter.next() + " ");
      System.out.println();
      System.out.print("Descending order: ");
      iter = ns.descendingIterator();
      while (iter.hasNext())
         System.out.print(iter.next() + " ");
      System.out.println("\n");
      outputClosestMatches(ns, 4);
      outputClosestMatches(ns.descendingSet(), 12);
   }

   static void outputClosestMatches(NavigableSet<Integer> ns, int i)
   {
      System.out.println("Element < " + i + " is " + ns.lower(i));
      System.out.println("Element <= " + i + " is " + ns.floor(i));
      System.out.println("Element > " + i + " is " + ns.higher(i));
      System.out.println("Element >= " + i +" is " + ns.ceiling(i));
      System.out.println();
   }
}

清单 9-13 创建一组可导航的整数元素。它利用自动装箱来确保 int s 被转换成整数。

当您运行此应用时，它会生成以下输出:

Ascending order: -13 -6 0 4 9 11 82
Descending order: 82 11 9 4 0 -6 -13

Element < 4 is 0
Element <= 4 is 4
Element > 4 is 9
Element >= 4 is 4

Element < 12 is 82
Element <= 12 is 82
Element > 12 is 11
Element >= 12 is 11

以元素开始的前四个输出行属于一个升序集合，其中被匹配的元素( 4 )是该集合的成员。第二个四个元素前缀的行属于降序集合，其中被匹配的元素( 12 )不是成员。

除了让您通过其最接近的匹配方法 ( ceiling() 、 floor() 、 higher() 和 lower() )方便地定位集合元素之外，navigabableset 还让您返回包含特定范围内所有元素的集合视图，如以下示例所示:

• ns.subSet(-13，true，9，true) :返回从 -13 到 9 的所有元素。
• ns.tailSet(-6，false) :返回所有大于 -6 的元素。
• ns.headSet(4，true) :返回所有小于等于 4 的元素。

最后，您可以通过调用 pollFirst() 从集合中返回和移除第一个(最低的)元素，通过调用 pollLast() 返回和移除最后一个(最高的)元素。比如 ns.pollFirst() 移除并返回 -13 ，而 ns.pollLast() 移除并返回 82 。

探索队列

一个队列是一个集合，其中的元素以特定的顺序存储和检索。大多数队列分为以下几类:

• 先进先出(FIFO )队列:在队列的尾部插入元素，在队列的头部移除元素。
• 后进先出(LIFO )队列:在队列的一端插入和移除元素，使得最后插入的元素是第一个检索到的元素。这种队列表现为一个堆栈。
• 优先级队列 :根据元素的自然排序或者根据提供给队列实现的比较器来插入元素。

Queue ，其类属类型为 Queue < E > ，扩展了集合，重新声明 add() 来调整其契约(如果有可能在不违反容量限制的情况下立即将指定元素插入该队列)，并从集合中继承其他方法。表 9-5 描述了 add() 和其他队列的具体方法。

表 9-5 。特定于队列的方法

表 9-5 揭示了两组方法:在一组中，一个方法(如 add() )在操作失败时抛出异常；在另一个集合中，一个方法(例如， offer() )在出现故障时返回一个特殊值(false 或 null)。返回特殊值的方法在容量受限的队列实现的上下文中很有用，在这种情况下，失败是经常发生的。

注意在使用容量受限队列时， offer() 方法通常优于 add() ，因为 offer() 不会抛出 IllegalStateException 。

Java 提供了许多队列实现类，其中大多数类都是 java.util.concurrent 包的成员: LinkedBlockingQueue 和 SynchronousQueue 就是例子。相比之下， java.util 包提供了 LinkedList 和 PriorityQueue 作为其队列实现类。

注意许多队列实现类不允许添加空元素。然而，一些类(例如， LinkedList )允许空元素。您应该避免添加 null 元素，因为 null 被 peek() 和 poll() 方法用作特殊的返回值，以指示队列为空。

优先级队列

PriorityQueue 类提供了一个优先级队列的实现，这是一个队列，它根据元素的自然排序或由队列实例化时提供的比较器对其元素进行排序。依赖自然排序时，优先级队列不允许空元素，也不允许插入非可比的对象。

优先级队列头部的元素是指定排序中最小的元素。当多个元素并列为最小元素时，任意选择其中一个元素作为最小元素。类似地，优先级队列尾部的元素是最大的元素，当出现平局时任意选择。

优先级队列是无限的，但是有一个容量来控制用于存储优先级队列元素的内部数组的大小。容量值至少与队列的长度一样大，并且随着元素被添加到优先级队列中而自动增长。

PriorityQueue (其泛型为 PriorityQueue < E > )提供了六个构造函数:

• PriorityQueue() 创建一个初始容量为 11 个元素的 PriorityQueue 实例，该实例根据元素的自然顺序对其进行排序。
• PriorityQueue(集合<？扩展 E > c) 创建一个包含 c 元素的优先级队列实例。如果 c 是一个 SortedSet 或 PriorityQueue 实例，那么这个优先级队列将按照相同的顺序进行排序。否则，该优先级队列将根据其元素的自然顺序进行排序。当 c 的元素不能根据优先级队列的顺序相互比较时，该构造函数抛出 ClassCastException ，当 c 或其任何元素包含空引用时，该构造函数抛出 NullPointerException 。
• priority queue(int initial capacity)用指定的 initialCapacity 创建一个 PriorityQueue 实例，该实例根据元素的自然顺序对其进行排序。当 initialCapacity 小于 1 时，该构造函数抛出 IllegalArgumentException 。
• priority queue(int initial capacity，比较器<？超级 E >比较器)使用指定的初始容量创建一个优先级队列实例，该实例根据指定的比较器对其元素进行排序。当比较器包含零参考时，使用自然排序。当 initialCapacity 小于 1 时，该构造函数抛出 IllegalArgumentException。
• 优先级队列(PriorityQueue <？扩展 E > pq) 创建一个包含 pq 元素的 PriorityQueue 实例。该优先级队列将按照与 pq 相同的顺序进行排序。当 pq 的元素不能根据 pq 的排序相互比较时，该构造函数抛出 ClassCastException ，当 pq 或其任何元素包含空引用时，该构造函数抛出 NullPointerException 。
• PriorityQueue(SortedSet <？扩展 E > ss) 创建一个包含 ss 元素的优先级队列实例。该优先级队列将按照与 ss 相同的顺序进行排序。当 ss 的元素不能根据 ss 的排序相互比较时，该构造函数抛出 ClassCastException ，当 ss 或其任何元素包含空引用时，该构造函数抛出 NullPointerException 。

清单 9-14 展示了一个优先级队列。

清单 9-14 。将随机生成的整数添加到优先级队列中

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueDemo
{
   public static void main(String[] args)
   {
      Queue<Integer> qi = new PriorityQueue<Integer>();
      for (int i = 0; i < 15; i++)
         qi.add((int) (Math.random() * 100));
      while (!qi.isEmpty())
         System.out.print(qi.poll() + " ");
      System.out.println();
   }
}

创建优先级队列后， PriorityQueueDemo 的主线程向该队列添加 15 个随机生成的整数(范围从 0 到 99)。然后它进入一个 while 循环，重复轮询下一个元素的优先级队列，并输出该元素，直到队列为空。

当您运行这个应用时，它从左到右按数字升序输出一行 15 个整数。例如，我在一次运行中观察到以下输出:

30 43 53 61 61 66 66 67 76 78 80 83 87 90 97

因为当没有更多的元素时， poll() 返回 null，所以我可以将这个循环编码如下:

Integer i;
while ((i = qi.poll()) != null)
   System.out.print(i + " ");

假设您想颠倒上一个示例的输出顺序，使最大的元素出现在左边，最小的元素出现在右边。如清单 9-15 所示，你可以通过将一个比较器传递给适当的优先级队列构造函数来完成这个任务。

清单 9-15 。使用带有优先级队列的比较器

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueDemo
{
   final static int NELEM = 15; // number of elements

   public static void main(String[] args)
   {
      Comparator<Integer> cmp;
      cmp = new Comparator<Integer>()
            {
               @Override
               public int compare(Integer e1, Integer e2)
               {
                  return e2 - e1;
               }
            };
      Queue<Integer> qi = new PriorityQueue<Integer>(NELEM, cmp);
      for (int i = 0; i < NELEM; i++)
         qi.add((int) (Math.random() * 100));
      while (!qi.isEmpty())
         System.out.print(qi.poll() + " ");
      System.out.println();
   }
}

清单 9-15 与清单 9-14 相似，但有一些不同。首先，我声明了一个名为 NELEM 的常量，这样我就可以通过在一个地方指定新值来轻松地改变优先级队列的初始容量和插入到优先级队列中的元素数量。

其次，清单 9-15 声明并实例化了一个匿名类，它实现了比较器。其 compareTo() 方法从元素 e1 中减去元素 e2 ，实现数字降序。编译器通过将 e2 - e1 转换为 E2 . int value()-E1 . int value()来处理 e2 和 e1 的解装箱任务。

最后，清单 9-15 将一个初始容量的 NELEM 元素和实例化的比较器传递给 priority queue(int initial capacity，Comparator <？超 E >比较器)构造器。优先级队列将使用该比较器对这些元素进行排序。

运行这个应用，您将会看到一个由 15 个整数组成的输出行，按照从左到右的降序排列。例如，我观察到这样的输出行:

97 72 70 70 67 64 56 43 36 22 9 5 3 2 1

探索德克

一个队列(发音为 deck)是一个双端队列，其中元素的插入或移除发生在其头或尾。Deques 可以用作队列或堆栈。

Deque ，其泛型为 Deque < E > ，扩展了队列，其中继承的 add(E)E 方法在 Deque 的尾部插入 e 。表 9-6 描述了退出的具体方法。

表 9-6 。特定于队列的方法

如表 9-6 所示，队列声明了访问队列两端元素的方法。提供了插入、移除和检查元素的方法。这些方法中的每一个都以两种形式存在:一个在操作失败时抛出异常，另一个返回特殊值(null 或 false，取决于操作)。后一种形式的插入操作是专门为容量受限的队列实现而设计的；在大多数实现中，插入操作不会失败。

图 9-2 展示了一个来自德克的 Java 文档的表格，该表格很好地总结了插入、移除以及检查头部和尾部的方法的两种形式。

图 9-2 Deque 声明了 12 种方法，用于插入、移除和检查 deque 头部或尾部的元素

当一个队列被用作队列时，您会观察到 FIFO(先进先出)行为。元素被添加到队列的末尾，并从开头移除。从队列接口继承的方法完全等同于表 9-7 中所示的队列方法。

表 9-7 。队列和等效的队列方法

最后，deques 也可以用作 LIFO(后进先出)堆栈。当一个队列被用作堆栈时，元素从队列的开始被推入和弹出。因为堆栈的 push(e) 方法等同于 dequee 的 addFirst(e) 方法，所以它的 pop() 方法等同于 dequee 的 removeFirst() 方法，它的 peek() 方法等同于 dequee 的 peekFirst() 方法

array deque〔t0〕

ArrayDeque 类提供了 Deque 接口的可调整大小的数组实现。它禁止将空元素添加到 deque 中，并且它的迭代器()方法返回失败快速迭代器。

ArrayDeque 提供了三个构造函数:

• 创建一个初始容量为 16 个元素的空数组 Deque。
• ArrayDeque(收藏<？extends E > c) 创建一个数组 deque，包含 c 的元素，按照它们被 c 的迭代器返回的顺序排列。(由 c 的迭代器返回的第一个元素成为 deque 的第一个元素或前面。)当 c 包含空引用时抛出 NullPointerException 。
• 创建一个空数组队列，其初始容量足以容纳 numElements 个元素。当传递给 numElements 的参数小于或等于零时，不会抛出异常。

清单 9-16 展示了一个数组队列。

清单 9-16 。使用数组队列作为堆栈

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeDemo
{
   public static void main(String[] args)
   {
      Deque<String> stack = new ArrayDeque<String>();
      String[] weekdays = { "Sunday", "Monday", "Tuesday", "Wednesday",
                            "Thursday", "Friday", "Saturday" };
      for (String weekday: weekdays)
         stack.push(weekday);
      while (stack.peek() != null)
         System.out.println(stack.pop());
   }
}

ArrayDequeDemo 创建一个队列，用作一个堆栈和一个星期名称数组。然后，它将这些名称压入堆栈并弹出，以相反的顺序输出名称。

当您运行此应用时，它会生成以下输出:

Saturday
Friday
Thursday
Wednesday
Tuesday
Monday
Sunday

探索地图

一个映射是一组键/值对(也称为条目)。因为键标识一个条目，所以一个映射不能包含重复的键。此外，每个键最多只能映射到一个值。映射由 Map 接口描述，该接口没有父接口，其泛型类型为 Map < K，V>T10】(K 为键的类型； V 是值的类型)。

表 9-8 描述了映射的方法。

表 9-8 。地图方法

与列表、集合、队列、地图不扩展集合。但是，可以通过调用 Map 的 keySet() 、 values() 和 entrySet() 方法，将映射视为集合实例，这些方法分别返回键的集合、值的集合和键/值对条目的集合。

注意values()方法返回集合而不是集合，因为多个键可以映射到同一个值，然后 values() 将返回同一个值的多个副本。

由这些方法返回的集合视图(回想一下，集合是集合，因为集合扩展了集合)提供了迭代映射的唯一方法。例如，假设您用三个颜色、红色、绿色和蓝色常量来声明清单 9-17 的颜色枚举。

清单 9-17 。七彩枚举

enum Color
{
   RED(255, 0, 0),
   GREEN(0, 255, 0),
   BLUE(0, 0, 255);

   private int r, g, b;

   private Color(int r, int g, int b)
   {
      this.r = r;
      this.g = g;
      this.b = b;
   }

   @Override
   public String toString()
   {
      return "r = " + r + ", g = " + g + ", b = " + b;
   }
}

以下示例声明了一个由字符串键和颜色值组成的映射，向该映射添加了几个条目，并对键和值进行迭代:

Map<String, Color> colorMap = . . .; // . . . represents the creation of a Map implementation
colorMap.put("red", Color.RED);
colorMap.put("blue", Color.BLUE);
colorMap.put("green", Color.GREEN);
colorMap.put("RED", Color.RED);
for (String colorKey: colorMap.keySet())
   System.out.println(colorKey);
Collection<Color> colorValues = colorMap.values();
for (Iterator<Color> it = colorValues.iterator(); it.hasNext();)
   System.out.println(it.next());

当针对 colorMap 的 hashmap 实现(稍后讨论)运行这段代码时，您应该会看到类似如下的输出:

red
blue
green
RED
r = 255, g = 0, b = 0
r = 0, g = 0, b = 255
r = 0, g = 255, b = 0
r = 255, g = 0, b = 0

前四个输出行标识映射的键；接下来的四个输出行标识地图的值。

entrySet() 方法 返回一个地图的集合。条目对象。这些对象中的每一个都将单个条目描述为一个键/值对，并且是实现映射的类的一个实例。条目接口，其中条目是映射的嵌套接口。表 9-9 描述了地图。条目的方法。

表 9-9。 地图。输入方法

以下示例向您展示了如何迭代上一示例的映射条目:

for (Map.Entry<String, Color> colorEntry: colorMap.entrySet())
   System.out.println(colorEntry.getKey() + ": " + colorEntry.getValue());

当针对前面提到的 hashmap 实现运行这个示例时，您会看到以下输出:

red: r = 255, g = 0, b = 0
blue: r = 0, g = 0, b = 255
green: r = 0, g = 255, b = 0
RED: r = 255, g = 0, b = 0

树图〔t0〕

TreeMap 类提供了一个基于红黑树的 Map 实现。因此，条目按其键的排序顺序存储。然而，访问这些条目比使用其他 Map 实现(没有排序)要慢一些，因为必须遍历链接。

注查看维基百科的“红黑树”词条()了解红黑树。

TreeMap 提供了四个构造函数:

• TreeMap() 创建一个新的、空的树形图，根据其关键字的自然顺序进行排序。所有插入到地图中的键必须实现可比的接口。
• TreeMap(比较器<？super K > comparator) 创建一个新的、空的树形图，根据指定的比较器进行排序。将 null 传递给比较器意味着将使用自然排序。
• TreeMap(地图<？扩展 K，？extends V > m) 创建一个包含 m 条目的新树形图，根据其键的自然排序进行排序。插入新地图的所有键必须实现可比接口。当 m 的键没有实现 Comparable 或者不能相互比较时，这个构造函数抛出 ClassCastException ，当 m 包含空引用时，抛出 NullPointerException 。
• 树形图(SortedMap < K，？extends V > sm) 创建一个新的树形图，包含相同的条目并使用与 sm 相同的排序。(我将在本章后面讨论排序地图。)当 sm 包含空引用时，这个构造函数抛出 NullPointerException 。

清单 9-18 展示了一个树形图。

清单 9-18 。根据基于字符串的键的自然顺序对映射条目进行排序

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo
{
   public static void main(String[] args)
   {
      Map<String, Integer> msi = new TreeMap<String, Integer>();
      String[] fruits = {"apples", "pears", "grapes", "bananas", "kiwis"};
      int[] quantities = {10, 15, 8, 17, 30};
      for (int i = 0; i < fruits.length; i++)
         msi.put(fruits[i], quantities[i]);
      for (Map.Entry<String, Integer> entry: msi.entrySet())
         System.out.println(entry.getKey() + ": " + entry.getValue());
   }
}

创建一个树形图和一个水果名称数组。然后用这些名称填充这个映射，并将映射的条目转储到标准输出。

当您运行此应用时，它会生成以下输出:

apples: 10
bananas: 17
grapes: 8
kiwis: 30
pears: 15

哈希映射

HashMap 类提供了一个基于散列表数据结构的 Map 实现。这个实现支持所有的映射操作，并允许空键和空值。它不保证条目的存储顺序。

一个哈希表在一个哈希函数的帮助下将键映射到整数值。Java 以对象的 hashCode() 方法的形式提供这个函数，类覆盖这些方法以提供适当的哈希代码。

一个哈希代码标识哈希表的数组元素之一，它被称为桶或槽 。对于一些哈希表，桶可以存储与键相关联的值。图 9-3 说明了这种散列表。

图 9-3 。一个简单的哈希表将键映射到存储与这些键相关的值的桶

哈希函数将鲍勃·多伊哈希到 0 ，这标识了第一个桶。这个桶包含账户，这是鲍勃·多伊的雇员类型。散列函数还散列 John Doe 和 Sally Doe 到 1 和 2 (分别)，它们的桶包含销售。

完美的散列函数将每个键散列成一个唯一的整数值。然而，这个理想很难实现。实际上，一些键将散列到相同的整数值。这种不唯一的映射被称为碰撞T2。

为了解决冲突，大多数哈希表将条目的链表与桶相关联。桶不包含值，而是包含链表中第一个节点的地址，每个节点包含一个冲突条目。参见图 9-4 。

图 9-4 。复杂的哈希表将键映射到存储链表引用的桶，链表的节点值是从相同的键散列而来的

当在哈希表中存储值时，哈希表使用哈希函数将键哈希到其哈希代码，然后搜索适当的链表以查看是否存在具有匹配键的条目。如果有条目，它的值会用新值更新。否则，将创建一个新节点，用键和值填充，并附加到列表中。

当从哈希表中检索值时，哈希表使用哈希函数将键哈希到其哈希代码，然后搜索适当的链表以查看是否存在具有匹配键的条目。如果有条目，则返回其值。否则，哈希表可能会返回一个特殊值来指示没有条目，或者可能会引发异常。

桶的数量称为哈希表的容量 。存储条目的数量除以桶的数量的比率被称为哈希表的加载因子 。选择正确的负载系数对于平衡性能和内存使用非常重要:

• 当负载因子接近 1 时，冲突的概率和处理冲突的成本(通过搜索冗长的链表)会增加。
• 当负载因子接近 0 时，散列表的大小随着存储桶数量的增加而增加，而搜索成本几乎没有提高。
• 对于许多哈希表来说，0.75 的加载因子接近最佳值。这个值是散列表的散列表实现的默认值。

HashMap 提供了四个构造函数:

• HashMap() 创建一个新的空 HashMap，初始容量为 16，装载系数为 0.75。
• HashMap(int initial capacity)创建一个新的空 HashMap，其容量由 initialCapacity 指定，负载系数为 0.75。当 initialCapacity 的值小于 0 时，该构造函数抛出 IllegalArgumentException 。
• HashMap(int initialCapacity，float loadFactor) 创建一个新的空 HashMap，其容量由 initialCapacity 指定，负载因子由 loadFactor 指定。当 initialCapacity 小于 0 或 loadFactor 小于或等于 0 时，该构造函数抛出 IllegalArgumentException 。
• HashMap(Map <？扩展 K，？扩展 V > m) 创建一个包含 m 条目的新散列表。当 m 包含空引用时，这个构造函数抛出 NullPointerException 。

清单 9-19 展示了一个散列表。

清单 9-19 。使用 Hashmap 计算命令行参数

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo
{
   public static void main(String[] args)
   {
      Map<String, Integer> argMap = new HashMap<String, Integer>();
      for (String arg: args)
      {
         Integer count = argMap.get(arg);
         argMap.put(arg, (count == null) ? 1 : count + 1);
      }
      System.out.println(argMap);
      System.out.println("Number of distinct arguments = " + argMap.size());
   }
}

HashMapDemo 创建一个由字符串键和整数值组成的 hashmap。每个键都是传递给该应用的命令行参数之一，其值是该参数在命令行中出现的次数。

例如， java HashMapDemo 如果一只土拨鼠能扔木头，它能扔多少木头生成以下输出:

{wood=2, could=2, how=1, if=1, chuck=2, a=2, woodchuck=2, much=1}
Number of distinct arguments = 8

因为 String 类覆盖了 equals() 和 hashCode() ，清单 9-19 可以使用 String 对象作为 hashmap 中的键。当创建一个其实例将用作键的类时，必须确保重写这两个方法。

清单 9-6 向您展示了一个类的覆盖 hashCode() 方法可以调用一个引用字段的 hashCode() 方法并返回它的值，只要该类声明一个引用字段(并且没有原始类型字段)。

更常见的是，类声明多个字段，并且需要一个更好的 hashCode() 方法的实现。实现应该尝试生成最小化冲突的哈希代码。

没有关于如何最好地实现 hashCode() 的规则，各种算法(完成任务的食谱)被创造出来。我最喜欢的算法出现在约书亚·布洛赫(Addison-Wesley，2008；ISBN: 0321356683)。

下面的算法假设存在一个被称为 X 的任意类，该算法与布洛赫的算法 非常相似，但并不相同:

1. 将 int 变量 hashCode (名称任意)初始化为任意非零整数值，比如 19。这个变量被初始化为一个非零值，以确保它考虑散列码为零的任何初始字段。如果你将 hashCode 初始化为 0，那么最终的散列码将不会受到这些字段的影响，并且你会冒增加冲突的风险。
2. 对于也在 X 的 equals() 方法中使用的每个字段 f ，计算 f 的哈希码，并将其分配给 int 变量 hc ，如下所示:
   • a.如果 f 为布尔型，计算 hc = f？1 : 0 。
   • b.如果 f 为字节整数、字符、整数或短整型，则计算 hc = (int) f 。整数值是散列码。
   • c.如果 f 为长整型，则计算 HC =(int)(f ^(f>>>32))。该表达式将长整数的最低有效 32 位与其最高有效 32 位进行异或运算。
   • d.如果 f 为浮点类型，则计算 HC = float . float pointbits(f)。此方法考虑了+无穷大、-无穷大和 NaN。
   • e.如果 f 为双精度浮点类型，则计算 long l = double . doubletolongbits(f)；HC =(int)(l ^(l>>>32))。
   • f.如果 f 为空引用的引用字段，则计算 hc = 0 。
   • g.如果 f 是一个非空引用的引用字段，并且如果 X 的 equals() 方法通过递归调用 equals() 来比较字段(如清单 9-12 的 Employee 类)，则计算 hc = f.hashCode() 。然而，如果 equals() 使用了一个更复杂的比较，创建一个字段的规范(尽可能简单的)表示，并在这个表示上调用 hashCode() 。
   • h.如果 f 是一个数组，通过递归应用该算法并组合 hc 值，将每个元素视为一个单独的字段，如下一步所示。
3. 将 hc 与 hashCode 组合如下: hashCode = hashCode * 31 + hc 。将 hashCode 乘以 31 使得产生的哈希值取决于字段在类中出现的顺序，这在一个类包含多个相似的字段(例如几个 int s)时提高了哈希值。我选择 31 与 String 类的 hashCode() 方法一致。
4. 从 hashCode() 返回 hashCode 。

在第四章，清单 4-7 的点类覆盖了 equals() 但没有覆盖 hashCode() 。我后来展示了一小段代码，它必须附加到 Point 的 main() 方法中，以演示不覆盖 hashCode() 的问题。我在这里重申这个问题:

虽然对象 p1 和 Point(10，20) 在逻辑上是等价的，但是这些对象有不同的 hash 码，导致每个对象引用 hashmap 中不同的条目。如果某个对象没有存储在该条目中(通过 put() )，则 get() 返回 null。

清单 9-20 通过声明一个 hashCode() 方法来修改清单 4-7 的 Point 类。该方法使用上述算法来确保逻辑上等价的点对象散列到相同的条目。

清单 9-20 。覆盖 hashCode()为点对象返回正确的散列码

import java.util.HashMap;
import java.util.Map;

public class Point
{
   private int x, y;

   Point(int x, int y)
   {
      this.x = x;
      this.y = y;
   }

   int getX()
   {
      return x;
   }

   int getY()
   {
      return y;
   }

   @Override
   public boolean equals(Object o)
   {
      if (!(o instanceof Point))
         return false;
      Point p = (Point) o;
      return p.x == x && p.y == y;
   }

   @Override
   public int hashCode()
   {
      int hashCode = 19;
      int hc = x;
      hashCode = hashCode * 31 + hc;
      hc = y;
      hashCode = hashCode * 31 + hc;
      return hashCode;
   }

   public static void main(String[] args)
   {
      Point p1 = new Point(10, 20);
      Point p2 = new Point(20, 30);
      Point p3 = new Point(10, 20);
      // Test reflexivity
      System.out.println(p1.equals(p1)); // Output: true
      // Test symmetry
      System.out.println(p1.equals(p2)); // Output: false
      System.out.println(p2.equals(p1)); // Output: false
      // Test transitivity
      System.out.println(p2.equals(p3)); // Output: false
      System.out.println(p1.equals(p3)); // Output: true
      // Test nullability
      System.out.println(p1.equals(null)); // Output: false
      // Extra test to further prove the instanceof operator's usefulness.
      System.out.println(p1.equals("abc")); // Output: false
      Map<Point, String> map = new HashMap<Point, String>();
      map.put(p1, "first point");
      System.out.println(map.get(p1)); // Output: first point
      System.out.println(map.get(new Point(10, 20))); // Output: null
   }
}

清单 9-20 的 hashCode() 方法有点冗长，因为它将 x 和 y 分别赋给局部变量 hc ，而不是在哈希代码计算中直接使用这些字段。然而，我决定采用这种方法来更好地反映哈希代码算法。

当您运行这个应用时，最感兴趣的是它的最后两行输出。现在，应用在这两行上正确地呈现了第一个点和第一个点以及第一个点，而不是在两行上呈现第一个点和第二个点以及第一个点和空值。

注意 LinkedHashMap 是 HashMap 的子类，它使用链表来存储条目。因此， LinkedHashMap 的迭代器按照条目插入的顺序返回条目。例如，如果清单 9-19 已经指定了 Map < String，Integer>arg Map = new linked hashmap()；，应用对 java 的输出 HashMapDemo 如果一只土拨鼠可以夹住木头土拨鼠可以夹住多少木头 {how=1，much=1，wood=2，could=2，a=2，土拨鼠=2，chuck=2，if=1} 后跟 distinct 参数个数= 8 。

identity yhashmap〔t0〕

IdentityHashMap 类提供了一个映射实现，它在比较键和值时使用引用等式( == )而不是对象等式( equals() )。这故意违反了 Map 的通用契约，该契约要求在比较元素时使用 equals() 。

IdentityHashMap 通过系统的 int identity hashCode(Object x)类方法获取哈希代码，而不是通过每个 key 的 hashCode() 方法。 identityHashCode() 为 x 返回与对象的 hashCode() 方法返回相同的哈希代码，无论 x 的类是否覆盖 hashCode() 。空引用的哈希代码为零。

这些特征赋予了 IdentityHashMap 相对于其他 Map 实现的性能优势。此外， IdentityHashMap 支持可变键(用作键的对象，当它们的字段值在映射中改变时，它们的散列码也会改变)。清单 9-21 对比了 IdentityHashMap 和 HashMap 中的可变键。

清单 9-21 。在可变键上下文中对比身份散列表和散列表

import java.util.IdentityHashMap;
import java.util.HashMap;
import java.util.Map;

public class IdentityHashMapDemo
{
   public static void main(String[] args)
   {
      Map<Employee, String> map1 = new IdentityHashMap<Employee, String>();
      Map<Employee, String> map2 = new HashMap<Employee, String>();
      Employee e1 = new Employee("John Doe", 28);
      map1.put(e1, "SALES");
      System.out.println(map1);
      Employee e2 = new Employee("Jane Doe", 26);
      map2.put(e2, "MGMT");
      System.out.println(map2);
      System.out.println("map1 contains key e1 = " + map1.containsKey(e1));
      System.out.println("map2 contains key e2 = " + map2.containsKey(e2));
      e1.setAge(29);
      e2.setAge(27);
      System.out.println(map1);
      System.out.println(map2);
      System.out.println("map1 contains key e1 = " + map1.containsKey(e1));
      System.out.println("map2 contains key e2 = " + map2.containsKey(e2));
   }
}

class Employee
{
   private String name;
   private int age;

   Employee(String name, int age)
   {
      this.name = name;
      this.age = age;
   }

   @Override
   public boolean equals(Object o)
   {
      if (!(o instanceof Employee))
         return false;
      Employee e = (Employee) o;
      return e.name.equals(name) && e.age == age;
   }

   @Override
   public int hashCode()
   {
      int hashCode = 19;
      hashCode = hashCode * 31 + name.hashCode();
      hashCode = hashCode * 31 + age;
      return hashCode;
   }

   void setAge(int age)
   {
      this.age = age;
   }

   void setName(String name)
   {
      this.name = name;
   }

   @Override
   public String toString()
   {
      return name + " " + age;
   }
}

清单 9-21 的 main() 方法创建了 IdentityHashMap 和 HashMap 实例，每个实例存储一个由雇员键和字符串值组成的条目。因为 Employee 实例是可变的(因为 setAge() 和 setName()),main()改变它们的年龄，而这些键存储在它们的映射中。这些更改会产生以下输出:

{John Doe 28=SALES}
{Jane Doe 26=MGMT}
map1 contains key e1 = true
map2 contains key e2 = true
{John Doe 29=SALES}
{Jane Doe 27=MGMT}
map1 contains key e1 = true
map2 contains key e2 = false

最后四行显示更改的条目保留在它们的映射中。然而， map2 的 containsKey() 方法报告其 HashMap 实例不再包含其 Employee 键(应该是 Jane Doe 27 )，而 map1 的 containsKey() 方法报告其 IdentityHashMap 实例仍然包含其 Employee 键，现在是【T18

注意 IdentityHashMap 的文档指出“这个类的一个典型用途是保持拓扑的对象图转换，比如序列化或深度复制。”(我在第 11 章中讨论了连载。)它还声明“这个类的另一个典型用途是维护代理对象。”还有，stackoverflow 的“Identity HashMap 的用例”主题(http://stack overflow . com/questions/838528/Use-Cases-for-Identity-HashMap)提到，当键是 java.lang.Class 对象时，使用 IdentityHashMap 比 HashMap 快得多。

枚举数

EnumMap 类提供了一个映射实现，它的键是同一个 enum 的成员。不允许空键；任何存储空键的尝试都会导致抛出 NullPointerException 。因为枚举映射在内部表示为数组，所以枚举映射在性能方面接近数组。

EnumMap 提供了以下构造函数:

• enum map(Classkey type)用指定的 keyType 创建一个空的枚举映射。当 keyType 包含空引用时，这个构造函数抛出 NullPointerException 。
• EnumMap(EnumMap < K，？extends V > m) 使用与 m 相同的键类型和 m 的条目创建一个枚举映射。当 m 包含空引用时，这个构造函数抛出 NullPointerException 。
• EnumMap(地图< K，？扩展 V > m) 创建一个用 m 的条目初始化的枚举映射。如果 m 是一个 EnumMap 实例，这个构造函数的行为就像前面的构造函数一样。否则， m 必须包含至少一个条目，以确定新枚举映射的键类型。当 m 包含空引用时，该构造函数抛出 NullPointerException ，当 m 不是 EnumMap 实例且为空时，该构造函数抛出 IllegalArgumentException。

清单 9-22 展示了枚举图。

清单 9-22 。一张硬币常数的枚举图

import java.util.EnumMap;
import java.util.Map;

enum Coin
{
   PENNY, NICKEL, DIME, QUARTER
}

public class EnumMapDemo
{
   public static void main(String[] args)
   {
      Map<Coin, Integer> map = new EnumMap<Coin, Integer>(Coin.class);
      map.put(Coin.PENNY, 1);
      map.put(Coin.NICKEL, 5);
      map.put(Coin.DIME, 10);
      map.put(Coin.QUARTER, 25);
      System.out.println(map);
      Map<Coin,Integer> mapCopy = new EnumMap<Coin, Integer>(map);
      System.out.println(mapCopy);
   }
}

EnumMapDemo 创建一个硬币键和整数值的映射。然后，它将几个硬币实例插入到该地图中，并输出该地图。最后，它创建该地图的副本并输出该副本。

当您运行此应用时，它会生成以下输出:

{PENNY=1, NICKEL=5, DIME=10, QUARTER=25}
{PENNY=1, NICKEL=5, DIME=10, QUARTER=25}

探索排序地图

TreeMap 是一个排序映射的例子，这是一个按照升序维护条目的映射，按照关键字的自然排序或者按照创建排序映射时提供的比较器排序。排序后的地图由 SortedMap 界面描述。

SortedMap (其通用类型为 SortedMap < K，V > )扩展 Map 。除了两个例外，它从映射继承的方法在排序映射上的行为与在其他映射上的行为相同:

• 由任何已排序地图的集合视图上的迭代器()方法返回的迭代器实例按顺序遍历集合。
• 由集合视图的 toArray() 方法返回的数组按顺序包含键、值或条目。

注意尽管没有保证，集合框架中 SortedMap 实现的集合视图的 toString() 方法(例如 TreeMap )返回一个包含所有视图元素的字符串。

SortedMap 的文档要求一个实现必须提供我在讨论树形图时提出的四个标准构造函数。此外，该接口的实现必须实现表 9-10 中描述的方法。

表 9-10。 分类地图的方法

清单 9-23 展示了一个基于树形图的排序图。

清单 9-23 。办公用品名称及数量分类图

import java.util.Comparator;
import java.util.SortedMap;
import java.util.TreeMap;

public class SortedMapDemo
{
   public static void main(String[] args)
   {
      SortedMap<String, Integer> smsi = new TreeMap<String, Integer>();
      String[] officeSupplies =
      {
         "pen", "pencil", "legal pad", "CD", "paper"
      };
      int[] quantities =
      {
         20, 30, 5, 10, 20
      };
      for (int i = 0; i < officeSupplies.length; i++)
          smsi.put(officeSupplies[i], quantities[i]);
      System.out.println(smsi);
      System.out.println(smsi.headMap("pencil"));
      System.out.println(smsi.headMap("paper"));
      SortedMap<String, Integer> smsiCopy;
      Comparator<String> cmp;
      cmp = new Comparator<String>()
                {
                   @Override
                   public int compare(String key1, String key2)
                   {
                      return key2.compareTo(key1); // descending order
                   }
                };
      smsiCopy = new TreeMap<String, Integer>(cmp);
      smsiCopy.putAll(smsi);
      System.out.println(smsiCopy);
   }
}

SortedMapDemo 创建一个排序的地图以及办公用品名称和数量的数组。然后从这些数组开始填充地图。在转储出地图的内容和地图各部分的头部视图后，它以降序创建并输出地图的副本。

当您运行此应用时，它会生成以下输出:

{CD=10, legal pad=5, paper=20, pen=20, pencil=30}
{CD=10, legal pad=5, paper=20, pen=20}
{CD=10, legal pad=5}
{pencil=30, pen=20, paper=20, legal pad=5, CD=10}

探索可导航地图

TreeMap 是导航地图的一个例子，这是一个排序的地图，可以以降序和升序迭代，并且可以报告给定搜索目标的最接近匹配。导航地图由 NavigableMap 接口描述，其通用类型为 NavigableMap < K，V>T8】，扩展了 SortedMap ，如表 9-11 所示。

表 9-11。 导航地图专用方法

表 9-11 的方法描述了表 9-4 中呈现的 NavigableSet 方法的 NavigableMap ，甚至在两个实例中返回 NavigableSet 实例。

清单 9-24 展示了一个基于树形地图的导航地图。

清单 9-24 。在地图上导航(鸟类，在小范围内计数)条目

import java.util.Iterator;
import java.util.NavigableMap;
import java.util.NavigableSet;
import java.util.TreeMap;

public class NavigableMapDemo
{
   public static void main(String[] args)
   {
      NavigableMap<String, Integer> nm = new TreeMap<String, Integer>();
      String[] birds = { "sparrow", "bluejay", "robin" };
      int[] ints = { 83, 12, 19 };
      for (int i = 0; i < birds.length; i++)
         nm.put(birds[i], ints[i]);
      System.out.println("Map = " + nm);
      System.out.print("Ascending order of keys: ");
      NavigableSet<String> ns = nm.navigableKeySet();
      Iterator iter = ns.iterator();
      while (iter.hasNext())
         System.out.print(iter.next() + " ");
      System.out.println();
      System.out.print("Descending order of keys: ");
      ns = nm.descendingKeySet();
      iter = ns.iterator();
      while (iter.hasNext())
         System.out.print(iter.next() + " ");
      System.out.println();
      System.out.println("First entry = " + nm.firstEntry());
      System.out.println("Last entry = "  + nm.lastEntry());
      System.out.println("Entry < ostrich is " + nm.lowerEntry("ostrich"));
      System.out.println("Entry > crow is " + nm.higherEntry("crow"));
      System.out.println("Poll first entry: " + nm.pollFirstEntry());
      System.out.println("Map = " + nm);
      System.out.println("Poll last entry: " + nm.pollLastEntry());
      System.out.println("Map = " + nm);
   }
}

清单 9-24 的 system . out . println(" Map = "+nm)；方法调用依靠 TreeMap 的 toString() 方法来获取可导航地图的内容。

运行该应用时，您会看到以下输出:

Map = {bluejay=12, robin=19, sparrow=83}
Ascending order of keys: bluejay robin sparrow
Descending order of keys: sparrow robin bluejay
First entry = bluejay=12
Last entry = sparrow=83
Entry < ostrich is bluejay=12
Entry > crow is robin=19
Poll first entry: bluejay=12
Map = {robin=19, sparrow=83}
Poll last entry: sparrow=83
Map = {robin=19}

探索数组和集合工具 API

没有它的数组和集合工具类，集合框架将是不完整的。每个类都提供各种类方法，这些方法在集合和数组的上下文中实现有用的算法。

以下是数组类的面向数组的实用方法的示例:

• 静态< T >列表< T > asList (T。。a) 返回一个由数组 a 支持的固定大小的列表。(对返回列表的更改“直写”到数组。)比如 Listbirds = arrays . aslist(" Robin "、" Oriole "、" blue Jay ")；将字符串的三元素数组(回想一下，可变参数序列被实现为数组)转换为列表，其引用被分配给 birds 。
• static int binary search(int[]a，int key) 使用二分搜索法算法在数组 a 中搜索条目键(在下面的列表中解释)。调用此方法之前，必须对数组进行排序；否则，结果是不确定的。此方法返回搜索关键字的索引(如果它包含在数组中)；否则返回(-(插入点)- 1)。插入点是将键插入到数组中的点(第一个元素的索引大于键，或者 a.length 如果数组中的所有元素都小于键)，并且当且仅当找到键时，保证返回值大于或等于 0。例如，arrays . binary search(new String[]{ " Robin "，" Oriole "，" Bluejay"}，" Oriole") 返回 1， "Oriole" 的索引。
• 静态空填充 (char[] a，char ch) 将 ch 存储在指定字符数组的每个元素中。比如 Arrays.fill(screen[i]，' ')；用空格填充 2D 屏幕数组的 i 行。
• 静态 void 排序 (long[] a) 将长整型数组 a 中的元素按数字升序排序，例如 long lArray = new long[] { 20000L，89L，66L，33L }；arrays . sort(lArray)；。
• 静态< T >无效排序 (T[] a，比较器<？超级 T > c) 使用比较器 c 对数组 a 中的元素进行排序。比如当给定比较器<字符串> cmp =新比较器<字符串>(){ @ Override public int compare(String E1，String E2){ return E2 . compare to(E1)；} };String[]内行星= { "水星"、"金星"、"地球"、"火星" }；， Arrays.sort(内行星，CMP)；使用 cmp 帮助将内行星按其元素降序排序:金星、水星、火星、地球就是结果。

在数组中搜索特定元素有两种常见的算法。线性搜索 从索引 0 到被搜索元素的索引或数组的末尾，逐个元素地搜索数组。平均来说，必须搜索一半的元素；更大的数组需要更长的搜索时间。然而，数组不需要排序。

相比之下，二分搜索法 在有序数组 a 的 n 项中搜索元素 e 的时间要快得多。它通过递归执行以下步骤来工作:

1. 将低索引设置为 0。
2. 将高索引设置为 n - 1。
3. 如果低索引>高索引，则打印“无法找到” e 。结束。
4. 将中间指数设置为(低指数+高指数)/ 2。
5. 如果 e > a 【中间指标】，那么将低指标设置为中间指标+ 1。转到第 3 节。
6. 如果 e < a 【中间指标】，那么将高指标设置为中间指标- 1。转到第 3 节。
7. 打印“找到” e “在索引”中间索引。

该算法类似于在电话簿中最优地查找名字。从打开书到正中间开始。如果名字不在那一页上，就把书翻到前半部分或后半部分的正中间，这取决于名字出现在哪一半。重复，直到找到名称(或找不到)。

对 4，000，000，000 个元素应用线性搜索会导致大约 2，000，000，000 次比较(平均)，这需要时间。相比之下，对 4，000，000，000 个元素应用二分搜索法最多可执行 32 次比较。这就是为什么数组包含 binarySearch() 方法，而不包含 linearSearch() 方法。

以下是集合类的面向集合的类方法的示例:

• 静态< T 扩展对象&可比<？超 T > > T min(收藏<？extends T > c) 根据元素的自然排序返回集合 c 的最小元素。例如，system . out . println(collections . min(arrays . aslist(10，3，18，25)))；输出 3 。所有 c 的元素必须实现可比的接口。此外，所有要素必须相互可比。当 c 为空时，该方法抛出 NoSuchElementException 。
• 静态无效反转(列表<？> l) 反转列表 l 的元素顺序。比如 Listbirds = arrays . aslist("知更鸟"、"黄鹂"、"蓝鸟")；Collections.reverse(鸟)；system . out . println(birds)；产生【蓝鸟、黄鹂、知更鸟】作为输出。
• 静态ListsingletonList(T o)返回一个只包含对象 o 的不可变列表。例如，list . remove all(collections . singletonlist(null))；从列表中删除所有空元素。
• 静态Setsynchronized Set(Sets)返回一个由指定 set s 支持的同步(线程安全)Set，例如，Setss = collections . synchronized Set(new HashSet())；。为了保证串行访问，通过返回的集合完成对后台集合( s )的所有访问是非常重要的。
• 静态< K，V >贴图< K，V >不可修改贴图(贴图<？扩展 K，？extends V > m) 返回 map m 不可修改的视图，例如 Map < String，Integer>MSI = collections . unmodifablemap(new HashMap())；。查询操作对返回的地图“通读”到指定的地图；并且试图修改返回的地图，无论是直接修改还是通过其集合视图修改，都会导致 UnsupportedOperationException。

注意由于性能原因，集合实现是不同步的——不同步的集合比同步的集合有更好的性能。但是，要在多线程上下文中使用集合，您需要获得该集合的同步版本。您可以通过调用诸如 synchronizedSet() 这样的方法来获得该版本。

您可能想知道集合类中各种空类方法的用途。例如，static finalListemptyList()返回一个不可变的空列表，如 Listls = collections . emptyList()；。这些方法之所以存在，是因为它们提供了在某些上下文中返回 null(并避免潜在的 NullPointerException s)的有用替代方法。考虑清单 9-25 中的。

清单 9-25 。空无一物的鸟类名单

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

class Birds
{
   private List<String> birds;

   Birds()
   {
      birds = Collections.emptyList();
   }

   Birds(String. . . birdNames)
   {
      birds = new ArrayList<String>();
      for (String birdName: birdNames)
         birds.add(birdName);
   }

   @Override
   public String toString()
   {
      return birds.toString();
   }
}

class EmptyListDemo
{
   public static void main(String[] args)
   {
      Birds birds = new Birds();
      System.out.println(birds);
      birds = new Birds("Swallow", "Robin", "Bluejay", "Oriole");
      System.out.println(birds);
   }
}

清单 9-25 声明了一个 Birds 类，它在一个列表中存储了各种鸟类的名字。这个类提供了两个构造函数:一个无参数构造函数和一个接受可变数量的字符串参数的构造函数，这些参数标识不同的鸟。

noargument 构造函数调用 emptyList() 将其私有的 birds 字段初始化为空的 List 的字符串 — emptyList() 是一个泛型方法，编译器从其上下文中推断其返回类型。

如果你想知道是否需要 emptyList() ，看看 toString() 方法。注意，这个方法计算的是 birds.toString() 。如果您没有将对空列表<字符串> 的引用分配给 birds ， birds 将包含 null (创建对象时此实例字段的默认值)，并且在尝试评估 birds.toString() 时将抛出一个 NullPointerException 实例。

当您运行这个应用( java EmptyListDemo )时，它会生成以下输出:

[]
[Swallow, Robin, Bluejay, Oriole]

emptyList() 方法实现如下:return(List)EMPTY _ List；。该语句返回分配给集合类中 EMPTY_LIST 类字段的单个列表实例。

你可能想直接使用 EMPTY_LIST ，但是如果你这样做的话，你会遇到一个未检查的警告消息，因为 EMPTY_LIST 被声明为原始类型 List ，混合原始和泛型类型会导致这样的消息。虽然您可以取消警告，但是最好使用 emptyList() 方法。

假设您向 Birds 添加了一个 void setBirds(ListBirds)方法，并向该方法传递一个空列表，如 Birds . setBirds(collections . empty List())；。编译器将响应一条错误消息，指出它要求参数的类型为 List < String > ，但参数的类型为 List < Object > 。这样做是因为编译器无法从上下文中找出正确的类型，所以它选择了 List < Object > 。

有一个方法可以解决这个问题，这个方法看起来可能会很奇怪。指定 birds.setBirds(集合。emptyList())；，其中形式类型形参列表及其实际类型实参出现在成员访问操作符之后，方法名之前。编译器现在知道正确的类型参数是字符串，并且 emptyList() 将返回列表<字符串> 。

探索传统集合 API

Java 1.2 引入了集合框架。在 Java 包含框架之前，开发人员在集合方面有两种选择:创建自己的框架，或者使用 Java 1.0 引入的向量、枚举、堆栈、字典、哈希表、属性和位集类型。

Vector 是一个描述可增长数组的具体类，很像 ArrayList 。与 ArrayList 实例不同， Vector 实例是同步的。 Vector 已经被通用化，并且也进行了改进以支持集合框架，这使得诸如 ListList = new Vector()；合法。

集合框架提供了迭代器来迭代集合的元素。相比之下， Vector 的 elements() 方法通过 Enumeration 的 hasmorelements()和 nextElement() 方法返回一个实现 Enumeration 接口的类的实例，用于枚举(迭代并返回)Vector 实例的元素。

Vector 被具体的 Stack 类子类化，它代表一个 LIFO 数据结构。 Stack 提供了一个 E push(E item) 方法用于将一个对象推送到堆栈上，一个 E pop() 方法用于从堆栈顶部弹出一个项目，以及其他一些方法，比如 boolean empty() 用于确定堆栈是否为空。

栈 就是糟糕的 API 设计的一个很好的例子。通过继承 Vector ，可以调用 Vector 的 void add(int index，E element) 方法在任意位置添加一个元素，并破坏 Stack 实例的完整性。事后看来， Stack 在设计时就应该使用 composition:使用一个 Vector 实例来存储一个 Stack 实例的元素。

Dictionary 是将键映射到值的子类的抽象超类。具体的哈希表类是字典的唯一子类。与 Vector 一样，哈希表实例被同步，哈希表被通用化，哈希表被改进以支持集合框架。

Hashtable 由 Properties 子类化，一个具体的类表示一组持久的属性(基于字符串的键/值对，用于标识应用设置)。 Properties 提供了用于存储属性的 Object set property(String key，String value) 和用于返回属性值的 String getProperty(String key)。

注意应用将属性用于各种目的。例如，如果你的应用有一个图形用户界面，你可以通过一个属性对象将它的主窗口的屏幕位置和大小存储在一个文件中，这样应用可以在下次运行时恢复窗口的位置和大小。

属性 是糟糕的 API 设计的另一个很好的例子。通过从哈希表继承，可以调用哈希表的 V put(K key，V value) 方法来存储一个带有非字符串键和/或非字符串值的条目。事后看来， Properties 应该有杠杆合成:在一个 Hashtable 实例中存储一个 Properties 实例的元素。

注意在第四章中，我讨论了包装类，这就是堆栈和属性应该如何实现。

最后，位集 是一个具体的类，它描述了一组可变长度的位。这个类能够表示任意长度的位集，这与之前描述的基于整数的固定长度位集形成对比，固定长度位集的最大成员数受到限制:基于 int 的位集有 32 个成员，基于 long 的位集有 64 个成员。

BitSet 提供了一对构造函数，用于初始化 BitSet 实例: BitSet() 初始化实例，以初始存储依赖于实现的位数，而 BitSet(int nbits) 初始化实例，以初始存储 nbits 位。 BitSet al so 提供了各种方法，包括以下几种:

• void 与 (位集 bs) 对这个位集与 bs 进行按位与运算。修改该位集，使得当它和 bs 中相同位置的位为 1 时，该位被设置为 1。
• void andNot (位集 bs) 将该位集中的所有位设置为 0，其对应的位在 bs 中设置为 1。
• void clear() 将该位集中的所有位设置为 0。
• Object clone() 克隆这个位集，产生一个新的位集。克隆的位设置为 1，与此位集完全相同。
• Boolean get(int bit index)在从零开始的 bitIndex 处，返回该位集的位的值，作为 Boolean true/false 值(true 为 1，false 为 0)。当 bitIndex 小于 0 时，该方法抛出 IndexOutOfBoundsException。
• int length() 返回该位集的“逻辑大小”，即最高 1 位加 1 的索引，如果该位集不包含 1 位，则返回 0。
• void or (位集 bs) 用 bs 对该位集进行按位异或运算。修改该位集，使得当该位或 bs 中相同位置的位为 1 或两个位都为 1 时，该位被设置为 1。
• void set(int bit index，boolean value) 将从零开始的位 bitIndex 设置为值 (true 转换为 1；false 转换为 0)。当 bitIndex 小于 0 时，该方法抛出 IndexOutOfBoundsException。
• int size() 返回该位集用来表示位值的位数。
• String toString() 根据为 1 的位的位置返回该位集的字符串表示，例如 {4，5，9，10} 。
• void xor (位集)用 bs 对该位集进行按位异或运算。修改该位集，使得当该位或 bs 中相同位置的位(但不是两者)为 1 时，该位被设置为 1。

清单 9-26 展示了一个应用，它演示了其中一些方法，并让你更深入地了解按位 AND ( & )、按位异或( | )和按位异或(【^】)运算符是如何工作的。

清单 9-26 。使用可变长度位集

import java.util.BitSet;

public class BitSetDemo
{
   public static void main(String[] args)
   {
      BitSet bs1 = new BitSet();
      bs1.set(4, true);
      bs1.set(5, true);
      bs1.set(9, true);
      bs1.set(10, true);
      BitSet bsTemp = (BitSet) bs1.clone();
      dumpBitset("        ", bs1);
      BitSet bs2 = new BitSet();
      bs2.set(4, true);
      bs2.set(6, true);
      bs2.set(7, true);
      bs2.set(9, true);
      dumpBitset("        ", bs2);
      bs1.and(bs2);
      dumpSeparator(Math.min(bs1.size(), 16));
      dumpBitset("AND (&) ", bs1);
      System.out.println();
      bs1 = bsTemp;
      dumpBitset("        ", bs1);
      dumpBitset("        ", bs2);
      bsTemp = (BitSet) bs1.clone();
      bs1.or(bs2);
      dumpSeparator(Math.min(bs1.size(), 16));
      dumpBitset("OR (|)  ", bs1);
      System.out.println();
      bs1 = bsTemp;
      dumpBitset("        ", bs1);
      dumpBitset("        ", bs2);
      bsTemp = (BitSet) bs1.clone();
      bs1.xor(bs2);
      dumpSeparator(Math.min(bs1.size(), 16));
      dumpBitset("XOR (^) ", bs1);
   }

   static void dumpBitset(String preamble, BitSet bs)
   {
      System.out.print(preamble);
      int size = Math.min(bs.size(), 16);
      for (int i = 0; i < size; i++)
         System.out.print(bs.get(i) ? "1" : "0");
      System.out.print("  size(" + bs.size() + "), length(" + bs.length() + ")");
      System.out.println();
   }

   static void dumpSeparator(int len)
   {
      System.out.print("        ");
      for (int i = 0; i < len; i++)
         System.out.print("-");
      System.out.println();
   }
}

为什么我在 dumpBitset() 中指定了 Math.min(bs.size()，16) ，并传递了一个类似的表达式给 dumpSeparator() ？我想精确地显示 16 位和 16 个破折号(为了美观)，并且需要考虑位集的大小小于 16。虽然这不会发生在 Oracle 和 Google 的位集类上，但它可能会发生在其他变体上。

当您运行此应用时，它会生成以下输出:

       0000110001100000  size(64), length(11)
        0000101101000000  size(64), length(10)
        ----------------
AND (&) 0000100001000000  size(64), length(10)

        0000110001100000  size(64), length(11)
        0000101101000000  size(64), length(10)
        ----------------
OR (|)  0000111101100000  size(64), length(11)

        0000110001100000  size(64), length(11)
        0000101101000000  size(64), length(10)
        ----------------
XOR (^) 0000011100100000  size(64), length(11)

注意与向量和哈希表，位集不同步。当在多线程上下文中使用位集时，必须在外部同步对此类的访问。

集合框架已经使得向量、枚举、栈、字典、哈希表过时。这些类型仍然是标准类库的一部分，以支持遗留代码。此外，首选项 API 使得属性在很大程度上过时了。因为位集仍然相关，所以这个类还在继续改进(最近是 Java 7)。

注意当你意识到可变长度位集的用处时，位集得到改进就不足为奇了。由于其紧凑性和其他优点，变长位集通常用于实现操作系统的优先级队列，并有助于内存页面分配。面向 Unix 的文件系统也使用位集来帮助分配索引节点(信息节点)和磁盘扇区。位集在霍夫曼编码 中很有用，这是一种用于实现无损数据压缩的数据压缩算法。

练习

以下练习旨在测试您对第 9 章内容的理解:

1. 什么是收藏？
2. 什么是集合框架？
3. 集合框架主要由哪些组件组成？
4. 定义可比。
5. 什么时候你会让一个类实现可比的接口？
6. 什么是比较器，它的目的是什么？
7. 是非判断:集合使用比较器来定义其元素的自然排序。
8. Iterable 接口描述了什么？
9. 集合接口代表什么？
10. 确定集合的 add() 方法会抛出 UnsupportedOperationException 类的实例的情况。
11. Iterable 的迭代器()方法返回实现迭代器接口的类的实例。这个接口提供了什么方法？
12. 增强的 for 循环语句的目的是什么？
13. 增强的 for 循环语句是如何表达的？
14. 是非判断:增强的 for 循环适用于数组。
15. 定义自动装箱。
16. 定义 unboxing。
17. 什么是列表？
18. 一个 ListIterator 实例使用什么来导航一个列表？
19. 什么是视图？
20. 为什么要使用 subList() 方法？
21. ArrayList 类提供了什么？
22. LinkedList 类提供了什么？
23. 定义节点。
24. 是非判断: ArrayList 比 LinkedList 提供更快的元素插入和删除。
25. 什么是集合？
26. 树集类提供什么？
27. HashSet 类提供了什么？
28. 是非判断:为了避免 hashset 中的重复元素，您自己的类必须正确地覆盖 equals() 和 hashCode() 。
29. HashSet 和 LinkedHashSet 有什么区别？
30. EnumSet 类提供了什么？
31. 定义排序集。
32. 什么是可导航集合？
33. 是非判断: HashSet 是有序集合的一个例子。
34. 为什么当你试图添加一个元素到一个有序集合时，这个有序集合的 add() 方法会抛出 ClassCastException ？
35. 什么是队列？
36. 是非判断: Queue 的 element() 方法在空队列上被调用时抛出 NoSuchElementException 。
37. PriorityQueue 类提供什么？
38. 什么是地图？
39. TreeMap 类提供什么？
40. HashMap 类提供了什么？
41. 哈希表用什么把键映射到整数值？
42. 继续上一个问题，产生的整数值被称为什么，它们完成什么？
43. 什么是哈希表的容量？
44. 什么是哈希表的加载因子？
45. HashMap 和 LinkedHashMap 有什么区别？
46. IdentityHashMap 类提供了什么？
47. EnumMap 类提供了什么？
48. 定义排序映射。
49. 什么是可导航地图？
50. 是非判断: TreeMap 是一个排序地图的例子。
51. 数组的目的是什么类的静态< T >列表< T > asList(T。。法阵)？
52. 是非判断:二分搜索法比线性搜索慢。
53. 您将使用哪个集合方法来返回 hashset 的同步变体？
54. 识别七种面向遗留集合的类型。
55. 作为数组列表有用性的一个例子，创建一个 JavaQuiz 应用，展示一个关于 Java 特性的基于多项选择的测验。 JavaQuiz 类的 main() 方法首先用 QuizEntry 数组中的条目填充数组列表(例如，new QuizEntry(" Java 的原始名称是什么？"，new String[] { "Oak "，" Duke "，" J "，"以上都不是" }，' A') )。每个条目由一个问题、四个可能的答案和正确答案的字母(A、B、C 或 D)组成。 main() 然后使用数组列表的 iterator() 方法返回一个 Iterator 实例，这个实例的 hasNext() 和 next() 方法对列表进行迭代。每次迭代输出问题和四个可能的答案，然后提示用户输入正确的选择。用户(通过 System.in.read() )输入 A、B、C 或 D 后， main() 输出一条消息，说明用户是否做出了正确的选择。
56. 哈希代码生成算法中为什么用(int)(f ^(f>>>32))代替 (int) (f ^ (f > > 32)) ？
57. 集合提供了静态 int 频率(集合<？> c，对象 o) 方法返回集合 c 元素等于 o 的个数。创建一个 FrequencyDemo 应用，该应用读取其命令行参数，并将除最后一个参数之外的所有参数存储在一个列表中，然后调用 frequency() ，将列表和最后一个命令行参数作为该方法的参数。然后，它输出该方法的返回值(最后一个命令行参数在前面的命令行参数中出现的次数)。例如， java FrequencyDemo 应该输出 null = 0 的出现次数，而 java FrequencyDemo 如果一只土拨鼠会夹木头的话一只土拨鼠能夹多少木头应该输出木头出现次数= 2 。

摘要

集合是一组对象，存储在为此目的而设计的类的实例中。为了使您不必创建自己的集合类，Java 提供了表示和操作集合的集合框架。

集合框架主要由核心接口、实现类以及数组和集合工具类组成。核心接口使得独立于集合的实现来操作集合成为可能。

核心接口包括可迭代、集合、列表、集合、分类集合、导航集合、队列、队列、地图、分类地图、导航地图。集合扩展可迭代；列表、集合，以及队列各自扩展集合；分类设置扩展设置；可导航集合扩展分类集合；队列延伸队列； SortedMap 扩展 Map；导航地图扩展分类地图。

实现类包括 ArrayList ， LinkedList ， TreeSet ， HashSet ， LinkedHashSet ， EnumSet ， PriorityQueue ， ArrayDeque ， TreeMap ， HashMap ， LinkedHashMap 每个具体类的名称都以核心接口名称结尾，标识它所基于的核心接口。

没有它的数组和集合工具类，集合框架是不完整的。每个类都提供各种类方法，在数组和集合的上下文中实现有用的算法。例如，数组让您有效地搜索和排序数组，而集合让您获得同步的和不可修改的集合。

在 Java 1.2 引入集合框架之前，开发人员可以创建自己的框架，或者使用 Java 1.0 引入的向量、枚举、堆栈、字典、哈希表、属性和位集类型。

集合框架已经使得向量、枚举、栈、字典、哈希表过时。此外，首选项 API 使得属性在很大程度上过时了。因为位集仍然相关，所以这个类继续被改进。

在第 10 章的中，我继续探索工具 API，重点是并发工具、日期类、格式化程序类、随机类、扫描程序类等等。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/26096.html