JAVA_Set系列集合:HashSet、LinkedHashSet、TreeSet底层详解

先看看 Set 系列集合的位置：
image.png

Set 系列集合的特点：

  • 无序：存取顺序不一致
    • 如存入张三、李四、王五。而遍历获取到的是李四, 张三, 王五
  • 不重复：可以去除重复
  • 无索引：没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素

Set 接口的实现类：

  • HashSet：无序、不重复、无索引
  • LinkedHashSet：有序、不重复、无索引
  • TreeSet：可排序、不重复、无索引

Set接口中的方法上基本上与Collection的API一致。
Collection 是单列集合的祖宗接口，它的功能是全部单列集合都可以使用的。
回顾一下：
image.png

--------------------------------

认识： HashSet ：

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

哈希表组成：

  • jdk8 前：数组+链表
  • jdk8 及以后：数组+链表+红黑树
    • 所以 HashSet 底层和数组、链表、红黑树都有关系

哈希值：对象的整数表现形式

  • 它是根据hashCode方法算出来的int类型的整数
  • 该方法定义在Object类中，所有对象都可以调用，没有重写则默认使用地址值进行计算
  • 一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值

对象的哈希值特点：

  • 如果没有重写 hashCode 方法，不同对象计算出的哈希值是不同的

image.png

  • 如果已经重写了 hashCode 方法，不同的对象只要属性值相同，计算出的哈希值就是一样的

image.png

  • 在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。（哈希碰撞）如下

image.png

jdk8 及以后的 HashSet 的底层原理。

  1. 创建 HashSet 集合后，会在底层创建一个长度为 16 的数组 table，并加载 负载因子为0.75 的 HashMap
    1. 这意味着当 HashSet 中的元素数量达到数组长度的 75% 时，数组会进行扩容（原有长度*2）操作，以保持较低的碰撞率和良好的性能。
  2. 根据元素的哈希值跟数组的长度计算出应存入的位置

int index=( 数组长度-1 ) & 哈希值
所以说第一个元素存入的位置不一定是 0 索引处，如下
image.png
获取元素时就从左到右遍历，所以说 HashSet 是无序的

  1. 判断当前位置是否为 null，如果是 null 直接存入
    1. 如果不是 null，表示有元素，则调用 equals 方法比较属性值
      1. 一样则不存，不一样则存入，形成链表
        1. 注意： jdk8 以前：新元素存入数组，老元素挂在新元素下面，jdk8及以后：新元素直接挂在老元素下面。如图：
        2. image.png
      2. 注意：当链表长度大于 8 并且 数组长度 大于等于 64 时，链表会变成红黑树。如图：
      3. image.png

注意点：

如果集合中存储的是自定义对象 ，必须要重写 hashCode 和 equals 方法（有的类已经重写过了，如 String Integer，会自动去重）不然 操作的都是地址值（一般来说，我们对于地址值是没有需求的）。

  • 重写 hashCode 是为了通过属性值计算哈希值
  • 重写 equals 是为了比较对象内部属性

用练习来理解：

Snipaste_2024-01-27_14-51-14.png

创建 Student 类–此时未重写 hashCode 和 equals 方法

public Student{
    private String name;
    private int age;

    //构造方法+set+get
	//此时未重写hashCode 和 equals 方法
}

创建测试类

Student1 s1=new Student("zhangsan",23);
Student1 s2=new Student("lisi",24);
Student1 s3=new Student("zhangsan",23);//已重复，不应该存入
//创建HashSet集合
HashSet <Student>set=new HashSet<>();

//重写hashCode和equals前，都能添加成功，这不是我们想要的
System.out.println(set.add(s1));//true
System.out.println(set.add(s2));//true
System.out.println(set.add(s3));//true

首先来说一下：为什么 s3 能添加成功：
因为此时在 Student 类中还未重写 hashCode ，所以使用的是地址值来获取的哈希值，由于不同对象地址值肯定不同，所以 s1 和 s3 被存在不同的位置上

此时在 Student 类中重写 hashCode 和 equals 方法(alt 和 insert 快捷键)

......
@Override
    public boolean equals(Object o) {

        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student1 student1 = (Student1) o;
        return age == student1.age && Objects.equals(name, student1.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

再来看测试类

Student1 s1=new Student("zhangsan",23);
Student1 s2=new Student("lisi",24);
Student1 s3=new Student("zhangsan",23);//属性重复，不应该存入
//创建HashSet集合
HashSet <Student>set=new HashSet<>();

/*重写hashCode和equals后，s3添加失败。                        */
System.out.println(set.add(s1));//true
System.out.println(set.add(s2));//true
System.out.println(set.add(s3));//false

说明一下此时为什么 s3 能添加成功：
重写 hashCode 后，通过属性来获取哈希值，而 s1 和 s3 的属性一样，所以会有一样的哈希值，所以存入的位置一样，此时就体现重写 equals 的作用了，s3 会和 s1 属性比较，发现一样，则不存
。

这个例子中，重写的 equals 方法拦截了相同哈希值，相同属性的对象的存入（实现了去重）
有时又不会拦截，如下哈希碰撞情况

它们有相同的哈希值，会放入同一个位置，重写的 equals 方法会比较它们的属性值，发现不一样，所以 acD 会挂在 abc 的下面，形成链表。

------------------------------------

认识： LinkedHashSet：

在集合体系中的位置：是 HashSet 的子类
image.png

特点：

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

原理：

底层数据结构依旧是哈希表（是 HashSet 的子类）
使用双链表记录添加顺序
如图：遍历时就按记录的添加顺序来获取元素，
image.png

注意点：
在以后如果要数据去重，我们使用 HashSet 还是 LinkedHashSet?

默认使用 HashSet，如果 要求去重 且 存取有序，才使用LinkedHashSet

要知道：HashSet比LinkedHashSet效率更高

---------------------------------

认识： TreeSet：

在集合体系中的位置
Snipaste_2024-01-27_15-16-27.png

特点：

  • 可排序：按照元素的默认规则（有小到大）排序。
    • 自然排序：如果集合中的元素实现了Comparable接口（例如Integer、String等，默认已实现），TreeSet会根据元素自身的compareTo()方法提供的排序规则进行排序。 / **若是自定义类，要手动实现Comparable接口和compareTo()方法，否则找不到排序方法，报错
    • 定制排序：你也可以提供一个Comparator对象给TreeSet的对象用于定义自定义的排序逻辑。
    • 使用原则：默认使用第一种，当第一种不能满足需求就使用第二种
  • 不重复
  • 无索引

底层：

Tree Set集合底层是基于红黑树的数据结构实现排序的，
删改查性能都较好。

1. 自然排序Comparable的使用

排序练习题：
image.png

//创建TreeSet集合对象
TreeSet<Integer>treeSet=new TreeSet<>();

treeSet.add(1);
treeSet.add(4);
treeSet.add(2);
treeSet.add(5);
treeSet.add(3);


//自然排序 默认从小到大排序

//1.迭代器
Iterator<Integer> it = treeSet.iterator();
while (it.hasNext()){
    int i=it.next();//jdk5后自动装箱，拆箱
    System.out.print(i+" ");//1 2 3 4 5
}

System.out.println();

//2.增强for
for (Integer i : treeSet) {
    System.out.print(i+" ");
}

System.out.println();

//3.lambda
treeSet.forEach(i-> System.out.print(i+" "));

控制台：
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

TreeSet集合 默认的排序规则（自然排序）：

  • 对于数值类型：Integer，Double，默认按照从小到大的顺序进行排序。
  • 对于字符、字符串类型：按照字符在ASCII码表中的数字升序进行排序。如图：
    • image.png
    • 第一个字符相同则比较第二个，有字符默认 比 无字符大

TreeSet_对象自然排序_练习题：
image.png

要求：
1.根据年龄排序

可知 可以通过 自然排序 解决。又因为是自定义类，所以要手动实现Comparable接口和compareTo()方法，否则找不到排序方法，报错

Student 类

public class Student {
    private String name;
    private int age;

//构造方法+set+get+toString
   
}

测试类

public class Test {
    public static void main(String[] args) {
    //创建对象
    Student stu1 = new Student("zhangsan", 23);
    Student stu2 = new Student("lisi", 24);
    Student stu3 = new Student("wangwu", 25);
    Student stu4 = new Student("zhaoliu", 26);

    //创建集合
    TreeSet<Student> ts = new TreeSet<>();

    //添加对象
    ts.add(stu3);
    ts.add(stu2);
    ts.add(stu1);
    ts.add(stu4);
    //打印集合
    System.out.println(ts);
    }
}

此时打印会报错，因为集合内是自定义类，要手动给出排序方式：

步骤：

  1. 实现 Comparable 接口
    1. image.png
    2. image.png
    3. 再实现里面的 Compare To 方法image.png
    4. 并书写方法image.png

给出排序方式后：Student 类

package com.lt.treeset;

public class Student implements Comparable<Student>{
    private String name;
    private int age;
    .....
    public String toString() {
        return "Student{name = " + name + ", age = " + age + "}";
    }


//this：表示当前要添加的元素
//o：表示已经在红黑树存在的元素
//返回值：
//负数：表示当前要添加的元素是小的，存左边
//正数：表示当前要添加的元素是大的，存右边
//0:表示当前要添加的元素已经存在，含弃
    @Override
    public int compareTo(Student o) {
        //只看年龄，升序，（降序就调换位置即可）
       return this.getAge()-o.getAge();
    }
}

测试类

public class Test {
    public static void main(String[] args) {
    //创建对象
    Student stu1 = new Student("zhangsan", 23);
    Student stu2 = new Student("lisi", 24);
    Student stu3 = new Student("wangwu", 25);
    Student stu4 = new Student("zhaoliu", 26);

    //创建集合
    TreeSet<Student> ts = new TreeSet<>();

    //添加对象
    ts.add(stu3);
    ts.add(stu2);
    ts.add(stu1);
    ts.add(stu4);
    //打印集合
    System.out.println(ts);
    }
}

控制台：
[Student{name = zhangsan, age = 23}, Student{name = lisi, age = 24}, Student{name = wangwu, age = 25}, Student{name = zhaoliu, age = 26}]

**若改变一下题目：
年龄相同则比较字母大小。
CompareTo 就可以这样写
image.png

其实元素存储的原理就是红黑树：
我们针对年龄来演示：
添加顺序：
image.png
红黑树添加规则：
image.png

-----开始：

  1. Snipaste_2024-01-27_21-33-38.png
  2. Snipaste_2024-01-27_21-33-48.png
  3. Snipaste_2024-01-27_21-34-30.png
  4. Snipaste_2024-01-27_21-34-58.png
  5. Snipaste_2024-01-27_21-36-10.png
  6. Snipaste_2024-01-27_21-36-32.png
  7. Snipaste_2024-01-27_21-37-56.png
  8. Snipaste_2024-01-27_21-38-53.png
  9. Snipaste_2024-01-27_21-39-08.png
  10. Snipaste_2024-01-27_21-40-31.png

2. 比较器排序（自定义）：

创建TreeSet对象时候，传递比较器Comparator指定规则

练习：
image.png
要按照字符串长度来比较，用自然排序无法比较，所以要使用自定义
步骤
image.png

public class Test02 {
    public static void main(String[] args) {

        //创建集合
        TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {

            @Override
            //o1：表示当前要添加的元素
            //o2表示已经在红黑树存在的元素
            public int compare(String o1, String o2) {
                //按照长度排序
                int i = o1.length() - o2.length();
                //如果一样长则按照首字母排序
                if (i == 0) {
                    //调用默认的字符排序，就不会被丢弃
                    return o1.compareTo(o2);
                }
                return i;
            }
        });

        //添加
        ts.add("c");
        ts.add("qwer");
        ts.add("df");
        ts.add("ab");

        //打印：
        System.out.println(ts);//[c, ab, df, qwer]

    }
}

上面的匿名内部类可以用 Lambda 简化

练习题 ：

TreeSet对象自定义排序练习题：

  • 存储老师对象并遍历，创建TreeSet集合使用带参构造方法
  • 要求：按照年龄从小到大排序，年龄相同时，按照姓名的字母长度排序

Teacher 类：

public class Teacher {
    private String name;
    private int age;
//构造+set+get+ toString
}

测试类：

package com.lt.treeset;





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

public class MyTreeSet4 {
    public static void main(String[] args) {
        //创建集合对象
        TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() {
            @Override
            public int compare(Teacher o1, Teacher o2) {
                //o1表示现在要存入的那个元素
                //o2表示已经存入到集合中的元素

                //主要条件
                int result = o1.getAge() - o2.getAge();
                //次要条件
                result = result == 0 ? o1.getName().length()-o2.getName().length() : result;
                return result;
            }
        });
        //创建老师对象
        Teacher t1 = new Teacher("zhangsan",22);
        Teacher t2 = new Teacher("lisi",22);
        Teacher t3 = new Teacher("wangwu",24);
        Teacher t4 = new Teacher("zhaoliu",24);
        //把老师添加到集合
        ts.add(t1);
        ts.add(t2);
        ts.add(t3);
        ts.add(t4);
        //遍历集合
        for (Teacher teacher : ts) {
            System.out.println(teacher);
        }
    }
}

自定义排序的应用场景：

当要给字符串长度排序
或
数字要从大到小排序

若排序方式一和方式二同时存在会以什么方式为准？
答：第二种

总结：
Snipaste_2024-01-27_16-26-38.png
Snipaste_2024-01-27_16-28-00.png

它们的 Set 系列的集合是基于 Map 接口的
HashSet:
Snipaste_2024-01-27_16-29-33.png
add 方法:
Snipaste_2024-01-27_16-29-52.png
LinkedHashSet：
Snipaste_2024-01-27_16-30-41.pngSnipaste_2024-01-27_16-30-55.png
TreeSet：
Snipaste_2024-01-27_16-31-21.png
后面讲 Map 接口再说。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/353255.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Redis缓存设计与性能优化

Redis缓存设计与性能优化

文章目录 多级缓存架构缓存设计缓存穿透缓存失效(击穿)缓存雪崩热点缓存key重建优化缓存与数据库双写不一致 开发规范与性能优化一、键值设计1. key名设计2. value设计bigkey的危害&#xff1a;bigkey的产生&#xff1a;如何优化bigkey 二、命令使用三、客户端使用Redis对于过期…
阅读更多...
SpringBoot系列之MybatisPlus实现分组查询

SpringBoot系列之MybatisPlus实现分组查询

SpringBoot系列之MybatisPlus实现分组查询 我之前博主曾记写过一篇介绍SpringBoot2.0项目怎么集成MybatisPlus的教程&#xff0c;不过之前的博客只是介绍了怎么集成&#xff0c;并没有做详细的描述各种业务场景&#xff0c;本篇博客是对之前博客的补充&#xff0c;介绍在mybat…
阅读更多...
GitHub 一周热点汇总第7期(2024/01/21-01/27)

GitHub 一周热点汇总第7期(2024/01/21-01/27)

GitHub一周热点汇总第7期 (2024/01/21-01/27) &#xff0c;梳理每周热门的GitHub项目&#xff0c;离春节越来越近了&#xff0c;不知道大家都买好回家的票没有&#xff0c;希望大家都能顺利买到票&#xff0c;一起来看看这周的项目吧。 #1 rustdesk 项目名称&#xff1a;rust…
阅读更多...
3个精美的wordpress律师网站模板

3个精美的wordpress律师网站模板

暗红色WordPress律师事务所网站模板 演示 https://www.zhanyes.com/qiye/23.html 暗橙色WordPress律师网站模板 演示 https://www.zhanyes.com/qiye/18.html 红色WordPress律所网站模板 演示 https://www.zhanyes.com/qiye/22.html
阅读更多...
最新国内GPT4.0使用教程，AI绘画-Midjourney绘画V6 ALPHA绘画模型，GPT语音对话使用，DALL-E3文生图+思维导图一站式解决方案

最新国内GPT4.0使用教程，AI绘画-Midjourney绘画V6 ALPHA绘画模型，GPT语音对话使用，DALL-E3文生图+思维导图一站式解决方案

一、前言 ChatGPT3.5、GPT4.0、GPT语音对话、Midjourney绘画&#xff0c;文档对话总结DALL-E3文生图&#xff0c;相信对大家应该不感到陌生吧&#xff1f;简单来说&#xff0c;GPT-4技术比之前的GPT-3.5相对来说更加智能&#xff0c;会根据用户的要求生成多种内容甚至也可以和…
阅读更多...
STM32实现软件IIC协议操作OLED显示屏（2）

STM32实现软件IIC协议操作OLED显示屏（2）

时间记录&#xff1a;2024/1/27 一、OLED相关介绍 &#xff08;1&#xff09;显示分辨率128*64点阵 &#xff08;2&#xff09;IIC作为从机的地址0x78 &#xff08;3&#xff09;操作步骤&#xff1a;主机先发送IIC起始信号S&#xff0c;然后发送OLED的地址0x78&#xff0c;然…
阅读更多...
Unity 光照

Unity 光照

光照烘培 光照模式切换为 Baked 或 Mixed&#xff0c;Baked 模式完全使用光照贴图模拟光照&#xff0c;运行时修改光照颜色不生效&#xff0c;Mixed 模式也使用光照贴图&#xff0c;并且进行一些实时运算&#xff0c;运行时修改光照颜色会生效 受光照影响的物体勾选 Contribute…
阅读更多...
【RH850U2A芯片】Reset Vector和Interrupt Vector介绍

【RH850U2A芯片】Reset Vector和Interrupt Vector介绍

目录 前言 正文 1. 什么是Reset Vector 1.1 S32K144芯片的Reset Vector 1.2 RH850芯片的Reset Vector 2. 什么是Interrupt Vector 2.1 S32K144芯片的Interrupt Vector 2.2 RH850芯片的Interrupt Vector 3. Reset Vector等价于Interrupt Vector吗 4. 总结 前言 最近在…
阅读更多...
MongoDB实战

MongoDB实战

1.MongoDB介绍 1.1 什么是MongoDB MongoDB是一个文档数据库&#xff08;以JSON 为数据模型&#xff09;&#xff0c;由C语言编写&#xff0c;旨在为WEB应用提供可扩展的高性能数据存储解决方案。 文档来自于"JSON Document"&#xff0c;并非我们一般理解的 PDF&…
阅读更多...
【RTP】webrtc 学习3： webrtc对h264的rtp解包

【RTP】webrtc 学习3： webrtc对h264的rtp解包

rtp_rtcp\source\video_rtp_depacketizer_h264.cc【RTP】webrtc 学习2： webrtc对h264的rtp打包 中分析了打包过程的代码，这样再来看解析过程的源码就容易多了：本代码主要基于m79，m98类似。解析ParseFuaNalu 第一个字节只取 FNRI第二个字节取 原始的nalu type识别第一个分片…
阅读更多...
【机器学习笔记】1 线性回归

【机器学习笔记】1 线性回归

回归的概念 二分类问题可以用1和0来表示 线性回归&#xff08;Linear Regression&#xff09;的概念 是一种通过属性的线性组合来进行预测的线性模型&#xff0c;其目的是找到一条直线或者一个平面或者更高维的超平面&#xff0c;使得预测值与真实值之间的误差最小化&#x…
阅读更多...
网络安全视野：2024 年的人工智能、弹性和协作

网络安全视野：2024 年的人工智能、弹性和协作

在不断发展的网络安全环境中&#xff0c;确保公司运营安全并保障客户体验是一项复杂而关键的挑战&#xff0c;特别是对于在边缘运营的大型组织而言。当我们展望未来时&#xff0c;必须承认人工智能 (AI) 对网络安全领域的深远影响。本文深入研究了2024 年的预测&#xff0c;将其…
阅读更多...
接口自动化测试问题汇总

接口自动化测试问题汇总

本篇文章分享几个接口自动化用例编写过程遇到的问题总结&#xff0c;希望能对初次探索接口自动化测试的小伙伴们解决问题上提供一小部分思路。 sql语句内容出现错误 空格&#xff1a;由于有些字段判断是变量&#xff0c;需要将sql拼接起来&#xff0c;但是在拼接字符串时没有…
阅读更多...
OpenCV-27 Canny边缘检测

OpenCV-27 Canny边缘检测

一、概念 Canny边缘检测算法是John F.Canny与1986年开发出来的一个多级边缘检测算法&#xff0c;也被很多人认为是边缘检测的最优算法。最优边缘检测的三个主要评价标准是&#xff1a; 低错频率&#xff1a;表示出尽可能多的实际边缘&#xff0c;同时尽可能的减小噪声产生的误…
阅读更多...
【QT+QGIS跨平台编译】之十二：【libpng+Qt跨平台编译】（一套代码、一套框架，跨平台编译）

【QT+QGIS跨平台编译】之十二：【libpng+Qt跨平台编译】（一套代码、一套框架，跨平台编译）

文件目录 一、libpng介绍二、文件下载三、文件分析四、pro文件五、编译实践一、libpng介绍 PNG（Portable Network Graphics，便携式网络图形），是一种采用无损压缩算法的位图格式，支持索引、灰度、RGB三种颜色方案以及Alpha通道等特性。 PNG使用从LZ77派生的无损数据压缩算…
阅读更多...
文心一言 VS ChatGPT ：谁是更好的选择？

文心一言 VS ChatGPT ：谁是更好的选择？

前言 目前各种大模型、人工智能相关内容覆盖了朋友圈已经各种媒体平台&#xff0c;对于Ai目前来看只能说各有千秋。GPT的算法迭代是最先进的&#xff0c;但是它毕竟属于国外产品&#xff0c;有着网络限制、注册限制、会员费高昂等弊端&#xff0c;难以让国内用户享受。文心一言…
阅读更多...
移动Web——平面转换-平移

移动Web——平面转换-平移

1、平面转换-平移 取值 像素单位数值百分比&#xff08;参照盒子自身尺寸计算结果&#xff09;正负均可 技巧 translate()只写一个值&#xff0c;表示沿着X轴移动单独设置X或Y轴移动距离&#xff1a;translateX()或translateY() <!DOCTYPE html> <html lang"en&q…
阅读更多...
短视频账号矩阵系统+无人直播系统源码技术开发

短视频账号矩阵系统+无人直播系统源码技术开发

短视频账号矩阵系统无人直播系统源码技术开发涉及到多个领域&#xff0c;包括但不限于前端开发、后端开发、数据库设计、网络通信等。 以下是一些基本技术的步骤和注意事项&#xff1a; 1.技术需求分析设计&#xff1a;首先&#xff0c;需要明确开发短视频账号矩阵系统和无人直…
阅读更多...
使用mergekit 合并大型语言模型

使用mergekit 合并大型语言模型

模型合并是近年来兴起的一种新技术。它允许将多个模型合并成一个模型。这样做不仅可以保持质量&#xff0c;还可以获得额外的好处。 假设我们有几个模型:一个擅长解决数学问题&#xff0c;另一个擅长编写代码。在两种模型之间切换是一个很麻烦的问题&#xff0c;但是我们可以将…
阅读更多...
腾讯云轻量应用Ubuntu服务器如何一键部署幻兽帕鲁Palworld私服？

腾讯云轻量应用Ubuntu服务器如何一键部署幻兽帕鲁Palworld私服？

幻兽帕鲁/Palworld是一款2024年Pocketpair开发的开放世界生存制作游戏&#xff0c;在帕鲁的世界&#xff0c;玩家可以选择与神奇的生物“帕鲁”一同享受悠闲的生活&#xff0c;也可以投身于与偷猎者进行生死搏斗的冒险。而帕鲁可以进行战斗、繁殖、协助玩家做农活&#xff0c;也…
阅读更多...
最新文章

Copyright @ 2022~2023