当前位置： 首页 > news >正文

我就不信你还不懂HashSet/HashMap的底层原理

news 来源：原创 2024/5/7 4:16:51

💥注💥


💗阅读本博客需备的前置知识如下💗

  • 🌟数据结构常识🌟👉1️⃣八种数据结构快速扫盲
  • 🌟Java集合常识🌟👉2️⃣Java单列集合扫盲

⭐️本博客知识点收录于⭐️👉🚀《JavaSE系列教程》:🚀—>🚗11【泛型、Map、异常】🚗

文章目录

  • 二、Set集合
    • 2.1 Set集合概述
    • 2.2 HashSet 集合
      • 2.2.1 HashSet数据结构
        • 1）HashSet简介
        • 2）Hash冲突1
        • 3）Hash冲突2
        • 4）HashSet底层存储原理
        • 5）HashSet特点总结
      • 2.2.2 HashSet去重原理
      • 2.2.3 HashSet存储测试
        • 1）hash冲突情况1
        • 2）hash冲突情况2

二、Set集合

2.1 Set集合概述

Set接口和List接口一样，继承与Collection接口，也是一个单列集合；Set集合中的方法和Collection基本一致；并没有对Collection接口进行功能上的扩充，只是底层实现的方式不同了（采用的数据结构不一样）；

  • Set集合体系结构：

在这里插入图片描述

2.2 HashSet 集合

2.2.1 HashSet数据结构

1）HashSet简介

HashSet是Set接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的（即存取顺序不一致）。

HashSet底层数据结构在JDK8做了一次重大升级，JDK8之前采用的是Hash表，也就是数组+链表来实现；到了JDK8之后采用数组+链表+红黑树来实现；

Tips：关于红黑树我们暂时理解为红黑树就是一颗平衡的二叉树（即使他不是绝对平衡）；

  • HashSet简单使用：
package com.dfbz.demo01;

import java.util.HashSet;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Demo01 {
    public static void main(String[] args) {
        //创建 Set集合
        HashSet set = new HashSet<String>();

        //添加元素
        set.add("湖北");
        set.add("河北");
        set.add("河北");          // HashSet带有去重特点,"河北"已经存储过了,不会再存储

        System.out.println(set);            // [河北, 湖北]
    }
}

HashSet判断两个元素是否重复的依据是什么呢？下面案例代码HashSet将会存储几个元素呢？

  • 示例代码：
package com.dfbz.demo01;

import java.util.HashSet;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Demo01 {
    public static void main(String[] args) {
        //创建 Set集合
        HashSet<String> set = new HashSet();

        //添加元素
        set.add(new String("河北"));
        set.add("湖北");
        set.add("河北");
        set.add("湖北");

        System.out.println(set.size());                // ?

        System.out.println("--------------------");

        HashSet<A> set2 =new HashSet<>();
        set2.add(new A());
        set2.add(new A());

        System.out.println(set2.size());                 // ?
    }
}

class A{}

要探究HashSet的去重原理我们需要继续往下看！

2）Hash冲突1

我们知道hash表数据结构的特点是：根据元素的hash值来对数组的长度取余，最终计算出元素所要存储的位置；Object类中有一个特殊的方法hashCode()，该方法被native关键字修饰（不是采用Java语言实现）；

  • public native int hashCode()：获取该对象的hash值，默认情况下根据该对象的内存地址值来计算；

默认情况下，对象的hash值是根据对象的内存地址值来计算；但是这种hash算法并不是特别完美，有时候不同的两个对象（内存地址值不一致）计算出来的hash值可能会一样，我们把这种情况称为hash冲突。尽管这种情况非常少，但依旧存在；

  • 下面是String类对hashCode代码的实现：
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

String默认情况下是获取每一个字符的ASCII码来参与hashCode的计算，在上面算法中，AB和BA得出的hashCode是不一致的；有效的解决了一定情况下的hash冲突问题，但是hash算法不能保证在所有情况下hash都能唯一；

例如Aa和BB的hashCode却是一样的，这种造成了Hash冲突问题；

Aa:
h = 31*0+65
h = 31*65+97
h = 2112
BB:
h = 31*0+66
H = 31*66+66
h = 2112
  • 示例代码：
package com.dfbz.demo01;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Demo01 {
    public static void main(String[] args) {

        System.out.println("Aa".hashCode()); // 2112
        System.out.println("BB".hashCode()); // 2112
    }
}

通过String类对hashCode的实现可以看出来：hash算法并不能绝对的保证两个不同的对象算出来的hash值不一样，当hash冲突时，HashSet将会调用当前对象的equlas方法来比较两个对象是否一致，如果一致则不存储该元素；

在这里插入图片描述

3）Hash冲突2

假设数组的长度为9，当元素1的hash值为6，元素2的hash值为15，计算的数组槽位都是6，同样的，那么这个时候也会触发hash冲突问题；

  • Integer对hashCode的实现：
@Override
public int hashCode() {
    return Integer.hashCode(value);
}
  • Integer.hashCode()：
public static int hashCode(int value) {
    // 就是返回元素本身
    return value;
}
  • 示例代码：
package com.dfbz.demo01;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Demo10 {
    public static void main(String[] args) {
        System.out.println(new Integer(15).hashCode());         // 15
        System.out.println(new Integer(6).hashCode());          // 6
    }
}

Tips：Integer的hashCode就是本身数值；

HashSet存储时的Hash冲突情况（假设散列表中的数组长度为9）：

在这里插入图片描述

发生上面这种Hash冲突时HashSet采用拉链法，将新增的元素添加到上一个元素之后形成链表；

需要注意的是：

  • 1）hashCode一致的两个对象不能说明两个对象一定相同，因为可能会造成hash冲突（例如上面的Aa和BB）
  • 2）但是如果hashCode不同，则一定能说明这两个对象肯定不同，因为同一个对象计算的hashCode永远一样；

因此在hash冲突的第二种情况下，并不需要调用equals来去重；而是采用拉链法直接将新添加的元素链在后面形成链表；

4）HashSet底层存储原理

我们前面了解过HashSet底层采用的是散列表这种数据结构（数组+链表），并且在JDK1.8对传统的散列表进行了优化，增加了红黑树来优化链表查询慢的情况；在默认情况下，HashSet中散列表的数组长度为16，并通过负载因子来控制数组的长度；HashSet中负载因子默认为0.75；

负载因子=HashSet中存储的元素/数组的长度

由此可以得出当HashSet中的元素个数为12个时（16*0.75=12），将进行数组的扩容，默认情况下将会扩容到原来的2倍；数组长度将会变为32，由公式可以推算出，下一次HashSet数组扩容时元素个数将为32*0.75=24，以此类推…

负载因子是控制数组扩容的一个重要参数；并且HashSet允许我们在创建时指定负载因子和数值的默认容量大小；

HashSet底层存储如图所示：

在这里插入图片描述

上述图中是一个hash表数据结构（数组+链表），也是JDK8之前的HashSet底层存储结构或者说还未达到阈值转换为红黑树的时候；

当存储的元素越来越多，hash也越来越多时，势必造成链表长度非常长，查找元素时性能会变得很低；在JDK8中当链表长度到达指定阈值8，并且数组容量达到了64时，将链表转换为红黑树，这样大大降低了查询的时间；

如图所示：

在这里插入图片描述

5）HashSet特点总结

  • 1）存取无序，元素唯一，先比较hashCode，
    • 1）Hash冲突情况1：hash值直接冲突了，当hash冲突时再比较equals，equals返回true则不存；
    • 2）Hash冲突情况2：hash值没有冲突，但是%数组的长度得到槽位冲突了，使用拉链法形成链表
  • 2）底层采用Hash表数据结构，当数组长度大于等于64并且链表长度大于等于8时，链表将会转换为红黑树，当长度降到6时将会重新转换为链表；
  • 3）HashSet默认数组长度为16，默认的负载因子为0.75；
  • 4）每次数组扩容时，默认扩容到原来的2倍；

2.2.2 HashSet去重原理

前面在分析hash冲突时就得出了结论：HashSet保证元素唯一性的方式依赖于：hashCode与equals方法。

来解释我们之前的问题：

package com.dfbz.demo01;

import java.util.HashSet;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Demo01 {
    public static void main(String[] args) {
        //创建 Set集合
        HashSet<String> set = new HashSet();

        //添加元素
        set.add(new String("河北"));
        set.add("河北");

        System.out.println(set.size());                 // ?
    }
}
  • 分析：

HashSet在存储元素时，都会调用对象的hashCode()方法计算该对象的hash值，如果hash值与集合中的其他元素一样，则调用equals方法对冲突的元素进行对比，如果equals方法返回true，说明两个对象是一致的，HashSet并不会存储该对象，反之则存储该元素；

一般情况下，不同对象的hash值计算出来的结果是不一样的，但还是有某些情况下，不同一个对象的hash值计算成了同一个，这种情况我们称为hash冲突；当hash冲突时，HashSet会调用equals方法进行对比，默认情况下equals方法对比的是对象内存地址值，因此如果对象不是同一个，equals返回的都是false；

在这里插入图片描述

另外，Java中的HashSet还进行了优化，如果两个字符串都是存储在常量池，那么直接在常量池中进行判断，不需要调用equals来判断是否重复；

  • 示例代码：
package com.dfbz.demo01;

import java.util.HashSet;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Demo02 {
    public static void main(String[] args) {
        //创建 Set集合
        HashSet<String> set = new HashSet();

        set.add("河北");
        
        /*
         存储第二个"河北"时,hashSet发现两个hashCode一致
         并且都是存储在常量池,因此都不需要调用equals来判断这个元素是否存在hashSet
         */
        set.add("河北");

        System.out.println(set.size());                 // 2
    }
}

2.2.3 HashSet存储测试

1）hash冲突情况1

HashSet的去重原理是依靠对象的hashCode和equals方法来决定是否要存储这个对象的；如果不同的两个对象其hashCode是不同的，即使hash冲突了，equals也不可能相同（默认情况下，Object中的equals比较是两个对象的内存地址值）；

但是在实际开发中，地址值并不是我们用来判断两个对象是否相等的依据，我们的习惯是，对象中的属性相等即判断两个对象是同一个对象；

  • 定义一个Person类：
package com.dfbz.demo01;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Person {

    private String name;
    private Integer age;

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    public Person() {
    }

    public Person(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }
}
  • 测试类：
package com.dfbz.demo01;

import java.util.HashSet;
import java.util.Set;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Demo02 {
    public static void main(String[] args) {
        Set persons = new HashSet<>();

        persons.add(new Person("小灰", 20));
        persons.add(new Person("小灰", 20));

        System.out.println(persons.size());         // 2
    }
}

默认情况下，hashCode的值是根据对象的内存地址值计算的，hashCode应该不一样，即使hashCode一样（hash冲突）调用equals返回值也是false，因为equlas默认的比较规则是比较两个对象的内存地址值

但是我们在实际开发中，即使new了两个对象，如果里面的属性是完全一样的，我们就认为两个对象是同一个对象，HashSet应该帮我们去除这样的重复对象；

我们可以重写hashCode和equals方法：

@Override
public boolean equals(Object o) {

    System.out.println("equals执行了...");
    // 为了测试,这样固定死是毫无意义的
    return false;
}

@Override
public int hashCode() {
    
    System.out.println("hashCode执行了...");
    // 为了测试,这样固定死是毫无意义的
    return 1;
}

测试代码：

package com.dfbz.demo01;

import java.util.HashSet;
import java.util.Set;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Demo02 {
    public static void main(String[] args) {

        Set persons = new HashSet<>();

        persons.add(new Person("小灰", 20));
        persons.add(new Person("小蓝", 18));

        System.out.println(persons.size());         // 1
    }
}

运行结果：

在这里插入图片描述

分析：

1）存储第一个Person对象时，调用这个Person对象的hashCode方法得出：1，并将其存储起来

2）存储第二个Person对象时，调用这个Person对象的hashCode方法得出：1，发现集合中已经有了hashCode为1的对象，因此调用Person对象的equals方法，将冲突了的Person对象传入（第一次添加的那个Person对象），然后equals方法返回的是true，因此不存这个Person对象（第二个Person对象），最终persons.size()为1；

真正的hashCode与equals的方法内部逻辑应该是：相同属性的对象的hashCode应该是一样的，也就是说hashCode应该根据对象属性来计算，并且equals对比的应该是对象属性的值；

使用idea快捷键：alt+insert

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3WT8GGut-1677985759628)(media/96.png)]

一直回车，生成hashCode和equals方法：

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Person person = (Person) o;
    return Objects.equals(name, person.name) &&
            Objects.equals(age, person.age);
}

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

此时再执行测试类：

在这里插入图片描述

将Person属性都改为一样的：

在这里插入图片描述

2）hash冲突情况2

当hashCode不一样，但是%数组的长度得到的槽位是一样时，也会产生hash冲突，但是这种hash冲突并不需要调用equals来判断，而是直接使用拉链法拼接在上一个元素的后面形成链表；

  • 示例代码：
package com.dfbz.demo01;

import java.util.HashSet;

/**
 * @author lscl
 * @version 1.0
 * @intro:
 */
public class Demo01 {
    public static void main(String[] args) {
        HashSet<A> set = new HashSet();

        set.add(new A(1));              // 1 % 16 = 1
        set.add(new A(17));             // 17 % 16 = 1

        System.out.println(set);
    }
}

class A {

    private Integer num;

    @Override
    public boolean equals(Object o) {
        System.out.println("equals调用了...");
        return false;
    }

    @Override
    public int hashCode() {
        return this.num;
    }

    public A(Integer num) {
        this.num = num;
    }
}

运行程序，发现并没有调用equals：

在这里插入图片描述

相关文章：

  • pytorch学习之pytorch构建模型的流程
  • react-swipeable-views轮播图实现下方的切换点控制组件
  • Java线程知识点总结
  • Android Compose——一个简单的Bilibili APP
  • 世界顶级五大女程序媛，不仅技术强还都是美女
  • 2023年再不会Redis，就要被淘汰了
  • 【学习笔记】深入理解JVM之垃圾回收机制
  • 【数据结构】链式二叉树
  • 自学大数据第三天~终于轮到hadoop了
  • 应用层协议 HTTP HTTPS
  • Linux内核学习笔记——页表的那些事。
  • 一文带你入门，领略angular风采（上）！！！
  • 嵌入式学习笔记——STM32硬件基础知识
  • 2023年“网络安全”赛项浙江省金华市选拔赛 任务书
  • Qt安装与使用经验分享；无.pro文件；无QTextCodec file；Qt小试；界面居中；无缝；更换Qt图标；更换Qt标题。
  • 【个人向】《HTTP图解》阅后小结
  • el-input获取焦点 input输入框为空时高亮 el-input值非法时
  • emacs初体验
  • Facebook AccountKit 接入的坑点
  • IE报vuex requires a Promise polyfill in this browser问题解决
  • JavaScript类型识别
  • laravel 用artisan创建自己的模板
  • Xmanager 远程桌面 CentOS 7
  • 程序员最讨厌的9句话，你可有补充？
  • 从0实现一个tiny react（三）生命周期
  • 近期前端发展计划
  • 扑朔迷离的属性和特性【彻底弄清】
  • 数据科学 第 3 章 11 字符串处理
  • 写给高年级小学生看的《Bash 指南》
  • media数据库操作，可以进行增删改查，实现回收站，隐私照片功能 SharedPreferences存储地址：
  • 【云吞铺子】性能抖动剖析（二）
  • ​草莓熊python turtle绘图代码（玫瑰花版）附源代码
  • #define
  • #Java第九次作业--输入输出流和文件操作
  • #NOIP 2014# day.1 T2 联合权值
  • #多叉树深度遍历_结合深度学习的视频编码方法--帧内预测
  • (+3)1.3敏捷宣言与敏捷过程的特点
  • （附源码）ssm教材管理系统 毕业设计 011229
  • （十五）devops持续集成开发——jenkins流水线构建策略配置及触发器的使用
  • (转)利用ant在Mac 下自动化打包签名Android程序
  • (转)重识new
  • .naturalWidth 和naturalHeight属性，
  • .NET Core 成都线下面基会拉开序幕
  • .NET Core 网络数据采集 -- 使用AngleSharp做html解析
  • .Net Core缓存组件(MemoryCache)源码解析
  • .net wcf memory gates checking failed
  • .NET简谈互操作(五：基础知识之Dynamic平台调用)
  • .stream().map与.stream().flatMap的使用
  • /bin/bash^M: bad interpreter: No such file ordirectory
  • @AliasFor注解
  • []error LNK2001: unresolved external symbol _m
  • [2019.2.28]BZOJ4033 [HAOI2015]树上染色
  • [ABP实战开源项目]---ABP实时服务-通知系统.发布模式
  • [BUUCTF NewStarCTF 2023 公开赛道] week4 crypto/pwn
  • [DevEpxress]GridControl 显示Gif动画