Trail: Collections
Lesson: Interfaces

Set 接口

Set 是不能包含重复元素的 Collection。它模拟了数学集抽象。Set 接口仅包含从 Collection 继承的方法，并添加了禁止重复元素的限制。Set 还为 equals 和 hashCode 操作的行为添加了更强的契约，允许比较 Set 实例即使它们的实现类型不同也有意义。如果两个 Set 实例包含相同的元素，则它们是相等的。

Java 平台包含三个通用 Set 实现：HashSet，TreeSet 和 LinkedHashSet。HashSet，将其元素存储在哈希表中，是性能最佳的实现；但它不能保证迭代的顺序。TreeSet，将其元素存储在红黑树中，根据其值对其元素进行排序；它比 HashSet 慢得多。LinkedHashSet，作为哈希表实现，其中有链表贯穿其中，根据它们插入集合的顺序对其元素进行排序（插入顺序）。LinkedHashSet 使客户端免受 HashSet 提供的未指定的、通常是混乱的排序的影响，其成本仅稍高一些。

这是一个简单但有用的 Set 习惯用法。假设你有一个 Collection，c，并且你想要创建另一个包含相同元素的 Collection，但会删除所有重复项。下面的一行就可以了。

Collection<Type> noDups = new HashSet<Type>(c);

它的工作原理是创建一个 Set(根据定义，它不能包含重复项)，最初包含 c 中的所有元素。它使用 The Collection Interface 部分中描述的标准转换构造函数。

或者，如果使用 JDK 8 或更高版本，你可以使用聚合操作轻松收集到 Set：

c.stream()
.collect(Collectors.toSet()); // no duplicates

这是一个稍长的示例，它将 Collection 的名称累积到 TreeSet 中：

Set<String> set = people.stream()
.map(Person::getName)
.collect(Collectors.toCollection(TreeSet::new));

以下是第一个习惯用法的次要变体，它在移除重复元素时保留了原始集合的顺序：

Collection<Type> noDups = new LinkedHashSet<Type>(c);

以下是封装前面的习惯用法的泛型方法，返回与传递的相同泛型类型的 Set。

public static <E> Set<E> removeDups(Collection<E> c) {
    return new LinkedHashSet<E>(c);
}

Set 接口基本操作

size 操作返回 Set(其 cardinality (基数))中的元素数。isEmpty 方法完全按照你的想法执行。add 方法将指定的元素添加到 Set(如果它尚不存在)并返回一个布尔值，指示是否添加了元素。类似地，remove 方法从 Set 中移除指定的元素(如果存在)并返回指示元素是否存在的布尔值。iterator 方法在 Set 上返回一个 Iterator。

以下 program 打印出其参数列表中的所有不同单词。提供了该程序的两个版本。第一个使用 JDK 8 聚合操作。第二个使用 for-each 结构。

使用 JDK 8 聚合操作：

import java.util.*;
import java.util.stream.*;

public class FindDups {
    public static void main(String[] args) {
        Set<String> distinctWords = Arrays.asList(args).stream()
		.collect(Collectors.toSet()); 
        System.out.println(distinctWords.size()+ 
                           " distinct words: " + 
                           distinctWords);
    }
}

使用 for-each 结构：

import java.util.*;

public class FindDups {
    public static void main(String[] args) {
        Set<String> s = new HashSet<String>();
        for (String a : args)
               s.add(a);
               System.out.println(s.size() + " distinct words: " + s);
    }
}

现在运行该程序的任一版本。

java FindDups i came i saw i left

生成以下输出：

4 distinct words: [left, came, saw, i]

请注意，代码始终通过其接口类型(Set)而不是其实现类型引用 Collection。这是 strongly (强烈) 推荐的编程实践，因为它使你可以灵活地仅通过更改构造函数来更改实现。如果用于存储集合的变量或用于传递它的参数被声明为 Collection 的实现类型而不是其接口类型，则必须更改 所有的 此类变量和参数的才能更改其实现类型。

此外，无法保证生成的程序能够正常运行。如果程序使用原始实现类型中存在但未在新实现类型中存在的任何非标准操作，则程序将失败。仅通过其接口引用集合可防止你使用任何非标准操作。

前面示例中 Set 的实现类型是 HashSet，它不保证 Set 中元素的顺序。如果希望程序按字母顺序打印单词列表，只需将 Set 的实现类型从 HashSet 更改为 TreeSet。进行这个简单的单行更改会导致前一个示例中的命令行生成以下输出。

java FindDups i came i saw i left

4 distinct words: [came, i, left, saw]

Set 接口批量操作

批量操作特别适合 Set;应用时，它们执行标准的集合代数运算。假设 s1 和 s2 是 set。以下是批量操作的作用：

s1.containsAll(s2) 如果 s2 是 s1 的 subset (子集)，则返回 true。(s2 是 s1 的子集，如果 set s1 包含 s2 中的所有元素。)
s1.addAll(s2) 将 s1 转换为 s1 和 s2 的 union (并集)。(两个集合的并集是包含任一集合中包含的所有元素的集合。)
s1.retainAll(s2) 将 s1 转换为 s1 和 s2 的交集。(两个集合的交集是仅包含两个集合共有的元素的集合。)
s1.removeAll(s2) 将 s1 转换为 s1 和 s2 的(不对称)集合差异（译注：应该也称为相对补集）。(例如，s1 减去 s2 的集合差异是包含 s1 中但不包含在 s2 中的所有元素)。

要 nondestructively (非破坏性地) (不修改任何一个集合)计算两个集合的并集，交集或集合差异，调用者必须在调用适当的批量操作之前复制一个集合。以下是由此产生的习惯用法。

Set<Type> union = new HashSet<Type>(s1);
union.addAll(s2);

Set<Type> intersection = new HashSet<Type>(s1);
intersection.retainAll(s2);

Set<Type> difference = new HashSet<Type>(s1);
difference.removeAll(s2);

前面的习惯用法中的结果 Set 的实现类型是 HashSet，正如已经提到的那样，它是 Java 平台最好的全面 Set 实现。但是，可以替换任何泛型的 Set 实现。

让我们重温一下 FindDups 程序。假设你想知道参数列表中的哪些单词只出现一次，哪些出现多次，但你不希望重复打印任何重复项。这种效果可以通过生成两组来实现。一个包含参数列表中的每个单词，另一个只包含重复项。仅出现一次的单词是这两组的集合差异，我们知道如何计算。这是 the resulting program 的展示。


import java.util.*;

public class FindDups2 {
    public static void main(String[] args) {
        Set<String> uniques = new HashSet<String>();
        Set<String> dups    = new HashSet<String>();

        for (String a : args)
            if (!uniques.add(a))
                dups.add(a);

        // Destructive set-difference
        uniques.removeAll(dups);

        System.out.println("Unique words:    " + uniques);
        System.out.println("Duplicate words: " + dups);
    }
}

当使用前面使用的相同参数列表运行时(i came i saw i left)，程序产生以下输出。

Unique words:    [left, saw, came]
Duplicate words: [i]

不太常见的集合代数运算是 symmetric set difference (对称集合差异) 两个指定集合中包含的元素集，但不包含在两个集合中。以下代码非破坏性地计算两个 set 的对称集合差异。

Set<Type> symmetricDiff = new HashSet<Type>(s1);
symmetricDiff.addAll(s2);
Set<Type> tmp = new HashSet<Type>(s1);
tmp.retainAll(s2);
symmetricDiff.removeAll(tmp);

Set 接口数组操作

对于 Set 数组操作，与其他任何 Collection 的数组操作相比，不会执行任何特殊操作。这些操作在 The Collection Interface 部分中描述。