31、【JavaSE】【Java 核心类库（上）】集合类-Set

1、概述

• java.util.Set接口是java.util.Collection的子接口，从整个 Java 的集合体系上看，java.util.Set与java.util.List、java.util.Queue是处在同一层级。

• java.util.Set中的元素，首先，与java.util.List不同，是没有先后放入次序的，这里，强调的是没有先后放入次序，并不代表在java.util.Set中的元素是完全无序的，而是这个顺序与元素放入的先后没关系；另外，java.util.Set中的元素是不允许有重复，这也符合数学中对“集合(Set)”的定义。

• 常用的实现java.util.Set的实现类有java.util.HashSet、java.util.TreeSet、java.util.LinkedHashSet。

Set 接口与实现类

• java.util.HashSet类的底层是采用哈希表进行数据管理的。

• java.util.TreeSet类的底层是采用红黑树进行数据管理的。

• java.util.LinkedHashSet类与java.util.HashSet类的不同之处在于在哈希表的基础上，内部维护了一个双向链表，链表中记录了元素的迭代顺序，也就是元素插入集合中的先后顺序，因此便于迭代。

2、HashSet 与 LinkedHashSet

• 在这里仅大概的阐述一下关于这个两个的底层的实现机制，具体的还需要看源码、研究相关的数据结构问题。

• 从下面的代码可以看出，一个是java.util.HashSet中元素的顺序与放入的顺序是无关的；另一个是在Set中不允许出现重复的元素。

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

public class SetTest {

    public static void main(String[] args) {
        Set<String> set = new HashSet<>();

        boolean b1 = set.add("two");
        System.out.println(set); // [two]
        System.out.println(b1); // true

        boolean b2 = set.add("one"); 
        System.out.println(set); // [one, two]
        System.out.println(b2); // true

        boolean b3 = set.add("three");
        System.out.println(set); // [one, two, three]
        System.out.println(b3); // true

        boolean b4 = set.add("two");
        System.out.println(set); // [one, two, three]
        System.out.println(b4); // false
    }

}

• 与java.util.HashSet不同的是java.util.LinkedHashSet使用链表来维护元素的放入顺序，也就是说，使用java.util.LinkedHashSet能够像使用java.util.List一样，放入的顺序是什么，到时候从集合中取出元素的顺序就是什么样的，但是，不允许有重复元素这一点仍然是“硬道理”。

import java.util.LinkedHashSet;
import java.util.Set;

public class SetTest {

    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<>();

        boolean b1 = set.add("two");
        System.out.println(set); // [two]
        System.out.println(b1); // true

        boolean b2 = set.add("one");
        System.out.println(set); // [two, one]
        System.out.println(b2); // true

        boolean b3 = set.add("three");
        System.out.println(set); // [two, one, three]
        System.out.println(b3); // true

        boolean b4 = set.add("two");
        System.out.println(set); // [two, one, three]
        System.out.println(b4); // false
    }

}

• java.util.HashSet的大概机制（实际的情况可能要比这里所说的复杂的多）。首先，先看一下一个哈希表，Hash 表是一个重要的数据结构，其经典的结构如下图：

哈希表经典的结构

首先，图的左侧部分可以理解成一个数组或者是说一个能够通过索引就能快速获取的元素的数据结构；每个索引位置，又都有一个链表。

之所以会有哈希表这样的数据结构，其主要的目的之一是为了提高查询效率。当一个元素放入哈希表之前，首先通过一定的算法，得到一个值，而这个值就是这个元素的索引位置（上图左侧，数组、索引），然而，对于众多的元素，我们不能完全保证通过这样的一套算法，最终得到的值（索引）各不相同，所以说对于得到的索引值相同的元素，就会以链表的形式将其放在对应的索引下。（注：不是完全准确的阐述，大致上是这么一回事）

HashSet元素放入的大体过程

上图所展示了一个元素进入 HashSet 的大致上的过程，实际情况，包括底层的数据结构以及相关的计算要比这个要复杂一些。再次重申，这里的流程是一个大体的流程。

尽管，上面的流程不是十分严格，但是，还是有一些问题需要大家关注的。

1、hashCode方法
这个方法是著名的java.lang.Object类中的方法。

我们知道，对于面向对象的思想而言，“万事万物皆对象”，对于任何一种数据结构而言，处理不仅仅是简简单单的数字，而是需要有能力处理对象。

大家从上面可以看到，对于像哈希表这样的一种数据结构，它需要先得到出一个数组索引的东西，但是，一个学生、一间教师这样的对象，是不会凭空、无依据的转化成为一个数字的，所以，只能通过hashCode的方法来为这个转化提供最原始的依据。

2、hashCode方法与equals方法
这个两个方法，都是java.lang.Object的方法。

并且，Java 中一个最基本的原则就是，如果两个对象使用equals所得到的结果为 true，那么两个对象，调用hashCode方法得到的结果也必须是一致的。所以，就有了要求一个类如果重写了equals方法，那么，就必须重写hashCode方法来保证基本原则。

但是，这个基本原则为什么要这样定或者说基于这样的原则能够干什么，在 HashSet 这里，可以看到想要的答案。

Set 的特点是，不能存在重复的对象等，而判断重复的依据是equals方法，但是，对于像数组这样的数据结构而言，放入元素的时候，判断是否重复，是需要经过遍历的，效率很低。但对于像哈希表这样的数据结构而言，暂且不需要通过遍历来判断是否重复，而是先通过hashCode方法得到的值以及一套算法获取到一个索引，判断是否重复，只需判断与当前这个索引下的已有的元素是否相等即可（当前索引下无任何元素，也不用判断！）。

判断两个对象通过hashCode方法得到值转换成索引过程中的一个中间值否相等，如果这两个中间值不相等，即认定新元素与当前元素不重复；
如果相等，新元素再调用equals方法，如果结果是true则最终认定新元素与该索引下的一个原有元素相等，构成重复元素；结果是false则认定与当前比较的那个已有元素不重复。

当该索引下所有的元素与新元素经过上面的步骤后，才可以得到最后的结论，所以，最终遍历只需要发生在某一索引下，而不是对集合中已有的全部元素进行遍历！

(如果认为此处有些啰嗦，请看上图中所给出例子！)

好，经过上面的对这一过程大致上的阐述，就能明白如果hashCode方法与equals方法得到的结论不一致的后果。

/**
 * 学生类
 * 
 * equals：学号相同即对象相等
 * hashCode：调用 name 的 hashCode 方法
 */
public class Student {

    // 学号
    private String id;

    // 姓名
    private String name;

    public Student() {
    }

    public Student(String id, String name) {
        this.id = id;
        this.name = name;
    }

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Student) {
            Student o = (Student) obj;
            return this.id.equals(o.getId());
        } else {
            return false;
        }
    }

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

    @Override
    public String toString() {
        return "Student{" +
                "id='" + id + '\'' +
                ", name='" + name + '\'' +
                '}';
    }

}

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

public class SetTest {

    public static void main(String[] args) {
        Set<Student> set = new HashSet<>();

        Student s1 = new Student("1001", "张三");
        Student s2 = new Student("1001", "李四");

        System.out.println(s1.equals(s2)); // true

        set.add(s1);
        set.add(s2);
        System.out.println(set); // [Student{id='1001', name='李四'}, Student{id='1001', name='张三'}]
    }

}

上面的代码，就是展示了一种hashCode方法与equals方法得到的结论不一致的情形。一般认为，学号是学生的在学校内的唯一标志，一个学号只能对应一个学生，所以两个学号相同的对象，完全有理由作为相等的对象看待。但是，在这里的hashCode方法，与equals方法的得到的结论不同。最终导致在 Set 中有两个元素。

3、TreeSet

• java.util.TreeSet也是java.util.Set的接口的一个比较重要的实现类。但是与java.util.HashSet以及java.util.LinkedHashSet不同，其底层的数据结构是红黑树。

• 对于java.util.TreeSet还有一点要注意的，一般情况下，是不允许在java.util.TreeSet中存 null 的，否则会抛出java.lang.NullPointerException异常。而对于java.util.HashSet和java.util.LinkedHashSet是允许存 null 的。

• 关于什么是红黑树，这里并不展开详细讲解，但是有几个最基本的东西要弄清。

1、二叉树
简单来讲，二叉树就是每一个节点最多拥有两个节点的树。

二叉树的基本概念

2、有序二叉树
当然也有一些其他的名称。侧重点在“有序”上，也就是说，对于以有序二叉树这样的一个数据结构来处理对象的时候，对象与对象之间必须是可比较的或者拥有比较的依据，最终才能达到“有序”的目的。

一般这个有序的规则是：
a、左子树中的任意节点元素都小于根节点元素值；
b、右子树中的任意节点元素都大于根节点元素值；
c、所有的左子树、右子树的内部也必须遵守上述规则；

有序二叉树的基本概念

3、红黑树
暂时不解释，但是有个关系要理清楚，红黑树是一种特殊的有序二叉树。

• java.util.TreeSet的底层是红黑树（特殊的有序二叉树），所以，当一个元素要放入 TreeSet 的时候，必然有一个放入“位置”的问题，也就是说，这个元素到底该位于这个树结构的什么位置上。 而“位置”的确定的必须的前提条件就是放入树中的元素具有可比性。而在 Java 中，对象之间的可比性（比较大小）的实现，除了之前使用equals方法来判断相等之外，在 TreeSet 中等场合所参考的是下面的两种：

比较元素大小的规则有两种方式：

1、使用元素的自然排序规则进行比较并排序，让元素类实现java.lang.Comparable接口。

2、使用比较器规则进行比较并排序，构造 TreeSet 集合时传入java.util.Comparator接口的参数。

• java.util.TreeSet对于java.lang.String的处理，通过这个来初步认识一下自然排序。

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

public class SetTest {

    public static void main(String[] args) {
        Set<String> set = new TreeSet<>();

        set.add("aa");
        set.add("ab");
        set.add("b");
        set.add("ac");
        set.add("z");
        set.add("abd");

        System.out.println(set); // [aa, ab, abd, ac, b, z]
    }

}

如果之前有了解过计算机中字符串比较的一般规则，相信看到输出并不惊讶。可以看到，TreeSet 默认就是“从小到大”排序，当然，java.lang.String已经提供好了自然排序的规则，即java.lang.String类实现了java.lang.Comparable的接口，否则，也无法完成排序。

// java.lang.Comparable 源码
public interface Comparable<T> {
    public int compareTo(T o);
}

// java.lang.String 源码
public final class String implements java.io.Serializable, Comparable<String>, CharSequence {

    ······

    public int compareTo(String anotherString) {
        byte v1[] = value;
        byte v2[] = anotherString.value;
        if (coder() == anotherString.coder()) {
            return isLatin1() ? StringLatin1.compareTo(v1, v2)
                              : StringUTF16.compareTo(v1, v2);
        }
        return isLatin1() ? StringLatin1.compareToUTF16(v1, v2)
                          : StringUTF16.compareToLatin1(v1, v2);
     }

     ······
}

• 自定义类的自然排序规则。前面讲到了java.lang.String类通过实现java.lang.Comparable接口（该接口为泛型接口），从而“制定”了自然排序规则，那么对于要放入 TreeSet 的其他元素，同样需要其对应类实现这一接口，并重写其要求的compareTo方法。

这个compareTo方法，方法的签名是public int compareTo(T o)，其返回值是int类型。

1、当返回值为0时，表示当前对象（调用该方法的对象）与参数对象o相等。
2、当返回值为正数时（一般取1即可），表示当前对象“大于”参数对象o。
3、当返回值为负数时（一般取-1即可），表示当前对象“小于”参数对象o。

总结一下，这个返回值相当于“拿当前对象减去参数对象”。

往 TreeSet 中所添加的新元素是当前对象，而集合中已有的元素是参数对象o！

public class Student implements Comparable<Student> {

    private String id;
    private String name;

    public Student() {
    }

    public Student(String id, String name) {
        this.id = id;
        this.name = name;
    }

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

    @Override
    public int compareTo(Student o) {
        // 当前对象 小于 参数的对象
        // 意味着新放入 TreeSet 的元素，比已经放在 TreeSet 中的元素小
        // 最终的结果是，集合中的元素顺序与放入的顺序是相反的
        return -1;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Student) {
            Student o = (Student) obj;
            return this.id.equals(o.getId());
        } else {
            return false;
        }
    }

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

    @Override
    public String toString() {
        return "Student{" +
                "id='" + id + '\'' +
                ", name='" + name + '\'' +
                '}';
    }

}

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

public class SetTest {

    public static void main(String[] args) {
        Set<Student> set = new TreeSet<>();

        set.add(new Student("1003", "张三"));
        set.add(new Student("1001", "李四"));
        set.add(new Student("1009", "王五"));

        System.out.println(set); 
        // 根据自然排序规则，新放入的元素都比之前放入的元素小
        // [Student{id='1009', name='王五'}, Student{id='1001', name='李四'}, Student{id='1003', name='张三'}]
    }

}

public class Student implements Comparable<Student> {

    ······

    // 当前对象 大于 参数的对象
    // 意味着新放入 TreeSet 的元素，比已经放在 TreeSet 中的元素大
    // 最终的结果是，集合中的元素顺序与放入的顺序是一致的
    @Override
    public int compareTo(Student o) {
        return 1;
    }

    ······

}

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

public class SetTest {

    public static void main(String[] args) {
        Set<Student> set = new TreeSet<>();

        set.add(new Student("1003", "张三"));
        set.add(new Student("1001", "李四"));
        set.add(new Student("1009", "王五"));

        System.out.println(set);
        // [Student{id='1003', name='张三'}, Student{id='1001', name='李四'}, Student{id='1009', name='王五'}]
    }

}

• 利用比较器规则进行排序。在创建java.util.TreeSet的过程中，传入一个比较器对象的参数，从而制定比较规则。自然排序的规则比较单一，而比较器的规则比较多元化，而且比较器优先于自然排序。

public class Student {

    private String id;
    private String name;

    public Student() {
    }

    public Student(String id, String name) {
        this.id = id;
        this.name = name;
    }

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Student) {
            Student o = (Student) obj;
            return this.id.equals(o.getId());
        } else {
            return false;
        }
    }

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

    @Override
    public String toString() {
        return "Student{" +
                "id='" + id + '\'' +
                ", name='" + name + '\'' +
                '}';
    }

}

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

public class SetTest {

    public static void main(String[] args) {

        Comparator<Student> comparator = new Comparator<>() {
            // o1 表示即将增加的元素、o2 表示集合中已有的元素
            // 返回正数，说明 o1 大于 o2
            // 返回负数，说明 o1 小于 o2
            // 返回0，说明 o1 与 o2 相等

            // 此处，按照学生的学号，由小到大在集合中排序
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getId().compareTo(o2.getId());
            }
        };

        Set<Student> set = new TreeSet<>(comparator);

        set.add(new Student("1003", "张三"));
        set.add(new Student("1001", "李四"));
        set.add(new Student("1009", "王五"));

        System.out.println(set);
        // [Student{id='1001', name='李四'}, Student{id='1003', name='张三'}, Student{id='1009', name='王五'}]
    }

}

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

public class SetTest {

    public static void main(String[] args) {

        // 使用 Lamba 表达式简化这个“比较器”代码
        Comparator<Student> comparator = (o1, o2) -> o1.getId().compareTo(o2.getId());

        Set<Student> set = new TreeSet<>(comparator);

        set.add(new Student("1003", "张三"));
        set.add(new Student("1001", "李四"));
        set.add(new Student("1009", "王五"));

        System.out.println(set);
    }

}