Java集合（三）之Set

水深无声 2022-05-24 14:09 210阅读 0赞

## 一、Set接口 ##

#### 1.1 Set集合概述 ####

Set集合：它类似于一个罐子，程序可以依次把多个对象 “丢进” Set 集合，而 **Set 集合通常不能**  
**记住元素的添加的顺序，也就是说Set 集合是无序的**。  
Set 集合与 Colleaction 基本相同，没有提供额外的方法，实际上 Set 就是 Collection，只是  
行为略有不同（Set 不允许包含重复元素）。

#### 1.2 Set类型集合特点 ####

集合中的元素不可重复，无索引，有没有序要看Set接口具体的实现类是谁。  
Set接口常见的实现类有:HashSet、LinkedHashSet。

*  HashSet集合中元素的特点 :**无序不可重复**
 *  LinkedHashSet集合中元素的特点:**有序不可重复**

## 二、HashSet ##

#### 2.1 HashSet概述 ####

Set 接口的典型实现类，HashSet是基于HashMap实现，大多数时候使用 Set 集合时就是使用  
这个实现类。**HashSet 按 Hash 算法来存储集合中的元素**，因此具有很好的存取和查找性能。  
**数据结构是哈希表**。**线程是非同步的**。

#### 2.2 HashSet特点 ####

*  **不能保证元素的排列顺序**，顺序可能和添加的顺序不同，顺序也有可能发生变化。
 *  **HashSet不是同步的**，如果多个线程同时来访问一个 HashSet，假设有两个或者两个以上线程  
    同时修改了HashSet 集合时，则必须通过代码来保证其同步。
 *  **集合元素值可以是 null**

#### 2.3 HashSet如何保证元素唯一性的原理 ####

当我们想要创建一个集合，该集合里面的元素都具有唯一性时。会遇到两种情况：  
**1）元素为String类型**  
元素为String类型，可以直接用Hashset集合来创建。  
String类重写了hashCode()和equals()方法，所以，它就可以把内容相同的字符串去掉，只留下一个。

**2）元素为自定义对象类型**  
![uUO65Sh.png][]

**3）HashSet保证元素唯一性的原理**

*  我们使用Set集合都是需要去掉重复元素的,*\* 如果在存储的时候逐个equals()比较, 效率较低,\**  
    **哈希算法提高了去重复的效率, 降低了使用equals()方法的次数**。
 *  当**HashSet调用add()方法存储对象的时候**, 先**调用对象的hashCode()方法得到一个哈希值,**  
    然后**在集合中查找是否有哈希值相同的对象**。
 *  如果**没有哈希值相同的对象就直接存入集合**。
 *  如果有**哈希值相同的对象, 就和哈希值相同的对象逐个进行equals()比较,比较结果为**  
    **false就存入, true则不存**。

**4）将自定义类的对象存入HashSet去重复**  
类中必须重写hashCode()和equals()方法

*  hashCode(): 属性相同的对象返回值必须相同, 属性不同的返回值尽量不同(提高效率)
 *  equals(): 属性相同返回true, 属性不同返回false,返回false的时候存储。

在开发中并不要我们去写，比如使用eclipse开发中，在类上面 Alt+Shift+s ，再点h，就能生成  
相对应的重写的hashCode()和equls()方法了。那我们就来分析一下，该怎么写的。

细说hashCode()和equals()方法：

/*
        注意：这里是一个Student类：里面有name和age属性。
         * 为什么是31?
         * 1,31是一个质数,质数是能被1和自己本身整除的数
         * 2,31这个数既不大也不小
         * 3,31这个数好算,2的五次方-1,2向左移动5位
         */
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + age;
            result = prime * result + ((name == null) ? 0 : name.hashCode());
            return result;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)                        //调用的对象和传入的对象是同一个对象
                return true;                        //直接返回true
            if (obj == null)                        //传入的对象为null
                return false;                        //返回false
            if (getClass() != obj.getClass())        //判断两个对象对应的字节码文件是否是同一个字节码
                return false;                        //如果不是直接返回false
            Person other = (Person) obj;            //向下转型
            if (age != other.age)                    //调用对象的年龄不等于传入对象的年龄
                return false;                        //返回false
            if (name == null) {                        //调用对象的姓名为null
                if (other.name != null)                //传入对象的姓名不为null
                    return false;                    //返回false
            } else if (!name.equals(other.name))    //调用对象的姓名不等于传入对象的姓名
                return false;                        //返回false
            return true;                            //返回true
        }

## 三、LinkedHashSet ##

#### 3.1 LinkedHashSet概述 ####

*  LinkedHashSet是HashSet的子类，LinkedHashSet 集合也是**根据元素的 hashCode 值来决定**  
    **元素的存储位置，但它同时使用链表维护元素的次序**，这样使得元素看起来是以插入的顺序保存的。  
    也就是说，当遍历 LinkedHashSet 将会按照添加元素顺序来访问集合里的元素。
 *  LinkedHashSet是通过**用一个链表的实现来扩展HashSet**，从而支持了对HashSet中的元素的排序。  
    所以LinkedHashSet可以按照元素插入时的顺序进行提取。
 *  LinkedHashSet **需要维护元素的插入顺序，因此性能略低于 HashSet 的性能**，但在迭代访问 Set里  
    的全部元素时将有很好的性能，因为它以链表来维护内部顺序。**虽然 LinkedHashSet 使用了链表记录集**  
    **合元素的添加顺序，但 LinkedhasHSet依然是 HashSet,因此它依然不允许集合元素重**复。
 *  LinkedHashSet\*\*只能按照先后顺序来进行排序**，TreeSet则是按照**比较器给的比较规则进行从小到大排\*\*  
    **序**。其实现也就是借助于TreeMap。

#### 3.2 LinkedHashSet的特点 ####

*  保证元素唯一
 *  可以保证怎么存就怎么取

#### 3.3 SortedSet接口与TreeSet类 ####

SortedSet接口是Set接口的子接口,除了拥有Set集合的一些基本特点之外,还提供了排序的功能。  
TreeSet类就是SortedSet接口的实现类。

## 四、TreeSet ##

#### 4.1 TreeSet概述 ####

**1）TreeSet继承与实现关系**

*  TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。它**继承于AbstractSet抽象类，实现了**  
    **NavigableSet, Cloneable, java.io.Serializable接口。**
 *  TreeSet 继承于AbstractSet，所以它是一个Set集合，具有Set的属性和方法。
 *  TreeSet 实现了NavigableSet接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。
 *  TreeSet 实现了Cloneable接口，意味着它能被克隆。
 *  TreeSet 实现了java.io.Serializable接口，意味着它支持序列化。

TreeSet是**基于TreeMap实现的**。**TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建**  
**TreeSet 时提供的 Comparator （比较器排序）进行排序**。这取决于使用的构造方法。  
TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。  
另外，TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。

**2）存储对象**  
TreeSet存储对象的时候, 可以排序, 但是需要指定排序的算法。  
Integer能排序(有默认顺序), String能排序(有默认顺序), 自定义的类存储的时候出现异常(没有顺序)。

*  在类上implement Comparable
 *  重写compareTo()方法
 *  在使用TreeSet存储对象的时候, add()方法内部就会自动调用compareTo()方法进行比较,  
    根据比较结果使用二叉树形式进行存储

**3）TreeSet的构造方法**

// 默认构造函数。使用该构造函数，TreeSet中的元素按照自然排序进行排列。
    　　TreeSet()
    
    　　// 创建的TreeSet包含collection
    　　TreeSet(Collection<? extends E> collection)
    
    　　// 指定TreeSet的比较器
    　　TreeSet(Comparator<? super E> comparator)
    
    　　// 创建的TreeSet包含set
    　　TreeSet(SortedSet<E> set)

**4）TreeSet与Collection的关系**  
![6wRPay3.png][]

*  TreeSet继承于AbstractSet，并且实现了NavigableSet接口.
 *  TreeSet的本质是一个”**有序的，并且没有重复元素”的集合，它是通过TreeMap实现的**。
 *  TreeSet中含有一个”NavigableMap类型的成员变量”m，而m实际上是”TreeMap的实例”。

#### 4.2 TreeSet原理 ####

**1）特点**  
 TreeSet是用来排序的, 可以指定一个顺序, 对象存入之后会按照指定的顺序排列.  
**2）使用方式**

*  自然顺序(Comparable)  
    TreeSet类的add()方法中会把存入的对象提升为Comparable类型  
    调用对象的compareTo()方法和集合中的对象比较  
    根据compareTo()方法返回的结果进行存储
 *  比较器顺序(Comparator)  
    创建TreeSet的时候可以制定 一个Comparator  
    如果传入了Comparator的子类对象, 那么TreeSet就会按照比较器中的顺序排序  
    add()方法内部会自动调用Comparator接口中compare()方法排序  
    调用的对象是compare方法的第一个参数,集合中的对象是compare方法的第二个参数
 *  两种方式的区别  
    TreeSet构造函数什么都不传, 默认按照类中Comparable的顺序(没有就报错ClassCastException)  
    TreeSet如果传入Comparator, 就优先按照Comparator

#### 4.3 图解TreeSet的排序原理 ####

**1）用例分析**  
我们创建了一个Person类和一个测试类TreeSetDemo类  
Person类:

package com.zyh.domain;
    
    public class Person {
        
        private String name;
        private int age;
    
        public Person(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;
        }
    
        /*
         * 为什么是31?
         * 1,31是一个质数,质数是能被1和自己本身整除的数
         * 2,31这个数既不大也不小
         * 3,31这个数好算,2的五次方-1,2向左移动5位
         */
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + age;
            result = prime * result + ((name == null) ? 0 : name.hashCode());
            return result;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)                        //调用的对象和传入的对象是同一个对象
                return true;                        //直接返回true
            if (obj == null)                        //传入的对象为null
                return false;                        //返回false
            if (getClass() != obj.getClass())        //判断两个对象对应的字节码文件是否是同一个字节码
                return false;                        //如果不是直接返回false
            Person other = (Person) obj;            //向下转型
            if (age != other.age)                    //调用对象的年龄不等于传入对象的年龄
                return false;                        //返回false
            if (name == null) {                        //调用对象的姓名为null
                if (other.name != null)                //传入对象的姓名不为null
                    return false;                    //返回false
            } else if (!name.equals(other.name))    //调用对象的姓名不等于传入对象的姓名
                return false;                        //返回false
            return true;                            //返回true
        }
    
        @Override
        public String toString() {
            return "Person{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    }

TreeSetDemo类:

package com.zyh.Collection.set;
    
    import com.zyh.domain.Person;
    
    import java.util.TreeSet;
    
    public class TreeSetDemo_0010 {
        public static void main(String[] args) {
            TreeSet<Person> ts = new TreeSet<>();
            ts.add(new Person("张三",23));
            ts.add(new Person("李四",13));
            ts.add(new Person("王五",43));
            ts.add(new Person("赵六",33));
    
            for (Person p:ts){
                System.out.println(p);
            }
        }
    
    }

当我们直接执行的时候，会报错误:

Exception in thread "main" java.lang.ClassCastException: com.zyh.domain.Person cannot be cast to java.lang.Comparable

分析：Integer能排序(有默认顺序), String能排序(有默认顺序),  
自定义的类存储的时候出现异常(没有顺序)。

**2）自然排序(Comparable)**  
我们让Person实现Comparable接口，重写compareTo()方法

public class Person implememnts Comparable<Person>

当我们把返回值设置为1时：

public int compareTo(Person o){
        return 1;
    }

图解：  
![tqAb4E8.png][]

*  当返回值是0时，张三作为二叉树的根，当我们其他的元素比较时，都返回0表示  
    相同的对象。所以只会存储张三。
 *  当返回值是-1时，张三作为二叉树的根，李四和它比较时，返回-1说明，李四小，挂在张三的左边。  
    王五一进来也和张三比较返回-1，放在张三左边，在和李四比较返回-1，挂在李四左边，以此类推。
 *  当返回值是1时。和上面一样的推理。

举例一：按照年龄排序  
![hUv9peE.png][]  
分析：

*  张三作为二叉树的根，当李四进来的时候，李四的年龄比张三小，挂在张三的左边。当王五进来的时候，
 *  王五的年纪比张三大，所以挂在张三的右边。当赵六的进来的时候，和张三比较年龄结果赵六大，挂在
 *  张三的右边，在和王五比较结果比王五小，挂在王五的左边。

结果排序就是：李四、张三、赵六、王五  
  ![Q947kWn.png][]

举例二：按年龄为主要条件，名字是次要条件  
![lnrSPTH.png][]

**3）比较器顺序(Comparator)**  
首先我们查看TreeSet的构造方法发现有一个这样的构造方法：

// 指定TreeSet的比较器
    　　　　　　TreeSet(Comparator<? super E> comparator)

通过查看它的构造方法就知道可以传入一个比较器。

构造一个新的空TreeSet，它根据指定比较器进行排序。插入到该 set 的所有元素都必须能够  
由指定比较器进行相互比较：对于 set 中的任意两个元素 e1 和e2，执行  
comparator.compare(e1, e2) 都不得抛出 ClassCastException。

如果用户试图将违反此约束的元素添加到 set 中，则 add 调用将抛出 ClassCastException。  
![HTJCXdU.png][]

TreeSetd的Comparetor比较器实现的二种方法:

*  第一种：写个类实现Comparator接口

class myComparator implements Comparator{
        
    
        @Override
        public int compare(Object o1, Object o2) {
            Person p1 = (Person) o1;
            Person p2 = (Person) o2;
    
            int num = p1.getName().compareTo(p2.getName());
          // 0的话是两个相同，进行下一个属性比较
            if (num == 0){
                return new Integer(p1.getAge()).compareTo(new Integer(p2.getAge()));
            }
    
            return num;
        }
    }
    然后在new Set的时候放进去。如 
    TreeSet ts = new TreeSet(new myComparator());

*  第二种：写匿名内部类方法

TreeSet ts = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                Person p1 = (Person) o1;
                Person p2 = (Person) o2;
    
                int num = p1.getName().compareTo(p2.getName());
    
                if (num == 0){
                    return new Integer(p1.getAge()).compareTo(new Integer(p2.getAge()));
                }
    
                return num;
    
            }
        });

[uUO65Sh.png]: https://i.imgur.com/uUO65Sh.png
[6wRPay3.png]: https://i.imgur.com/6wRPay3.png
[tqAb4E8.png]: https://i.imgur.com/tqAb4E8.png
[hUv9peE.png]: https://i.imgur.com/hUv9peE.png
[Q947kWn.png]: https://i.imgur.com/Q947kWn.png
[lnrSPTH.png]: https://i.imgur.com/lnrSPTH.png
[HTJCXdU.png]: https://i.imgur.com/HTJCXdU.png