学习目标：掌握Set接口及其实现类HashSet、LinkedHashSet、TreeSet类。

Set接口与HashSet类

Set接口是Collection的子接口。Set接口存放的元素是无序的且不包含重复的对象元素，类似于数学概念的集合，集合中不允许有重复元素。Set接口有三个常用的实现类，分别是HashSet、LinkedHashSet、TreeSet。

HashSet是Set接口实现类之一，使用较为广泛。它存储的对象元素是无序的，并且不允许存储重复的对象元素。也就是当容器中已经存储一个相同的对象元素时，无法再添加一个完全相同的对象元素。

案例13：建立HashSetTest，实例化HashSet对象set，添加String对象到set集合，最后迭代输出set集合的所有String对象。

在collection包下新建HashSetTest类。代码如下：

package collection;
 
import java.util.HashSet;
import java.util.Iterator;
 
public class HashSetTest {
    public static void main(String[] args) {
        // 实例化HashSet对象
        HashSet set = new HashSet();
        // 添加String对象到set集合
        set.add("a");
        set.add("b");
        set.add("c");
        set.add("d");
        set.add("e");
        // 获取set集合的迭代器
        Iterator iter = set.iterator();
        // 循环输出set集合的String对象
        while (iter.hasNext()) {
            String value = (String) iter.next();
            System.out.println(value);
        }
 
    }
}

案例代码实例化了一个HashSet对象，然后通过HashSet的add方法添加String对象，最后通过Iterator迭代器遍历HashSet集合。

运行上述程序，在控制台上显示效果如下图所示：

从输出结果看，HashSet添加的顺序与迭代显示的结果顺序虽然一致，这是set集合存储对象元素过少的原因。HashSet存储的对象元素是无序的，也就是对象元素的添加顺序和输出顺序并不一致。有的同学可能会问，前面学过的数组、集合类ArrayList都与加入对象元素的顺序相关，为什么HashSet与加入的对象元素顺序就无关了呢？

其实，HashSet类是根据元素的哈希码进行存储的，HashSet根据每个存储对象的哈希码值（调用hashCode方法获得），用固定的算法算出它的存储索引，把存储对象存放在一个叫做散列表的相应位置中，如果对应的位置没有其它元素，就只需要直接存入；如果该位置已经有元素了，就会将新对象跟该位置的所有对象进行比较（调用equals（）方法），以查看容器中是否已经存在该对象，若不存在，就存放该对象，若已经存在，就直接使用该对象。

HashSet的存储结构是个链表数组，每一个数组元素就是一个链表，类似这种数据结构称为散列表。上图中左边是数组，用于存储元素，该存储元素对应的数组下标是调用hashCode方法返回的存储元素的哈希码。当后加入元素的哈希码与已经加入的元素哈希码相同时，HashSet就会创建一个链表，将相同哈希码的元素存入一个链表，并将该链表的头指针存储到哈希码对应的数组元素中。

前面的示例只是添加了String对象，如果要添加一个自定义的对象，又该如何呢？

案例14：建立一个Person类，使用HashSet存储Person对象。

在PUnit10项目新建set包，在set包下新建Person类。代码如下：

package set;
 
public class Person {
    private String name;
    private Integer age;
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public Integer getAge() {
        return age;
    }
 
    public void setAge(Integer age) {
        this.age = age;
    }
 
    // 重写父类Object的equal方法
    @Override
    public boolean equals(Object var1) {
        // 测试var1是否是Person类的实例
        if (!(var1 instanceof Person)) {
            return false;
        }
        Person person = (Person) var1;
        if (person.name == null) {
            return false;
        }
        // 判断name是否相等
        return this.name == person.getName();
    }
 
    // 重写hashCode
    @Override
    public int hashCode() {
        return this.name.hashCode();
    }
 
    // 重写toString，为打印方便
    @Override
    public String toString() {
        return "{" + this.name + "," + this.getAge() + "}";
    }
 
}

因为Set集合中不能加入重复的元素，所以对于自定义类，需要提供判断怎样才算重复元素的方法。在例子代码中，hashCode()和equals()方法即是用来判断Person对象是否为重复对象的标准方法。

equals()方法用来比较两个对象是否为相等的对象。在自己实现的equals()方法中，用相关的条件来进行比较。例如对于Person类，这里用name属性进行比较，name属性相同的为相等对象。

hashCode()方法是用来在散列存储结构中确定对象的存储地址的，两个对象的hashCode相同，并不一定表示两个对象就相同，只能够说明这两个对象在散列存储结构中，存储在在同一个链表中。Java初学者可以这样理解，hashCode（）方法实际上返回的就是对象存储的物理地址（实际可能并不是，而是一个与对象相关的值）。 当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。

Set实现类取对象时根据对象和哈希吗值计算出该对象的存储索引，在散列表相应位置上的元素间进行少量的比较操作就可以找到。Set接口存、取、删对象都有很高的效率。

在set包下新建HashSetTest测试类。代码如下：

package set;
 
import java.util.HashSet;
 
public class HashSetTest {
    public static void main(String[] args) {
        // 测试数据
        Person p1 = new Person();
        p1.setName("小明");
        p1.setAge(10);
        Person p2 = new Person();
        p2.setName("小红");
        p2.setAge(20);
        Person p3 = new Person();
        p3.setName("小明");
        p3.setAge(30);
 
        // 测试代码
        HashSet<Person> testSet = new HashSet<Person>();
        testSet.add(p1);
        testSet.add(p2);
        testSet.add(p3);
 
        System.out.println("testSet集合存储的Person对象个数为：" + testSet.size());
        System.out.println(testSet.toString());
 
 
    }
}

程序执行结果如下图所示：

从程序执行结果可以看出，虽然testSet集合添加了3个Person对象，但由于p1对象和p3对象的name相同，equals()方法返回的结果是true，因此p3不能加入testSet集合。

LinkedHashSet类

相对HashSet来说，LinkedHashSet存储结构是一个双向链表，因此它存储的元素是有序的。

LinkedHashSet继承自HashSet，与HashSet唯一的区别是LinkedHashSet内部使用的是LinkHashMap。这样做的意义或者好处就是LinkedHashSet中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的。

LinkedHashSet类支持四个构造函数。第一种构造函数初始化一个空的LinkedHashSet：

LinkedHashSet( )；

第二种构造函数使用Collection元素集初始化LinkedHashSet：

LinkedHashSet(Collection c)

第三种构造函数用给定的容量初始化LinkedHashSet：

LinkedHashSet(int capacity)

第四种构造函数通过传入的容量和填充比初始化LinkedHashSet：

LinkedHashSet(int capacity, float fillRatio)

案例15：建立LinkedHashSetTest测试类，添加String对象到LinkedHashSet集合。

在set包下新建LinkedHashSetTest测试类。代码如下：

package set;
 
import java.util.LinkedHashSet;
 
public class LinkedHashSetTest {
    public static void main(String[] args) {
        // 实例化LinkedHashSet对象
        LinkedHashSet<String> lhs = new LinkedHashSet<>();
        lhs.add("a");
        lhs.add("a");
        lhs.add("a");
        lhs.add("a");
        lhs.add("b");
        lhs.add("c");
        lhs.add("d");
        // 输出lsh集合
        System.out.println(lhs);
 
    }
}

LinkedHashSet 底层采用双向链表实现，可以保证元素的插入顺序，又因为是HashSet的子类，所以插入的元素不能重复。

运行上面的程序，输出结果如下图所示：

从上图可以看出，LinkedHashSet添加了多个内容为“a”的String对象，但只有一个String对象添加成功。另外，元素的输出顺序也和添加元素的顺序一致。

LinkedHashSet需要维护元素的插入顺序，因此性能略低于HashSet的性能，但在迭代访问Set里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。

LinkedHashSet 是 Set 的一个具体实现类，它维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。

如果需要迭代的顺序为插入顺序或者访问顺序，那么 LinkedHashSet 是需要你首先考虑的。

TreeSet类

TreeSet类也是一个有序的集合，TreeSet使用二叉树的原理对加入的元素按照升序或降序排序，该类对新添加的元素都会进行排序，将元素插入到二叉树指定的位置。

TreeSet在实现Set接口基础上，增加了一些用于集合的操作方法，增加的主要方法如下。

● E  first ()

返回当前TreeSet集合的第一个元素，E指Element（元素的英文名称简写）。

● E  last()

返回TreeSet集合的最后一个元素。

● SortedSet<E>  headSet (E toElement)

返回一个新的已排序的TreeSet集合，该集合的元素小于toElement元素。

● SortedSet<E>  subSet (E fromElement, E toElement)

返回一个新的已排序的集合，该集合元素范围从fromElement（包含）到toElement（不包含）。

● SortedSet<E>  tailSet (E fromElement, E toElement)

返回一个新的已排序的集合，该集合中元素大于或等于fromElement。

● Comparator<? super E>  comparator()

返回当前TreeSet集合的排序比较器，如果此集合使用其元素的自然排序，则返回null。

案例16：建立TreeSetTest测试类，添加String对象到TreeSet集合。

在set包下新建TreeSetTest测试类。代码如下：

import java.util.TreeSet;
 
public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<Integer>();
        set.add(9);
        set.add(-2);
        set.add(3);
        set.add(10);
        System.out.println(set);
        // 输出集合中第一个元素
        System.out.println("set.first() = " + set.first());
        // 输出集合中最后一个元素
        System.out.println("set.last() = " + set.last());
        // 返回小于4的子集，不包含4
        System.out.println("set.headSet() = " + set.headSet(4));
        // 返回大于5的子集，包含5
        System.out.println("set.tailSet() = " + set.tailSet(5));
        // 返回大于等于-3，小于4的子集
        System.out.println("set.subSet() = " + set.subSet(-3, 4));
 
 
    }
}

与HashSet集合采用通过hash算法来决定元素的存储位置不同，TreeSet采用二叉树的数据结构来存储集合元素。

程序执行结果如下图所示：

从输出结果可以看出，TreeSet对加入元素默认按照升序进行排序。

TreeSet的排序原理

TreeSet调用对象元素的compareTo方法来比较元素之间的大小关系，然后将元素按升序或降序排列，因此待加入的元素必须实现compareTo方法，并通过compareTo方法比较两个元素内容的大小。

待加入的元素如何实现compareTo方法呢？Java提供了一个Comparable接口，该接口定义了一个compareTo(Object o)方法，用于比较两个元素的大小，并返回一个整数值。需要加入TreeSet集合的元素必须要实现该接口，该接口的实现代码用于比较当前元素与传入元素的大小进行比较，并返回结果。因此实现该接口类的对象就可以比较大小。当一个对象调用该方法与另一个对象进行比较时，该方法就可以返回比较结果。例如：tempObj1.compareTo(obj2)，如果该方法返回0，则代表这两个对象相等；如果该方法返回1，则表明tempObj1大于obj2；如果该方法返回-1，则表明tempObj1小于obj2。

需要加入TreeSet集合的元素必须实现Comparable接口，如果试图把没有实现Comparable接口的类对象加入TreeSet时，程序就会抛出异常。

案例17：建立MyNumber 类，MyNumber没有实现Comparable接口，将MyNumber对象加入TreeSet集合。

在set包下新建MyNumber类。代码如下：

package set;
 
public class MyNumber {
    public int num;
 
    public MyNumber(int innum) {
        num = innum;
    }
 
    public void OutNum() {
        System.out.println("序号：" + num);
    }
 
}

MyNumber为自定义的序号类，该类没有实现Comparable接口。

在set包下新建TreeSetTest1类，添加MyNumber对象到TreeSet集合。代码如下：

package set;
 
import java.util.TreeSet;
 
public class TreeSetTest1 {
    public static void main(String[] args) {
        TreeSet<MyNumber> set = new TreeSet<MyNumber>();
        set.add(new MyNumber(12));
        set.add(new MyNumber(8));
        set.add(new MyNumber(19));
 
    }
}

程序在TreeSetTest1类的main方法中声明了TreeSet集合，并添加MyNumber对象。运行上述代码后，程序抛出错误，如下图所示：

从输出结果可以看出，程序抛出“Exception in thread "main" java.lang.ClassCastException: treesetnum.MyNumber cannot be cast to java.lang.Comparable”异常，意思是MyNumber类没有实现Comparable接口，导致进行元素比较时发生错误。

在上面的案例代码中，TreeSet集合添加了三个MyNumber对象，添加第一个对象时，TreeSet里没有任何元素，所以不会出现任何问题，当添加第二个MyNumber对象时，TreeSet就会调用该对象的compareTo(Object obj)方法与集合中的其他元素进行比较，如果其对应的类没有实现Comparable 接口，则会引发ClassCastException异常。

案例18：建立MyNumber1 类，实现Comparable接口，将MyNumber1对象加入TreeSet集合。

在set包下新建MyNumber1类。代码如下：

package set;
 
public class MyNumber1 implements Comparable{
    public int num;
 
    public MyNumber1(int innum) {
        num = innum;
    }
 
    public void OutNum() {
        System.out.println("序号：" + num);
    }
 
    @Override
    public int compareTo(Object obj) {
        // TODO Auto-generated method stub
        MyNumber1 inMyNumner = (MyNumber1) obj;
        // 大于返回1
        if (this.num > inMyNumner.getNum())
            return 1;
        // 小于返回-1
        if (this.num < inMyNumner.getNum())
            return -1;
        // 相等返回0
        return 0;
    }
 
    public int getNum() {
        return num;
    }
 
    public void setNum(int num) {
        this.num = num;
    }
 
}

MyNumber1类实现了Comparable接口，在compareTo()方法内对传入的MyNumber1和当前对象的num值进行了比较。如果当前num大于传入的num，该方法返回1；如果当前num小于传入的num，该方法返回-1；若相等则返回0。

在set包下新建TreeSetTest2类，添加MyNumber1对象到TreeSet集合。代码如下：

package set;
 
import java.util.Iterator;
import java.util.TreeSet;
 
public class TreeSetTest2 {
    public static void main(String[] args) {
        TreeSet<MyNumber1> set = new TreeSet<MyNumber1>();
        set.add(new MyNumber1(12));
        set.add(new MyNumber1(8));
        set.add(new MyNumber1(19));
 
        // 输出集合元素
        Iterator<MyNumber1> iteror = set.iterator();
        while (iteror.hasNext()) {
            MyNumber1 temp = iteror.next();
            temp.OutNum();
 
        }
 
 
    }
}

程序执行结果如下图所示：

从图中可以看出，修改后的代码可以正常地加入元素，并能对加入的元素进行正确排序。

在实际编程中，需要注意的是放入TreeSet集合中的元素必须是可“排序”的，对加入的元素（自定义类），若要实现compareTo方法，必须实现Comparable接口。在Java  SDK中，已经有一些实现了Comparable接口的类，其中包括String字符串类，还包括Float、Interger、Long、Short、Double等数字类。