Java中Set集合的使用和底层原理

灰太狼 2023-09-24 12:50 98阅读 0赞

#### 文章目录 ####

*  Set系列集合介绍
 *   *  Set集合概述
     *  HashSet无序原理
     *  Set集合对象去重
     *  LinkedHashSet
     *  TreeSet排序规则

## Set系列集合介绍 ##

### Set集合概述 ###

**Set系列集合特点**:

> 无序：存取数据的顺序是不一定的, 当数据存入后, 集合的顺序就固定下来了
> 
> 不重复：可以去除重复
> 
> 无索引：没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素。

**Set集合实现类特点**:

> HashSet : 无序、不重复、无索引。

public static void main(String[] args) {
        
      	// 无序, 不重复, 无索引
        Set<String> sets = new HashSet<>();
        sets.add("MySQL");
        sets.add("MySQL");
        sets.add("JAVA");
        sets.add("JAVA");
        sets.add("HTML");
        sets.add("HTML");
        sets.add("Vue");
        sets.add("Vue");
        System.out.println(sets); // [JAVA, MySQL, Vue, HTML]
    }

> LinkedHashSet：有序、不重复、无索引。

public static void main(String[] args) {
        
      	// 有序、不重复、无索引
        Set<String> sets = new LinkedHashSet<>();
        sets.add("MySQL");
        sets.add("MySQL");
        sets.add("JAVA");
        sets.add("JAVA");
        sets.add("HTML");
        sets.add("HTML");
        sets.add("Vue");
        sets.add("Vue");
        System.out.println(sets); // [MySQL, JAVA, HTML, Vue]
    }

> TreeSet：排序: 默认升序、不重复、无索引。

public static void main(String[] args) {
        
        // 排序、不重复、无索引
        Set<Integer> sets = new TreeSet<>();
        sets.add(10);
        sets.add(10);
        sets.add(20);
        sets.add(20);
        sets.add(30);
        sets.add(30);
        sets.add(40);
        sets.add(40);
        sets.add(50);
        sets.add(50);
        System.out.println(sets); // [10, 20, 30, 40, 50]
    }

**Set集合的功能上基本上与Collection的API一致, Set集合没有扩展额外的API**。

### HashSet无序原理 ###

> HashSet集合底层采取**哈希表**存储的数据。
> 
> 哈希表是一种对于增删改查数据性能都较好的结构。

**哈希表的组成**:

> JDK8之前的，底层使用`数组+链表`组成
> 
> JDK8开始后，底层采用`数组+链表+红黑树`组成。
> 
> 哈希表是一种对于增删改查数据性能都较好的结构。
> 
> 在了解哈希表之前需要先理解哈希值的概念

**哈希值**:

> 是JDK根据对象的地址，按照某种规则算出来的int类型的数值。

**获取哈希值: 通过Object类的API**:

> `public int hashCode()`：返回对象的哈希值

**对象的哈希值特点**:

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

public static void main(String[] args) {
        
        String address = "成都市";
        System.out.println(address.hashCode()); // 25299637
        System.out.println(address.hashCode()); // 25299637
        System.out.println(address.hashCode()); // 25299637
    }

> 默认情况下，不同对象的哈希值是不同的。

**JDK8之前的版本HashSet原理解析：数组 + 链表 +（结合哈希算法）, 详细流程如下**:

> 1.  底层会默认创建一个默认长度16的数组，数组名table

![在这里插入图片描述][8051059170b640a08db9e18bc6c623d5.png_pic_center]

> 1.  根据元素的**哈希值**跟**数组的长度求余**计算出应存入的位置（哈希算法）
> 
> > 例如数组长度是16, 哈希值与16取余, 得出的结果一定是0到15之间的数字
> 
> 1.  判断当前位置是否为null，如果是null直接存入
> 2.  如果位置不为null，表示有元素，则调用equals方法比较
> 3.  如果一样，则不存，如果不一样，则存入数组
> 
> > 在JDK 7中, 新元素占老元素位置，并且新元素会指向老元素
> > 
> > 在JDK 8中, 新元素挂在老元素下面

**JDK8之后的版本HashSet原理解析**:

> 底层结构：哈希表（数组、链表、红黑树的结合体）
> 
> 当挂在元素下面的数据过多时，查询性能降低，从JDK8开始后，当链表长度超过8的时候，自动转换为红黑树。

![在这里插入图片描述][cd56ff2faf3f454f80303883c6c6bbb4.png_pic_center]

> **JDK8开始后，哈希表对于红黑树的引入进一步提高了操作数据的性能。**

### Set集合对象去重 ###

**HashSet去重注意点**:

> Set集合在比较两个对象时, 默认比较的是两个对象的地址是否一致, 若地址不同则认为是两个不同的对象;
> 
> 而如果希望Set集合认为2个内容一样的对象是重复的，则需要自己重写对象的hashCode()和equals()方法

**我们来看下面这样一个案例**:

> **需求**: 创建一个存储学生对象的集合，存储多个学生对象，使用程序实现在控制台遍历该集合，要求：学生对象的成员变量值相同，我们就认为是同一个对象
> 
> **分析**:
> 
> 1.  定义学生类，创建Set集合对象, 创建学生对象
> 2.  把学生添加到集合
> 3.  在学生类中重写两个方法，hashCode()和equals()，自动生成即可

*  步骤一: 定义学生类

public class Student {
        
        private String name;
        private int age;
        private int id;
    
        // 构造器
        public Student() {
        };
    
        public Student(String name, int age, int id) {
        
            this.name = name;
            this.age = age;
            this.id = id;
        }
    
        // getter和setter方法
        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;
        }
    
        public int getId() {
        
            return id;
        }
    
        public void setId(int id) {
        
            this.id = id;
        }
      
        // 重写toString方法
        @Override
        public String toString() {
        
            return "Student{" +
                    "name='" + name + '\'' +
                    ", age=" + age +
                    ", id=" + id +
                    '}';
        }
    }

*  步骤二: 创建学生对象和HashSet集合, 并将学生对象存入HashSet集合中, 如下代码:

public class Test {
        
        public static void main(String[] args) {
        
            // 创建集合存储学生对象
            Set<Student> students = new HashSet<>();
            // 创建学生对象
            Student stu1 = new Student("小明", 18, 101);
            Student stu2 = new Student("小明", 18, 101);
            Student stu3 = new Student("小王", 20, 102);
            // 将学生对象添加到集合中
            students.add(stu1);
            students.add(stu2);
            students.add(stu3);
    
            System.out.println(students);
            // 打印结果如下: 
            //  [Student{name='小明', age=18, id=101}, 
            //  Student{name='小明', age=18, id=101}, 
            //  Student{name='小王', age=20, id=102}]
        }
    }

*  步骤三: 我们发现步骤二代码中, stu1和stu2对象的内容完全一样, 但是由于对象的地址不一样, 会被当成两个不同的对象存入到集合中; 因此我们需要在**学生类中**重写两个方法，hashCode()和equals()，自动生成即可

@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 && id == student.id && Objects.equals(name, student.name);
    }
    
    @Override
    public int hashCode() {
        
      	// 该方法传入的参数相同, 就会返回相同的哈希值
        return Objects.hash(name, age, id);
    }

*  步骤四: 此时再将stu1和stu2对象存入集合, 由于内容一样就会被去掉重复的

public class Test {
        
        public static void main(String[] args) {
        
            // 创建集合存储学生对象
            Set<Student> students = new HashSet<>();
            // 创建学生对象
            Student stu1 = new Student("小明", 18, 101);
            Student stu2 = new Student("小明", 18, 101);
            Student stu3 = new Student("小王", 20, 102);
            // 将学生对象添加到集合中
            students.add(stu1);
            students.add(stu2);
            students.add(stu3);
    
            System.out.println(students);
            //  [Student{name='小王', age=20, id=102}, Student{name='小明', age=18, id=101}]
        }
    }

### LinkedHashSet ###

**LinkedHashSet集合概述和特点**:

> 有序、不重复、无索引。
> 
> 这里的有序指的是保证存储和取出的元素顺序一致

**原理**：

> 底层数据结构是依然哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序。

![在这里插入图片描述][6b9e34561b1d4d21b72917d07ae9117c.png_pic_center]

### TreeSet排序规则 ###

**TreeSet集合特点**:

> 不重复、无索引、可排序
> 
> 可排序：按照元素的大小默认升序（有小到大）排序。
> 
> TreeSet集合底层是基于红黑树的数据结构实现排序的，增删改查性能都较好。
> 
> **注意：TreeSet集合是一定要排序的，可以将元素按照指定的规则进行排序**。

**TreeSet默认排序规则**:

> 对于数值类型：Integer , Double，官方默认按照大小进行升序排序。
> 
>     public static void main(String[] args) {
>          
>         Set<Integer> sets1 = new TreeSet<>();
>         sets1.add(50);
>         sets1.add(10);
>         sets1.add(30);
>         sets1.add(20);
>         System.out.println(sets1); // [10, 20, 30, 50]
>     
>         Set<Double> sets2 = new TreeSet<>();
>         sets2.add(10.11);
>         sets2.add(20.22);
>         sets2.add(43.22);
>         sets2.add(8.22);
>         System.out.println(sets2); // [8.22, 10.11, 20.22, 43.22]
>     }
> 
> 对于字符串类型：默认按照首字符的编号升序排序。
> 
>     public static void main(String[] args) {
>          
>         Set<String> sets = new TreeSet<>();
>         sets.add("bbb");
>         sets.add("eee");
>         sets.add("aaa");
>         sets.add("ccc");
>         System.out.println(sets); // [aaa, bbb, ccc, eee]
>     }

**对于自定义类型如Student对象，TreeSet无法直接排序, 需要制定排序规则; 例如下面代码中向集合中添加学生类, TreeSet是无法进行排序的, 会崩溃报错**。

// 错误演示
    public static void main(String[] args) {
        
        // 创建学生对象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小赵", 18, 102);
        Student stu3 = new Student("小王", 18, 103);
        // 创建集合
        Set<Student> students = new TreeSet<>();
        students.add(stu1);
        students.add(stu2);
        students.add(stu3);
        System.out.println(students);
    }

**自定义排序规则**: TreeSet集合存储对象的的时候有2种方式可以设计自定义比较规则

> 方式一: 让自定义的类（如学生类）实现Comparable接口, 并重写compareTo方法来定制比较规则。

// 实现Comparable接口
    public class Student implements Comparable<Student> {
        
      	// 其他代码...
      
      	// 重写compareTo方法
        @Override
        public int compareTo(Student o) {
        
            // 例如按照id进行排序
            return this.id - o.id;
        }
    }

public static void main(String[] args) {
        
        // 创建学生对象
        Student stu1 = new Student("小明", 18, 101);
        Student stu2 = new Student("小赵", 18, 102);
        Student stu3 = new Student("小王", 18, 103);
        // 创建集合
        Set<Student> students = new TreeSet<>();
        students.add(stu1);
        students.add(stu2);
        students.add(stu3);
        System.out.println(students);
        // 打印结果: 按照id升序
        // [Student{name='小明', age=18, id=101}, 
        // Student{name='小赵', age=18, id=102}, 
        // Student{name='小王', age=18, id=103}]
    }

> 方式二: TreeSet集合有参数构造器自带比较器对象，来进行定制比较规则, 并且该方法如果和方式一同时出现, 会优先使用此方法的比较规则。

public class SetDemo {
        
        public static void main(String[] args) {
        
            // 创建学生对象
            Student stu1 = new Student("小明", 18, 101);
            Student stu2 = new Student("小赵", 18, 102);
            Student stu3 = new Student("小王", 18, 103);
            // 创建集合
            // 方式二: 使用构造器自带的比较器对象
            Set<Student> students = new TreeSet<>(new Comparator<Student>() {
        
                @Override
                public int compare(Student o1, Student o2) {
        
                    return o2.getId() - o1.getId();
                }
            });
            students.add(stu1);
            students.add(stu2);
            students.add(stu3);
            System.out.println(students);
            // 打印结果: 按照id降序
            // [Student{name='小王', age=18, id=103},
            // Student{name='小赵', age=18, id=102},
            // Student{name='小明', age=18, id=101}]
        }
    }

*  并且可以使用Lambda表达式简化代码

public class SetDemo {
        
        public static void main(String[] args) {
        
            // 创建学生对象
            Student stu1 = new Student("小明", 18, 101);
            Student stu2 = new Student("小赵", 18, 102);
            Student stu3 = new Student("小王", 18, 103);
            // 创建集合
            // 方式二: 使用构造器自带的比较器对象
            Set<Student> students = new TreeSet<>((Student o1, Student o2) -> o2.getId() - o1.getId());
            
            students.add(stu1);
            students.add(stu2);
            students.add(stu3);
            System.out.println(students);
            // 打印结果: 按照id降序
            // [Student{name='小王', age=18, id=103},
            // Student{name='小赵', age=18, id=102},
            // Student{name='小明', age=18, id=101}]
        }
    }

[8051059170b640a08db9e18bc6c623d5.png_pic_center]: https://img-blog.csdnimg.cn/8051059170b640a08db9e18bc6c623d5.png#pic_center
[cd56ff2faf3f454f80303883c6c6bbb4.png_pic_center]: https://img-blog.csdnimg.cn/cd56ff2faf3f454f80303883c6c6bbb4.png#pic_center
[6b9e34561b1d4d21b72917d07ae9117c.png_pic_center]: https://img-blog.csdnimg.cn/6b9e34561b1d4d21b72917d07ae9117c.png#pic_center