第十三章《集合》第3节：Set集合

Set也是Collection的子接口，它定义了另一种形式的集合，专业上称之为Set集合。Set集合的特点如图13-9所示。

图13-9 Set类型集合

从图13-9可以看出：Set类型的集合就像是一个装苹果的筐子，程序员只要把元素存入这个筐子即可。集合中的元素像是胡乱堆积在一起，因此元素没有索引，而程序员也无法通过索引找到某个元素。Set集合与Collection基本相同，它没有定义更多的方法，但Collection并不要求集合中的元素不能相同，而Set则要求集合中的元素必须不同。如果试图把两个相同的元素加入同一个Set集合中，则添加操作会失败，add()方法返回false，新元素也不会被加入集合。Set接口的常用实现类有HashSet、TreeSet以及EnumSet，它们都符合Set集合的最基本特征。

13.3.1 HashSet类

HashSet 是Set接口的典型实现类，程序员使用Set集合时大多数都会选用这个实现类。HashSet按Hash算法来存储集合中的元素，因此具有很好的存取和查找性能。

HashSet具有以下特点：

1. 不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化
2. HashSet 不是同步的，如果多个线程同时访问一个HashSet，假设有两个或者两个以上线程同时修改了HashSet集合时，则必须通过代码来保证其同步
3. 集合中允许有空元素null存在

当向HashSet集合中存入一个元素时，HashSet 会调用该对象的 hashCode()方法来得到该对象的hashCode值，然后根据该hashCode值决定该对象在HashSet中的存储位置。如果有两个元素通过equals()方法比较返回true，但它们的 hashCode()方法返回值不相等，HashSet将会把它们存储在不同的位置，因此元素依然可以成功添加到HashSet集合中。由此可见，HashSet集合判断两个元素相等的标准是：两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也要相等。下面的【例13_05】展示了HashSet保存元素时对元素是否相同的判断标准。

【例13_05 HashSet保存元素】

Exam13_05.java

import java.util.HashSet;
class A{
    public boolean equals (Object obj){
        return  true;
    }
}
 
class B{
    public int hashCode(){
        return 1;
    }
}
 
class C{
    public boolean equals (Object obj){
        return  true;
    }
 
    public int hashCode(){
        return 2;
    }
}
 
public class Exam13_05 {
    public static void main(String[] args) {
        HashSet set = new HashSet();
        set.add(new A());
        set.add(new A());
        set.add(new B());
        set.add(new B());
        set.add(new C());
        set.add(new C());
        System.out.println(set);
    }
}

【例13_05】的Exam13_05.java文件中定义了四个类，其中A、B、C都是元素的类型。可以看到：A类中重写了equals()方法，并且使方法始终返回true，这样A类的对象与任何一个对象做比较的结果都是true，B类重写了hashCode()方法并使方法返回1，这样任何两个B类对象的hashCode()值都是相等的，C类重写了equals()和hashCode()两个方法，并且使它们的返回值分别是true和2，按照HashSet对元素相同的判断标准：对象调用equals()方法返回true并且对象的hashCode()方法返回值相同，这两个对象就是相同的，因此任何两个C类对象都会被HashSet认为是相同的对象。程序中分别添加了A、B、C类的两个对象，之后打印HashSet集合，程序运行结果如图13-10所示。

图13-10【例13_05】运行结果

从图13-10可以看出：由于任何两个C类对象都是相同的，所以虽然两次调用add()方法向集合中加入C类对象，但最终集合中只有一个C类对象。此外还可以看出：对象加入集合中的顺序与对象在集合中排列的顺序并不相同。

HashSet中每个能存储元素的“槽位”通常被称为“桶”，如果有多个元素的hashCode值相同，但它们通过equals()方法比较返回false，就需要在一个桶里放多个元素，这样会导致性能下降，因此存入HashSet集合中的元素要尽量避免其hashCode值相同。

为最大程度的避免元素的hashCode值相同，程序员可以重写hashCode()方法。重写hashCode()时需要注意以下几个原则：

1. 在程序运行过程中，同一个对象多次调用hashCode()方法应该返回相同的值
2. 当两个对象通过equals()方法比较返回true时，两个对象的hashCode()方法应返回相等的值
3. 对象中用作equals()方法比较标准的属性，都应该用于计算 hashCode值

在第11章所介绍的Objects类中所定义的hash()方法就能够帮助程序员重写hashCode()方法，只要把类中的属性值都作为hash()方法的参数即可，例如：

class Person{
    String name;//姓名
    int age;//年龄
    char sex;//性别
    //重写hashCode()方法
    public int hashCode(){
        return Objects.hash(name,age,sex);
    }
}

以上代码中，以Objects类的hash()方法的返回值作为哈希码，在产生哈希码时把Person类的name、age、sex三个属性都当作hash()方法的参数，这样就能够最大程度的避免哈希码的重复。当程序把可变对象添加到 HashSet中之后，尽量不要去修改该集合元素中参与计算hashCode()、equals()的属性，否则将会导致HashSet无法正确访问这些集合元素。

List类型的集合可以通过索引去遍历所有元素，而Set类型的集合并没有索引，因此根本无法通过索引遍历所有元素。为解决这个问题，Java语言允许使用迭代器遍历元素。迭代器的工作原理与流很相似，也有一个指针，但迭代器的指针最初在第一个元素之前，使用hasNext()方法判断集合中是否还有未访问的元素，如果有的话，使用next()方法把指针移动到下一个元素并获取下一个元素。Collection接口中定义了一个iterator()方法用以产生一个迭代器，因此所有List、Set和Queue类型的集合都拥有这个方法。方法所产生的迭代器属于Iterator类型，实际上Iterator是一个接口，iterator()方法所产生的迭代器是它的实现类接口。下面的【例13_06】展示了如何使用迭代器遍历Set类型的集合。

【例13_06 使用迭代器遍历Set集合】

Exam13_06.java

import java.util.*;
public class Exam13_06 {
    public static void main(String[] args) {
        HashSet set = new HashSet();
        set.add("Java");
        set.add("Python");
        set.add("C++");
        Iterator it = set.iterator();//产生迭代器
        while (it.hasNext()){
            System.out.println(it.next());//遍历集合中的元素
        }
    }
}

【例13_06】的运行结果如图13-11所示。

图13-11【例13_06】运行结果

从图13-11可以看出：使用迭代器能够遍历Set集合中的所有元素，但遍历的顺序与元素加入集合的顺序未必相同。

13.3.2 LinkedHashSet类

HashSet还有一个子类叫做LinkedHashSet，LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置，但它同时使用链表维护元素的次序，这样使得元素看起来是以插入的顺序保存的。也就是说，当遍历LinkedHashSet集合里的元素时，LinkedHashSet将会按元素的添加顺序来访问集合里的元素。

LinkedHashSet需要维护元素的插入顺序，因此性能略低于HashSet 的性能，但在迭代访问Set里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。虽然LinkedHashSet使用了链表记录集合元素的添加顺序，但 LinkedHashSet依然是HashSet，因此它依然不允许集合元素重复。下面的【例13_07】能够很好的展示LinkedHashSet集合的特性。

【例13_07 LinkedHashSet的使用】

Exam13_07.java

import java.util.*;
public class Exam13_07 {
    public static void main(String[] args) {
        LinkedHashSet set = new LinkedHashSet();
        set.add("Java");
        set.add("Python");
        set.add("C++");
        set.add("C++");//重复加入"C++"
        Iterator it = set.iterator();//产生迭代器
        while (it.hasNext()){
            System.out.println(it.next());//遍历集合中的元素
        }
    }
}

【例13_07】的运行结果如图13-12所示。

图13-12【例13_07】运行结果

从图13-12可以看出：集合中元素的顺序与它们加入集合中的顺序完全相同。

13.3.3 TreeSet类

TreeSet是SortedSet接口的实现类，正如SortedSet名字所暗示的，TreeSet可以确保集合元素处于排序状态。与HashSet集合相比，TreeSet还提供了几个额外的方法，如表13-4所示。

表13-4 TreeSet类的方法

正因为TreeSet中的元素是有序的，所以增加了访问第一个、前一个、后一个、最后一个元素的方法，并提供了三个从TreeSet中截取子TreeSet的方法，但读者必须清楚：这些访问都不是通过索引完成的。下面的【例13_08】展示了TreeSet集合的特性。

【例13_08 TreeSet的使用】

Exam13_08.java

import java.util.TreeSet;
public class Exam13_08 {
    public static void main(String[] args) {
        TreeSet nums = new TreeSet();
        nums.add(5);
        nums.add(2);
        nums.add(10);
        nums.add(-9);
        System.out.println("整个集合："+nums);
        System.out.println("集合中的第一个元素："+nums.first());
        System.out.println("集合中的最后一个元素："+nums.last());
        System.out.println("集合中小于5的元素："+nums.headSet(5));//①
        System.out.println("集合中小于等于5的元素："+nums.headSet(5,true));//②
        System.out.println("集合中大于等于5的元素："+nums.tailSet(5));//③
        System.out.println("集合中大于5的元素："+nums.tailSet(5,false));//④
        System.out.println("集合中位于区间[2,10)的元素"+ nums.subSet(2,10));//⑤
        System.out.println("集合中位于区间[2,10]的元素"+nums.subSet(2,true,10,true));//⑥
    }
}

【例13_08】的运行结果如图13-13所示。

图13-13【例13_08】运行结果

从图13-13可以看出：TreeSet会按照元素从小到大的顺序自动对元素进行排序。语句①中调用headSet()方法时给方法传递的参数是5，所得到的结果中并不包含5，但语句③使用tailSet()方法时所传递的参数也是5，所得到的结果中却包含5，这个细节一定不能忽略。如果希望语句①的计算能包含参数5在内，则需要另外添加一个表示包含关系的参数true，就是语句②的写法，同理，语句④中添加了表示不包含关系的参数false，就能使得参数5不被包含到计算结果中。语句⑤在计算子集时，只会包含前面数值较小的参数，而不会包含后面数值较大的参数，如果希望对包含关系做出改变需要像语句⑥那样用boolean型参数指出是否包含两个元素。

与HashSet集合采用hash算法来决定元素的存储位置不同，TreeSet 采用红黑树的数据结构来存储集合元素。那么TreeSet进行排序的规则是怎样的呢？TreeSet支持两种排序方法：自然排序和定制排序，在默认情况下，TreeSet采用自然排序。TreeSet会调用集合元素的compareTo()方法来比较元素之间的大小关系，然后将集合元素按升序排列，这种方式就是自然排序。

在第11章中曾经介绍过：compareTo()方法定义在Comparable接口中，它用来定义比较规则，而比较规则的确立最终是为了完成排序。TreeSet能够完成对元素自动排序的操作就是因为元素实现了Comparable接口从而有了比较规则，如果一个类没有实现Comparable接口，那么它的对象就不能进入TreeSet集合，如果强行把这样的对象加入TreeSet集合就会引发ClassCastException。此外还需注意：大部分类在实现compareTo()方法时，都需要将被比较对象obj强制类型转换成相同类型，因为只有相同类的两个对象才会比较大小。当试图把一个对象添加到TreeSet集合时，TreeSet会调用该对象的compareTo()方法与集合中的其他元素进行比较，这就要求集合中的其他元素与该元素是同一个类的对象。因此，向TreeSet中添加的应该是同一个类的对象，否则也会引发ClassCastException异常。保证同一种类型的对象被加入集合的最好办法当然是在创建对象时使用泛型限制元素类型，例如：

TreeSet nums = new TreeSet();

当把一个对象加入TreeSet集合中时，TreeSet 调用该对象的compareTo()方法与容器中的其他对象比较大小，然后根据红黑树结构找到它的存储位置。如果两个对象通过compareTo()方法比较相等，新对象将无法添加到 TreeSet集合中。因此，对于TreeSet集合而言，它判断两个元素是否相等的唯一标准是：两个元素通过compareTo()方法比较是否返回0，如果通过compareTo()方法比较返回0，则TreeSet会认为它们相等，否则就认为它们不相等。下面的【例13_09】展示了TreeSet集合如何判断元素是否相等。

【例13_09 TreeSet集合判断元素相等】

Exam13_09.java

import java.util.TreeSet;
class Z implements Comparable{
    public int compareTo(Object o) {
        return 1;
    }
}
 
public class Exam13_09 {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        Z z = new Z();
        set.add(z);
        set.add(z);//连续两次加入同一个对象
        System.out.println("集合中的元素个数："+set.size());
    }
}

【例13_09】的Exam13_09.java文件中包含两个类，其中Z类实现了Comparable接口，并在实现compareTo()方法时让方法始终返回1，main()方法中让同一个z对象连续两次加入TreeSet集合后打印集合的元素个数。【例13_09】的运行结果如图13-14所示。

图13-14【例13_09】运行结果

从图13-14可以看出：同一个对象被连续两次加入同一个TreeSet集合，之所以认为同一个对象是不相同的，就是因为对象的compareTo()方法没有返回0。

如果向TreeSet中添加一个可变类的对象后，在后面的程序中修改了该可变对象的属性，这可能导致它与其他对象的大小顺序发生了改变，但TreeSet不会再次调整它们的顺序，甚至可能导致TreeSet 中保存的这两个对象通过compareTo()方法比较返回0，出现了重复元素同事存在于一个Set的现象，因此为了让程序更加健壮，尽量不要修改放入Set集合中元素的属性值。

TreeSet 的自然排序是根据集合元素的大小，将它们按照从小到大的顺序升序排列。如果需要实现定制排序，例如以降序排列，则可以通过借助于Comparator 接口实现。Comparator接口在第11章中已经介绍过，它包含一个int compare(T o1, T o2)方法，该方法用于比较o1和o2的大小，如果该方法返回正整数，则表明o1大于o2;如果该方法返回0，则表明o1等于o2;如果该方法返回负整数，则表明o1小于o2。如果需要实现定制排序，则需要在创建TreeSet集合对象时，提供一个Comparator对象与该TreeSet集合关联，由该Comparator对象负责集合元素的排序逻辑。下面的【例13_10】展示了如何使用Comparator接口完成在TreeSet集合中对元素从大到小的降序排列。

【例13_10 实现TreeSet集合的定制排序】

Exam13_10.java

import java.util.*;
class IntegerComparator implements Comparator{
    public int compare(Integer i1,Integer i2){
        //按降序方式指定两个对象的比较标准
        if(i1
            return 1;
        }else if(i1>i2){
            return -1;
        }else{
            return 0;
        }
    }
}
 
public class Exam13_10 {
    public static void main(String[] args) {
        TreeSet set = new TreeSet(new IntegerComparator());
        set.add(1);
        set.add(5);
        set.add(-3);
        System.out.println(set);
    }
}

【例13_10】的Exam13_10.java文件中包含两个类，其中IntegerComparator实现了Comparator接口，这个类在实现compare()方法时按照降序排列的规则定义了返回值。main()方法在创建TreeSet类对象时以IntegerComparator类的对象作为参数，这样的话TreeSet就能以IntegerComparator所定义的排序规则对元素进行排序。【例13_10】的运行结果如图13-15所示。

图13-15【例13_10】运行结果

从图13-15可以看出：TreeSet集合中的元素按照规定的降序方式排列。

13.3.4 EnumSet类

EnumSet是一个专为枚举类设计的集合类，EnumSet 中的所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建EnumSet时显式或隐式地指定。EnumSet 的集合元素也是有序的，EnumSet以枚举值在 Enum类内的定义顺序来决定集合元素的顺序。EnumSet对象占用内存很小，而且运行效率很高，尤其是进行批量操作如调用containsAll()和retainAll()这样的方法。EnumSet集合不允许加入空元素null，如果试图加入null，EnumSet将抛出 NullPointerException异常，相应的如果调用remove()方法删除null，方法的返回值必然是false。

EnumSet没有提供公开的构造方法，因此不能通过调用构造方法的形式创建它的对象。通常情况下，程序员都是调用EnumSet类的静态方法获得对象，下面的表13-5展示了获得EnumSet类对象的静态方法。

表13-5 获得EnumSet对象的静态方法

EnumSet类自身定义的非静态方法仅有一个clone()方法，这个方法用来返回一个当前集合对象的副本，由此可见：EnumSet类并没被定义为有特殊功能的集合，它只是专门用来存放枚举值。下面的【例13_11】展示了以各种方式创建EnumSet对象的过程。

【例13_11 EnumSet集合的创建】

Exam13_11.java

import java.util.*;
enum Week{
    Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday
}
 
public class Exam13_11 {
    public static void main(String[] args) {
        Collection c = new HashSet();
        Week[] values = Week.values();
        for (Week w:values){//以循环的形式把枚举值存入集合
            c.add(w);
        }
 
        //创建包含所有Week枚举的EnumSet集合
        EnumSet es1 = EnumSet.allOf(Week.class);
        //以c创建EnumSet集合
        EnumSet es2 = EnumSet.copyOf(c);
        //用指定的几个枚举值创建EnumSet集合
        EnumSet es3 = EnumSet.of(Week.Saturday,Week.Friday,Week.Sunday);
        //以es3所不包含的枚举值创建EnumSet集合
        EnumSet es4 = EnumSet.complementOf(es3);
        //创建从Tuesday到Friday范围内所有枚举值组成的EnumSet集合
        EnumSet es5 = EnumSet.range(Week.Tuesday,Week.Friday);
        System.out.println("es1："+es1);
        System.out.println("es2："+es2);
        System.out.println("es3："+es3);
        System.out.println("es4："+es4);
        System.out.println("es5："+es5);
    }
}

【例13_11】的运行结果如图13-16所示。

图13-16【例13_11】运行结果

13.3.5 各种Set集合性能分析

HashSet和TreeSet是Set接口的两个典型实现类，通常情况下HashSet的性能总是比TreeSet好，特别是最常用的添加、查询元素等操作，这是因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时，才应该使用TreeSet，否则都应该使用HashSet。

HashSet 还有一个子类:LinkedHashSet，对于普通的插入、删除操作，LinkedHashSet 比 HashSet要略微慢一点，这是因为维护链表所带来的额外开销造成的。但由于有了链表，遍历LinkedHashSet 会更快。

EnumSet是所有Set实现类中性能最好的，但它只能保存同一个枚举类的枚举值作为集合元素。必须指出的是，Set的三个实现类HashSet、TreeSet和 EnumSet都是线程不安全的。如果有多个线程同时访问一个Set集合，并且有超过一个线程修改了该Set集合，则必须手动保证该Set集合的同步性。通常可以通过Collections工具类的synchronizedSortedSet()方法保证Set集合的同步性，Collections类的知识将在13.6小节中进行讲解。

除阅读文章外，各位小伙伴还可以点击这里观看我在本站的视频课程学习Java！