Set接口及其实现类

1. Set接口介绍

java.util.Set 接口和 java.util.List 接口一样，同样继承自 Collection 接口，它与Collection 接口中的方法基本一致，并没有对 Collection 接口进行功能上的扩充，只是比Collection 接口更加严格了。

与 List 接口不同的是， Set 接口中元素无序，并且都会以某种规则保证存入的元素不出现重复。

Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法。

Set集合取出元素的方式可以采用：迭代器、增强for。

Set 集合有多个子类，这里我们介绍其中的 java.util.HashSet 、 java.util.LinkedHashSet、java.util.TreeSet 这三个集合。

2. Set接口的主要实现类

2.1 HashSet集合☆

java.util.HashSet 是 Set 接口的一个典型实现类，它所存储的元素是不可重复的，集合元素可以为null，线程不安全，并且元素都是无序的(即存取顺序不能保证不一致)。

HashSet 是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存储和查找性能。保证元素唯一性的方式依赖于：hashCode 与 equals 方法。即两个对象通过 hashCode() 方法比较相等，并且两个对象的 equals() 方法返回值也相等。

对于存放在Set容器中的对象， 对应的类一定要重写equals() 和hashCode(Object obj) 方法，以实现对象相等规则。即： “相等的对象必须具有相等的散列码” 。

java.util.HashSet 底层的实现其实是一个 java.util.HashMap 支持。

哈希值和哈希表

哈希值简介：是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。

如何获取哈希值：Object类中的public int hashCode()；返回对象的哈希码值。

哈希值的特点：

同一个对象多次调用hashCode()方法返回的哈希值是相同的。

默认情况下，不同对象的哈希值是不同的。而重写hashCode()方法，可以实现让不同对象的哈希值相同。

什么是哈希表呢？哈希表是HashSet集合存储数据的结构

在JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。

而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

底层也是数组，初始容量为16，当如果使用率超过0.75，（16*0.75=12）就会扩大容量为原来的2倍。（16扩容为32，依次为64,128….等）。

简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下图所示：

1563700294020

HashSet中添加元素的过程

当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象hashCode 值，然后根据 hashCode 值，通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置。（这个散列函数会与底层数组的长度相计算得到在数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，该散列函数设计的越好）

如果两个元素的hashCode()值相等，会再继续调用equals方法，如果equals方法结果为true，添加失败；如果为false，那么会保存该元素，但是该数组的位置已经有元素了，那么会通过链表的方式继续链接。

重写 hashCode() 方法的基本原则

在程序运行时，同一个对象多次调用 hashCode() 方法应该返回相同的值。

当两个对象的 equals() 方法比较返回 true 时，这两个对象的 hashCode()方法的返回值也应相等。

对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。

重写 equals() 方法的基本原则

以自定义的Student类为例，何时需要重写equals()？

当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候，总是要改写hashCode()，根据一个类的equals方法（改写后），两个截然不同的实例有可能在逻辑上是相等的，但是，根据Object.hashCode()方法，它们仅仅是两个对象。

因此，违反了“相等的对象必须具有相等的散列码”。

结论：复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode 的对象的属性也应该参与到equals()。

HashSet存储自定义类型元素☆

给HashSet中存放自定义类型元素时，需要重写对象中的hashCode和equals方法，建立自己的比较方式，才能保证HashSet集合中的对象唯一。

/**
*创建自定义Student类
*/
public class Student {
    private String name;
    private int age;
    public Student() {
    }
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Student student = (Student) o;
        return age == student.age &&
            Objects.equals(name, student.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

public class HashSetDemo {
    public static void main(String[] args) {
        
        //创建集合对象 该集合中存储 Student类型对象
        HashSet<Student> stuSet = new HashSet<Student>();
        //存储
        Student stu = new Student("于谦", 43);
        stuSet.add(stu);
        stuSet.add(new Student("郭德纲", 44));
        stuSet.add(new Student("于谦", 43));
        stuSet.add(new Student("郭麒麟", 23));
        stuSet.add(stu);
        for (Student stu2 : stuSet) {
            System.out.println(stu2);
        }
    }
}

执行结果：

Student [name=郭德纲, age=44]

Student [name=于谦, age=43]

Student [name=郭麒麟, age=23]

Objects.hash(name, age);执行细节如下：

public static int hash(Object... values) {
       return Arrays.hashCode(values);
   }
       
   public static int hashCode(Object a[]) {
       if (a == null)
           return 0;

       int result = 1;

       for (Object element : a)
           result = 31 * result + (element == null ? 0 : element.hashCode());

       return result;
   }

LinkedHashSet集合☆

我们知道HashSet保证元素唯一，可是元素存放进去是没有顺序的，那么我们要保证有序，怎么办呢？在HashSet下面有一个子类java.util.LinkedHashSet ，它是链表和哈希表组合的一个数据存储结构。

LinkedHashSet 是 HashSet 的子类。

LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。

LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。

LinkedHashSet 不允许集合元素重复。

2.2 TreeSet集合

TreeSet 是 SortedSet 接口的实现类，TreeSet 可以确保集合元素处于排序状态。

TreeSet底层使用红黑树结构存储数据。

可以将元素按照规则进行排序。

TreeSet()：根据其元素的自然排序进行排序。

TreeSet(Comparator comparator) ：根据指定的比较器进行排序。

特点：

有序，查询速度比List快。

排序—自然排序

自然排序：TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序(默认情况)排列。

如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable接口。

实现 Comparable 的类必须实现 compareTo(Object obj) 方法，两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。

Comparable 的典型实现：

BigDecimal、BigInteger 以及所有的数值型对应的包装类：按它们对应的数值大小进行比较。

Character：按字符的 unicode值来进行比较。

Boolean：true 对应的包装类实例大于 false 对应的包装类实例。

String：按字符串中字符的 unicode 值进行比较。

Date、Time：后边的时间、日期比前面的时间、日期大。

向 TreeSet 中添加元素时，只有第一个元素无须比较compareTo()方法，后面添加的所有元素都会调用compareTo()方法进行比较。

因为只有相同类的两个实例才会比较大小，所以向 TreeSet 中添加的应该是同一个类的对象。

对于 TreeSet 集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过 compareTo(Object obj) 方法比较返回值。

当需要把一个对象放入 TreeSet 中，重写该对象对应的 equals() 方法时，应保证该方法与compareTo(Object obj) 方法有一致的结果：如果两个对象通过equals() 方法比较返回 true，则通过 compareTo(Object obj) 方法比较应返回 0。否则，让人难以理解。

排序—定制排序

TreeSet的自然排序要求元素所属的类实现Comparable接口，如果元素所属的类没有实现Comparable接口，或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序，则考虑使用定制排序。

定制排序，通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。

利用int compare(T o1,T o2)方法，比较o1和o2的大小：

如果方法返回正整数，则表示o1大于o2；

如果返回0，表示相等；

返回负整数，表示o1小于o2。

要实现定制排序，需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。

此时，仍然只能向TreeSet中添加类型相同的对象，否则发生ClassCastException异常。

使用定制排序判断两个元素相等的标准是：通过Comparator比较两个元素返回了0。

☆

本文作者: DuanChaojie

本文链接: http://www.itbuild.cn/2020/12/19/JavaSE-%E9%9B%86%E5%90%88/6.Set%E6%8E%A5%E5%8F%A3%E5%8F%8A%E5%85%B6%E5%AE%9E%E7%8E%B0%E7%B1%BB/