Java数据结构第二十三期:Map与Set的高效应用之道(二)

专栏:Java数据结构秘籍

个人主页:手握风云

目录

一、哈希表

1.1. 概念

1.2. 冲突

1.3. 避免冲突

1.4. 解决冲突

1.5. 实现

二、OJ练习

2.1. 只出现一次的数字

2.2. 随机链表的复制

 2.3. 宝石与石头


一、哈希表

1.1. 概念

        顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找⼀个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(n),平衡树中为树的⾼度,即O(n),搜索的效率取决于搜索过程中元素的比较次数。

        理想的搜索⽅法:可以不经过任何比较,⼀次直接从表中得到要搜索的元素。如果构造⼀种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。

        当向该结构中,根据待插⼊元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放;对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。该方式即为哈希(散列)方法,哈希方法中使⽤的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

        哈希函数设置为:hash(key) = key % capacity;其中capacity为存储元素底层空间总的大小。

        我们设一个整数集合{1,7,6,4,5,9},把capacity设置为10,那我们就可以按照下图来存储。如果我们再想存放一个元素12,我们可以直接通过哈希函数存进下标2中,要想搜索,直接通过2下标来找到12,这样时间复杂度为O(n),从而提高效率。

1.2. 冲突

        不同关键字通过相同哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。把具有不同关键码⽽具有相同哈希地址的数据元素称为“同义词”。例如我们要想存放一个14,通过上面的哈希函数应该存到4下标,但此时4下标已经存了一个4,就会造成哈希冲突。

        出现了哈希冲突,我们就要想办法避免冲突。由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,就会导致冲突的发⽣是必然的,但我们能做的应该是尽量的降低冲突率。

1.3. 避免冲突

        第一种方法可以设计合理的哈希函数。设计原则:定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间;计算出来的地址能均匀分布在整个空间中;比较简单。

        直接订制法:取关键字的某个线性函数为散列地址:Hash(Key) = A*Key + B。优点:简单、均匀。缺点:需要事先知道关键字的分布情况。使用场景:适合查找比较小且连续的情况。

        除留余数法:设散列表中允许的地址数为m,取⼀个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址。

        哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突。

        我们还有另外一种就是调节负载因子。哈希表的载荷因子为:ą=填入表中元素个数/哈希表长度。当冲突率达到⼀个⽆法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率。已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。

1.4. 解决冲突

        解决哈希冲突两种常⻅的⽅法是:闭散列和开散列。

        闭散列:也叫开放地址法,当发⽣哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下⼀个” 空位置中去。那如何寻找下⼀个空位置呢?此时我们就需要应用线性探索。从发生冲突的位置开始,依次向后探测,直到寻找到下⼀个空位置为止。但这样还是会有一个缺点,就是会使得冲突元素聚集在一起,并且如果我们把4删除了,又如何寻找14、24、34这些元素。因此线性探测采⽤标记的伪删除法来删除⼀个元素。

        ⼆次探测为了避免该问题,找下⼀个空位置的⽅法为:Hi = (H0+i^2)%m,i表示冲突的次数,m为表的大小。

        开散列:开散列法⼜叫链地址法(开链法),⾸先对关键码集合⽤散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每⼀个⼦集合称为⼀个桶,各个桶中的元素通过⼀个单链表链接起来,各链表的头结点存储在哈希表中。

1.5. 实现

        由于我们需要节点数组来创建哈希表,利用内部类来表示节点对象。

public class HashBucket {//创建节点数组static class Node{public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}public Node[] array = new Node[10];public int UsedSize;//表示还系统中存放的元素public static final float LOAD_FACTOR = 0.75f;//负载因子表示为常数
}

        我们先来模拟哈希表中放元素的方法。我们要想把元素放入,首先得是一个结点。比如key=14,如果表中已经有14了,就不能再放14并且更新val,所以我们首先需要遍历数组判断key是否相同,如果相同,更新val。下面再使用头插法来把节点元素放入哈希表中。插入元素之后,我们还需要重新计算负载因子是否超过了我们规定的LOAD_FACTOR。如果超过了,就需要进行扩容操作。扩容的时候还需要注意,比如我们要插入的元素的key为14,扩容前需要插入下标为4的位置,扩容2倍后,就需要插入下标为14的位置。

        完整代码实现:

    public void put(int key, int val) {int index = key % array.length;//先遍历index数组下的链表,如果有相同的key,则更新valNode cur = array[index];while (cur != null) {if (cur.key == key) {cur.val = val;return;}cur = cur.next;}//头插法Node node = new Node(key, val);node.next = array[index];array[index] = node;UsedSize++;//重新计算负载因子是不是超过了我们规定的值if (CalculateLoadFactor() >= LOAD_FACTOR) {//扩容ReSize();}}private float CalculateLoadFactor() {return UsedSize * 1.0f / array.length;}private void ReSize() {Node[] newArray = new Node[array.length*2];for (Node node : array) {Node cur = node;while (cur != null) {int newIndex = cur.key % newArray.length;//把当前节点放入新数组的位置,再次使用头插法Node curNext = cur.next;cur.next = newArray[newIndex];newArray[newIndex] = cur;cur = curNext;}}array = newArray;}

        get方法也是一样,也是通过索引下标来寻找目标值。

    public int get(int key){int index = key % array.length;Node cur = array[index];while(cur != null){if(cur.key == key){return cur.val;}cur = cur.next;}return -1;}

        我们在Test类里面进行实例化并调试。

public class Test {public static void main(String[] args) {HashBucket hashBucket = new HashBucket();hashBucket.put(11,99);hashBucket.put(2,99);hashBucket.put(43,99);hashBucket.put(4,99);hashBucket.put(14,99);hashBucket.put(24,99);hashBucket.put(7,99);hashBucket.put(8,99);}
}

        我们上面的方法key是整型,那如果key是引用类型呢,比如String或者Person类。那我们就把整型换作是泛型K、V。需要注意的是,key换成了泛型,不能直接进行%操作,我们可以使用hashCode方法转成整型,并且进行比较要使用equals方法。

/*** @author: gao* @create-date: 2025/3/15 16:32*/public class HashBucket<K, V> {static class Node<K, V> {public K key;public V val;public Node<K, V> next;public Node(K key, V val) {this.key = key;this.val = val;}}public Node<K, V>[] array = (Node<K, V>[]) new Node[10];public int UsedSize;//表示还系统中存放的元素public static final float LOAD_FACTOR = 0.75f;//负载因子表示为常数public void put(K key, V val) {int hashcode = key.hashCode();int index = hashcode % array.length;//先遍历index数组下的链表,如果有相同的key,则更新valNode<K, V> cur = array[index];while (cur != null) {if (cur.key == key) {cur.val = val;return;}cur = cur.next;}Node<K, V> node = new Node<K, V>(key, val);node.next = array[index];array[index] = node;UsedSize++;}public V get(K key) {int hashcode = key.hashCode();int index = hashcode % array.length;Node<K, V> cur = array[index];while (cur != null) {if (cur.key.equals(key)) {return cur.val;}cur = cur.next;}return null;}
}

        如果我们要判断是否为同一个人,我们可以判断身份证号码是否相等。如果我们按照这种方法去写,发现比较结果为false。这是因为我们没有重写equals和hashCode方法,编译器默认调用Object方法。

class Person {public String id;public Person(String id) {this.id = id;}
}public class Test {public static void main(String[] args) {Person person1 = new Person("1234");Person person2 = new Person("1234");System.out.println(person1.equals(person2));System.out.println(person1.hashCode());System.out.println(person2.hashCode());}
}

    public boolean equals(Object obj) {return (this == obj);}

        我们在Person类里面右击,点击Generate,再点击equals() and hashCode(),就可以重写。

    @Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return Objects.equals(id, person.id);}@Overridepublic int hashCode() {return Objects.hash(id);}

二、OJ练习

2.1. 只出现一次的数字

        我们的基本思路是:利用HashSet,先遍历一遍数组,把集合中没有的数字放入,如果有,再移除,最后集合中剩下的元素就是只出现一次的数字,再遍历一遍数组,匹配HashSet中的数组。

        完整代码实现:

class Solution {public int singleNumber(int[] nums) {Set<Integer> set = new HashSet<>();for (int i = 0;i < nums.length;i++) {if(! set.contains(nums[i])){set.add(nums[i]);}else{set.remove(nums[i]);}}for (int i = 0;i < nums.length;i++) {if(set.contains(nums[i])){return nums[i];}}return -1;}
}

        执行时间还是比较高,因为使用了两次for循环遍历数组。

2.2. 随机链表的复制

        题目比较长,大概题意就是复制出一份与原来相同的链表。这道题的难点在于比单链表多了一个可以指向任意节点或者空的random域。起初,很多人会去想定义一个Node cur去遍历一遍链表,一个一个节点进行拷贝,但一拷贝就会发现问题,因为我们我们不知道cur.next和cur.random是哪一个节点的地址。既然遍历一遍链表不行,那就遍历两遍。第一遍遍历,所有节点的val域全都拷贝过来,next域以及random域全都默认为null,每遍历一个链表,就新实例化一个节点。然后我们<K,V>结构来建立老节点与新节点之间的映射关系。

        我们每获取一个节点的地址,都可以修改它的next域与random域。

        完整代码实现:

class Solution {public Node copyRandomList(Node head) {Map<Node,Node> map = new HashMap<>();//第一遍遍历链表Node cur = head;while(cur != null){Node node = new Node(cur.val);map.put(cur,node);cur = cur.next;}//第二遍遍历链表cur = head;while(cur != null){map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}return map.get(head);}
}

 2.3. 宝石与石头

        题目很简单,就是查找stones中含有jewels中的字符的个数。我们先遍历jewels字符串,将里面的字符放入集合中,再去遍历stones中的字符,最后返回宝石个数。

        完整代码实现:

class Solution {public int numJewelsInStones(String jewels, String stones) {Set<Character> set = new HashSet<>();for (int i = 0; i < jewels.length(); i++) {char ch = jewels.charAt(i);set.add(ch);}int count = 0;for (int i = 0; i < stones.length(); i++) {char ch = stones.charAt(i);if(set.contains(ch)){count++;}}return count;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OSPF | LSDB 链路状态数据库 / SPF 算法 / 实验

注&#xff1a;本文为 “OSPF | LSDB / SPF ” 相关文章合辑。 LSDB 和 SPF 算法 潇湘浪子的蹋马骨汤 发布 2019-02-15 23:58:46 1. 链路状态数据库 (LSDB) 链路状态协议除了执行洪泛扩散链路状态通告&#xff08;LSA&#xff09;以及发现邻居等任务外&#xff0c;其第三个任…

Android Framework 之了解系统启动流程二

Android Framework 源码阅读系列篇章有&#xff1a; 系统启动流程一之init进程和zygote进程启动分析系统启动流程二之SystemServer进程启动分析 1. SystemServer 进程启动分析 在 系统启动流程一之init进程和zygote进程启动分析 中分析 zygote 进程时&#xff0c;我们知道了…

阿里云企业邮箱出现故障怎么处理?

阿里云企业邮箱出现故障怎么处理&#xff1f; 以下是处理阿里云企业邮箱故障的详细分步指南&#xff0c;帮助您快速定位问题并恢复邮箱正常使用&#xff1a; 一、初步排查&#xff1a;确认故障范围与现象 确定影响范围 全体用户无法使用 → 可能为阿里云服务端故障或网络中断。…

Python----数据分析(Pandas二:一维数组Series,Series的创建,Series的属性,Series中元素的索引与访问)

一、一维数组Series Series&#xff1a;一维数组,与Numpy中的一维array类似。它是一种类似于一维数组的对象&#xff0c;是由一组数据(各种 NumPy 数据类型)以及一组与之相关的数据标签(即索引)组成。 仅由一组数据也可产生简单的 Series 对象&#xff0c;用值列表生成 Series …

小程序配置

注册小程序账号和安装开发工具 参考文档&#xff1a;注册小程序账号和安装开发工具https://blog.csdn.net/aystl_gss/article/details/127878658 HBuilder新建项目 填写项目名称&#xff0c;选择UNI-APP&#xff0c;修改路径&#xff0c;点击创建 manifest.json 配置 需要分别…

前端UI编程基础知识:基础三要素(结构→表现→行为)

以下是重新梳理的前端UI编程基础知识体系&#xff0c;结合最新技术趋势与实战要点&#xff0c;以更适合快速掌握的逻辑结构呈现&#xff1a; 一、基础三要素&#xff08;结构→表现→行为&#xff09; 1. HTML5 核心能力 • 语义化标签&#xff1a;<header>, <nav&g…

【eNSP实战】将路由器配置为DHCP服务器

拓图 要求&#xff1a; 为 office100 和 office200 分别配置地址池 AR1接口配置 interface GigabitEthernet0/0/0ip address 192.168.100.1 255.255.255.0 # interface GigabitEthernet0/0/1ip address 192.168.200.1 255.255.255.0 AR1路由器上创建office100地址池 [AR1…

Stable Diffusion 模型具体如何设置参数?

基础参数设置 随机种子&#xff08;seed&#xff09;&#xff1a;设置一个固定的随机种子值&#xff0c;可以确保在相同文本提示下生成相同的图像。如果设置为-1&#xff0c;则每次生成的图像都是随机的。 num_inference_steps&#xff1a;控制模型推理的步数。步数越多&#…

阿里云服务器购买及环境搭建宝塔部署springboot和vue项目

云服务器ECS_云主机_服务器托管_计算-阿里云 一、前言 对于新手或者学生党来说&#xff0c;有时候就想租一个云服务器来玩玩或者练练手&#xff0c;duck不必花那么多钱去租个服务器。这些云服务厂商对学生和新手还是相当友好的。下面将教你如何快速搭建自己的阿里云服务器&…

ABAP语言的动态编程(4) - 综合案例:管理费用明细表

本篇来实现一个综合案例&#xff1a;管理费用明细表。报表在实际项目中&#xff0c;也有一定的参考意义&#xff0c;一方面展示类似的报表&#xff0c;比如管理费用、研发费用等费用的明细&#xff0c;使用业务比较习惯的展示格式&#xff1b;另一方面正好综合运用前面学习的动…

【Python办公】Excel通用匹配工具(双表互匹)

目录 专栏导读1、背景介绍2、库的安装3、核心代码4、完整代码总结专栏导读 🌸 欢迎来到Python办公自动化专栏—Python处理办公问题,解放您的双手 🏳️‍🌈 博客主页:请点击——> 一晌小贪欢的博客主页求关注 👍 该系列文章专栏:请点击——>Python办公自动化专…

2025-03-15 吴恩达机器学习2——线性回归模型

文章目录 1 概述1.1 案例1.2 分析 2 代价函数2.1 代价函数公式2.2 理解代价函数2.3 可视化代价函数 3 梯度下降3.1 实现步骤3.2 理解梯度下降3.3 学习率 4 最佳实践4.1 导入数据4.2 代码实现4.3 可视化 1 概述 ​ 线性回归模型是使用最广泛的学习算法&#xff0c;让我们从一个…

Webpack 前端性能优化全攻略

文章目录 1. 性能优化全景图1.1 优化维度概览1.2 优化效果指标 2. 构建速度优化2.1 缓存策略2.2 并行处理2.3 减少构建范围 3. 输出质量优化3.1 代码分割3.2 Tree Shaking3.3 压缩优化 4. 运行时性能优化4.1 懒加载4.2 预加载4.3 资源优化 5. 高级优化策略5.1 持久化缓存5.2 模…

实验篇| CentOS 7 下 Keepalived + Nginx 实现双机高可用

为什么要做双机高可用&#xff1f;‌ 想象一下&#xff1a;你的网站突然宕机&#xff0c;用户无法访问&#xff0c;订单流失、口碑暴跌…&#x1f4b8; ‌双机热备‌就是解决这个痛点的终极方案&#xff01;两台服务器互为备份&#xff0c;724小时无缝切换&#xff0c;保障业务…

C语言【内存函数】详解加模拟实现

目录&#xff1a; 1. memcpy使用和模拟实现 2. memmove使用和模拟实现 3. memset函数的使用 4. memcmp函数的使用 以上函数均包含在一个头文件<string.h>里面 一、memcpy的使用和模拟实现。 memcpy函数介绍&#xff1a; 函数原型&#xff1a; void * memcpy ( void…

Flutter——Android与Flutter混合开发详细教程

目录 1.创建FlutterModule项目&#xff0c;相当于Android项目里面的module库&#xff1b;2.或者编辑aar引用3.创建Android原生项目3.直接运行跑起来 1.创建FlutterModule项目&#xff0c;相当于Android项目里面的module库&#xff1b; 2.或者编辑aar引用 执行 flutter build a…

Windows根据文件名批量在文件夹里查找文件并复制出来,用WPF实现的详细步骤

项目前言 在日常工作和生活中&#xff0c;我们常常会遇到需要从大量文件中根据文件名批量查找特定文件并复制到指定位置的情况。手动一个个查找和复制文件不仅效率低下&#xff0c;还容易出错。使用 Windows Presentation Foundation (WPF) 可以创建一个用户友好的图形界面应用…

matlab 控制系统GUI设计-PID控制超前滞后控制

1、内容简介 matlab164-控制系统GUI设计-PID控制超前滞后控制 可以交流、咨询、答疑 2、内容说明 略 3、仿真分析 略 4、参考论文 略

【大模型基础_毛玉仁】2.4 基于 Encoder-Decoder 架构的大语言模型

更多内容&#xff1a;XiaoJ的知识星球 目录 2.4 基于 Encoder-Decoder 架构的大语言模型2.4.1 Encoder-Decoder 架构2.4.2 T5 语言模型1&#xff09;T5 模型结构2&#xff09;T5 预训练方式3&#xff09;T5 下游任务 2.4.3 BART 语言模型1&#xff09;BART 模型结构2&#xff0…

AI智能代码疫苗技术,赋能数字化应用内生安全自免疫

“DevSecOps市占率持续领先&#xff0c;IAST探针覆盖率十倍增长&#xff0c;代码疫苗技术已成功帮助上千家行业用户成功抵御‘Log4j2.x’等重大未知漏洞的利用攻击。”子芽在腾讯专访中透露。 这是2021年悬镜安全交出的一张成绩单。悬镜安全是DevSecOps敏捷安全先行者&#xf…