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

2024-01-28 05:20

本文主要是介绍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 快捷键)

......
@Overridepublic 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);}@Overridepublic 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:表示当前要添加的元素已经存在,含弃@Overridepublic 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>() {@Overridepublic 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 接口再说。

这篇关于JAVA_Set系列集合:HashSet、LinkedHashSet、TreeSet底层详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/652575

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听