Set系列集合：Hashset、LinkedHashset、TreeSet --java学习笔记_hashset treeset linkedhashset

Set系列集合

• Set系列集合特点:无序、不重复、无索引
• 添加数据的顺序和获取出的数据顺序不一致;
• Hashset:无序、不重复、无索引
• LinkedHashset:有序、不重复、无索引
• TreeSet:排序、不重复、无索引

代码演示：

import java.util.*;
 
public class ListTest5 {
    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>(); //一行经典代码,多态写法,创建了一个HashSet集合对象
        //HashSet集合:无序,不重复,无索引
        set.add(555);
        set.add(222);
        set.add(222);
        set.add(111);
        set.add(333);
        set.add(333);
        set.add(444);
        System.out.println(set);    //[555, 444, 333, 222, 111]
        System.out.println("---------------------------------");
        Set<Integer> set2 = new LinkedHashSet<>();
        //LinkedHashSet集合:有序,不重复,无索引
        set2.add(555);
        set2.add(222);
        set2.add(222);
        set2.add(111);
        set2.add(333);
        set2.add(333);
        set2.add(444);
        System.out.println(set2);   //[555, 222, 111, 333, 444]
        System.out.println("---------------------------------");
        Set<Integer> set3 = new TreeSet<>();
        //TreeSet:可排序,不重复,无索引
        set3.add(555);
        set3.add(222);
        set3.add(222);
        set3.add(111);
        set3.add(333);
        set3.add(333);
        set3.add(444);
        System.out.println(set3);   //[111, 222, 333, 444, 555]
    }
}

注意:Set要用到的常用方法，基本上就是Collection提供的!
自己几乎没有额外新增一些常用功能!

在学习Set系列之前得先了解哈希值

哈希值

• 就是一个int类型的数值，Java中每个对象都有一个哈希值
• Java中的所有对象，都可以调用Obejct类提供的hashCode方法，返回该对象自己的哈希值

对象哈希值的特点

• 同一个对象多次调用hashcode()方法返回的哈希值是相同的
• 不同的对象，它们的哈希值一般不相同，但也有可能会相同(哈希碰撞，小概率)

Hashset集合的底层原理

• 基于哈希表实现
• 哈希表是一种增删改查数据，性能都较好的数据结构

哈希表

哈希表是一种增删改查数据性能都较好的结构

• JDK8之前，哈希表=数组+链表
  1、往哈希表添加数据时，会创建一个默认长度16的数组，默认加载因子为0.75，数组名table
  2、使用元素的哈希值对数组的长度求余计算出应存入的位置
  3、判断当前位置是否为null，如果是null直接存入
  4、如果不为null，表示有元素，则调用equals方法比较
          相等，则不存;不相等，则存入数组
         JDK 8之前，新元素存入数组，占老元素位置，老元素挂下面
         JDK 8开始之后，新元素直接挂在老元素下面
  
• JDK8开始，哈希表=数组+链表+红黑树
  如果数组快占满了，链表会过长，导致查询性能降低
  此时就会进行扩容
  当数组占满长度*加载因子（16*0.75=12）个位置时，会将数组的长度翻倍，将原来的数据重新存入数组
  并且从JDK8开始，当链表长度超过8，且数组长度>=64时，自动将链表转成红黑树
  
  红黑树，就是可以自平衡的二叉树
  红黑树是一种增删改查数据性能相对都较好的结构

深入理解HashSet集合去重复的机制

Hashset集合默认不能对内容一样的两个不同对象去重复!因为它们哈希值一样
比如内容一样的两个学生对象存入到Hashset集合中去，Hashset集合是不能去重复的!

例：

import java.util.HashSet;
 
public class SetTest2 {
    public static void main(String[] args) {
        Student s1 = new Student("小明","男","170");
        Student s2 = new Student("小明","男","170");
        Student s3 = new Student("小明","男","170");
        HashSet<Student> students = new HashSet<>();
        students.add(s1);
        students.add(s2);
        students.add(s3);
        System.out.println(students);
 
    }
}

运行结果：

如果希望Set集合认为2个内容一样的对象是重复的必须重写对象的hashcode()和equals()方法

LinkedHashset集合的底层原理

• 有序、不重复、无索引
• 依然是基于哈希表(数组、链表、红黑树)实现的
• 但是，它的每个元素都额外的多了一个双链表的机制记录它前后元素的位置，会有头节点变量和尾结点变量记录第一个和最后一个元素（空间换时间）

TreeSet集合的底层原理

• 不重复、无索引、可排序（默认）
• 排序的原理：基于红黑树实现的排序

注意:

• 对于数值类型:Integer，Double，默认按照数值本身的大小进行升序排序
• 对于字符串类型:默认按照首字符的编号升序排序。
• 对于自定义类型如Student对象，Treeset默认是无法直接排序的，

自定义排序规则

TreeSet集合存储自定义类型的对象时，必须指定排序规则，支持如下两种方式来指定比较规则

• 方式一：让自定义的类(如学生类)实现comparable接口，重写里面的compareTo方法来指定比较规则
   
• 方式二：通过调用TreeSet集合有参数构造器，可以设置Comparator对象比较器对象，用于指定比较规则

方法一：

import java.util.Objects;
 
public class Student implements Comparable<Student>{
    private String name;
    private String sex;
    private double height;
 
    //按照身高升序排序
    @Override
    public int compareTo(Student o) {
        return Double.compare(this.getHeight(), o.getHeight());
    }
 
    //......
}

方法二：

public class SetTest3 {
    public static void main(String[] args) {
        Student s1 = new Student("小明","男",170);
        Student s2 = new Student("小美","女",168);
        Student s3 = new Student("小黑","男",188);
        //按照身高升序排序
        TreeSet<Student> students = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return Double.compare(o1.getHeight(),o2.getHeight());
            }
        });
        students.add(s1);
        students.add(s2);
        students.add(s3);
        System.out.println(students);
    }
}

两种方式中，关于返回值的规则:

• 如果认为第一个元素 > 第二个元素 返回正整数即可
• 如果认为第一个元素<第二个元素返回负整数即可
• 如果认为第一个元素=第二个元素返回0即可，此时Treeset集合只会保留一个元素，认为两者重复

注意:如果类本身有实现Comparable接口，Treeset集合同时也自带比较器，默认使用集合自带的比较器排序