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

数据结构-哈希表

系列文章目录

1.集合-Collection-CSDN博客​​​​​​

2.集合-List集合-CSDN博客

3.集合-ArrayList源码分析(面试)_喜欢吃animal milk的博客-CSDN博客

4.数据结构-哈希表_喜欢吃animal milk的博客-CSDN博客


文章目录

目录

系列文章目录

文章目录

前言

一 . 什么是哈希表?

哈希碰撞

冲突避免

冲突解决

1.闭散列

1.1线性探测

​编辑

1.2 二元探测

2.开散列

二 . 代码实现


前言

大家好,今天给大家介绍一下哈希表相关内容以及模拟实现


一 . 什么是哈希表?

哈希表(Hash Table),也称为散列表,是一种根据关键码值(Key)而直接进行访问的数据结构。它通过将关键码值映射到表中的一个位置来访问记录,以加快查找的速度。

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

哈希表的基本思想是利用哈希函数将关键码值映射到表中的一个位置,然后在该位置上进行查找或插入操作。哈希函数将关键码值映射到表中的位置时,应该尽量避免冲突,即不同的关键码值映射到同一个位置。当两个不同的关键码值映射到同一个位置时,称为哈希冲突。

解决哈希冲突的常用方法有两种:

  1. 开放定址法:当发生冲突时,通过一定的规则找到下一个空的位置,将冲突的元素放到该位置。常见的开放定址法有线性探测法、二次探测法和双重哈希法。

  2. 链地址法:将哈希表的每个位置都设置为一个链表,当发生冲突时,将冲突的元素插入到链表中。链地址法可以处理任意数量的冲突,但是需要额外的空间来存储链表。

哈希表的优点是可以快速地进行插入、删除和查找操作,平均时间复杂度为 O(1)。但是它也有一些缺点,如哈希冲突的处理和空间的浪费等。

例如:数据集合{1,7,6,4,5,9}; 哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。


哈希碰撞

对于两个数据元素的关键字 Ki  和 Kj (i != j),有 Ki != Kj,但有:Hash(Ki ) == Hash(Kj ),即:不同关键字通过相同哈 希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。

想象一下,如果在上面的哈希表中插入44 hash(44) = 44%10 = 4 这个时候该怎么解决?

还记得上面提到的解决方法吗?


冲突避免

负载因子(Load Factor)是指哈希表中已存储元素个数与哈希表大小之比。它可以用来衡量哈希表的空间利用率。

负载因子的计算公式为:负载因子 = 已存储元素个数 / 哈希表大小。

负载因子的大小会影响哈希表的性能和空间利用率。当负载因子较小时,表示哈希表中的元素较少,空间利用率较低,但是哈希表的性能可能较好,因为冲突的概率较低。当负载因子较大时,表示哈希表中的元素较多,空间利用率较高,但是哈希表的性能可能较差,因为冲突的概率较高。

通常情况下,负载因子的取值范围是 0 到 1,可以根据实际情况进行调整。一般来说,当负载因子超过某个阈值(如 0.75),就需要进行扩容操作,以保证哈希表的性能。扩容操作会重新计算哈希函数和重新分配存储空间,因此会引起一定的开销。

在实际应用中,选择合适的负载因子可以平衡哈希表的性能和空间利用率。较小的负载因子可以提高性能,但会浪费空间;较大的负载因子可以提高空间利用率,但会降低性能。因此,需要根据具体的应用场景和需求来选择合适的负载因子。


冲突解决

1.闭散列

也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以 把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢?

比如上面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,下标为4,因此44理论上应该插在该 位置,但是该位置已经放了值为4的元素,即发生哈希冲突。

1.1线性探测

从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他 元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标 记的伪删除法来删除一个元素。

1.2 二元探测

线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨 着往后逐个去找。

二元探测步骤:

  1. 假设哈希表的大小为 capacity,哈希函数将关键码值映射到位置 pos = hash(key) % capacity。
  2. 如果位置 pos 已经被占用,即发生了哈希冲突,那么继续探测下一个位置。
  3. 下一个位置的计算公式为 pos = (pos + i^2) % capacity,其中 i 是探测的次数。
  4. 如果下一个位置仍然被占用,继续增加 i 的值,继续探测下一个位置,直到找到一个空的位置
2.开散列

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


二 . 代码实现

案例: 使用哈希表管理员工

Emp

public class Emp {public int id;public String name;public Emp next;// 默认为空public Emp(int id,String name){super();this.id = id;this.name = name;}
}

 EmpLikedList

// 表示链表,存放数据
public class EmpLikedList {private Emp head;// 头指针,指向当前链表的第一个雇员// 添加雇员// 假定id自增长,直接尾增public void add(Emp emp){if(head == null){head = emp;return;}Emp cur = head;while(cur.next != null){cur = cur.next;}cur.next = emp;}// 遍历链表的雇员信息public void list(int count){if(head == null){System.out.println("第"+count+"条链表为空");return;}System.out.println("第"+count+"条链表的信息为");Emp cur = head;while(cur != null){if(cur.next == null){System.out.printf("(id = %d name = %s)\n",cur.id,cur.name);return;}System.out.printf("(id = %d name = %s)=>",cur.id,cur.name);cur = cur.next;}}// 通过id查找对应的雇员public Emp findEmp(int id){Emp cur = head;while(true){if(cur == null){System.out.println("雇员不存在");return null;}if(cur.id == id){return cur;}cur = cur.next;}}
}

 HashTable

// 创建 HashTable 管理多条链表
public class HashTable {// 盛放链表的数组,即哈希表EmpLikedList[] EmpLikedListArr;public int capacity;// 构造器,制定链表数量public HashTable(int capacity){this.capacity = capacity;EmpLikedListArr = new EmpLikedList[capacity];// 初始化一把,不然直接报空指针异常for (int i = 0; i < capacity; i++) {EmpLikedListArr[i] = new EmpLikedList();}}// 添加public void add(Emp emp){// 根据员工id确定员工应该在哪个链表EmpLikedListArr[HashFunction(emp.id)].add(emp);}// 遍历所有的链表public void list(){int count = 0;while (count < capacity) {EmpLikedListArr[count].list(count);count++;}}// 根据Id查找对应的雇员public void findEmp(int id){int count = HashFunction(id);Emp emp = EmpLikedListArr[count].findEmp(id);if(emp == null){System.out.println("没有找到该雇员");}else{System.out.println("找到了该雇员,在第"+count+"条链表中"+"id = "+id);}}// 散列函数 取模法public int HashFunction(int no){return no%capacity;}}

相关文章:

数据结构-哈希表

系列文章目录 1.集合-Collection-CSDN博客​​​​​​ 2.集合-List集合-CSDN博客 3.集合-ArrayList源码分析(面试)_喜欢吃animal milk的博客-CSDN博客 4.数据结构-哈希表_喜欢吃animal milk的博客-CSDN博客 文章目录 目录 系列文章目录 文章目录 前言 一 . 什么是哈希表&a…...

深度学习在图像识别领域还有哪些应用?

深度学习在图像识别领域的应用非常广泛&#xff0c;除了之前提到的图像分类、目标检测、语义分割和图像生成&#xff0c;还有其他一些应用。 图像超分辨率重建&#xff1a;深度学习技术可以用于提高图像的分辨率&#xff0c;例如通过使用生成对抗网络&#xff08;GAN&#xff…...

前端项目练习(练习-005-webpack-03)

学习前&#xff0c;首先&#xff0c;创建一个web-005项目&#xff0c;内容和web-004一样。&#xff08;注意将package.json中的name改为web-005&#xff09; 前面的代码中&#xff0c;打包工作已经基本完成了&#xff0c;下面开始在本地启动项目。这里需要用到webpack-dev-serv…...

『力扣每日一题10』:字符串中的单词数

因为身体原因&#xff0c;再加上学校的 DeadLine 比较多&#xff0c;太忙太累&#xff0c;拖更了半个月。现在开始重拾日更&#xff0c;期待我们一起遇见更好的自己&#xff01; 一、题目 统计字符串中的单词个数&#xff0c;这里的单词指的是连续的不是空格的字符。 请注意&a…...

初级篇—第三章多表查询

文章目录 为什么需要多表查询一个案例引发的多表连接初代查询笛卡尔积&#xff08;或交叉连接&#xff09;的理解 多表查询分类等值连接 vs 非等值连接自连接 vs 非自连接内连接VS外连接 SQL99语法实现多表查询内连接的实现外连接的实现左外连接右外连接满外连接 UNION的使用7种…...

<Xcode> Xcode IOS无开发者账号打包和分发

关于flutter我们前边聊到的初入门、数据解析、适配、安卓打包、ios端的开发和黑苹果环境部署&#xff0c;但是对于苹果的打包和分发&#xff0c;我只是给大家了一个链接&#xff0c;作为一个顶级好男人&#xff0c;我认为这样是对大家的不负责任&#xff0c;那么这篇就主要是针…...

vertx的学习总结2

一、什么是verticle verticle是vertx的基本单元&#xff0c;其作用就是封装用于处理事件的技术功能单元 &#xff08;如果不能理解&#xff0c;到后面的实战就可以理解了&#xff09; 二、写一个verticle 1. 引入依赖&#xff08;这里用的是gradle&#xff0c;不会吧&#…...

网络安全内网渗透之DNS隧道实验--dnscat2直连模式

目录 一、DNS隧道攻击原理 二、DNS隧道工具 &#xff08;一&#xff09;安装dnscat2服务端 &#xff08;二&#xff09;启动服务器端 &#xff08;三&#xff09;在目标机器上安装客户端 &#xff08;四&#xff09;反弹shell 一、DNS隧道攻击原理 在进行DNS查询时&#x…...

探索ClickHouse——连接Kafka和Clickhouse

安装Kafka 新增用户 sudo adduser kafka sudo adduser kafka sudo su -l kafka安装JDK sudo apt-get install openjdk-8-jre下载解压kafka 可以从https://downloads.apache.org/kafka/下找到希望安装的版本。需要注意的是&#xff0c;不要下载路径包含src的包&#xff0c;否…...

基于监督学习的多模态MRI脑肿瘤分割,使用来自超体素的纹理特征(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

【RocketMQ】(八)Rebalance负载均衡

消费者负载均衡&#xff0c;是指为消费组下的每个消费者分配订阅主题下的消费队列&#xff0c;分配了消费队列消费者就可以知道去消费哪个消费队列上面的消息&#xff0c;这里针对集群模式&#xff0c;因为广播模式&#xff0c;所有的消息队列可以被消费组下的每个消费者消费不…...

线性筛和埃氏筛

线性筛&#xff1a; #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<ut…...

【Java 进阶篇】JDBC ResultSet 类详解

在Java应用程序中&#xff0c;与数据库交互通常涉及执行SQL查询以检索数据。一旦执行查询&#xff0c;您将获得一个ResultSet对象&#xff0c;该对象包含查询结果的数据。本文将深入介绍ResultSet类&#xff0c;它是Java JDBC编程中的一个核心类&#xff0c;用于处理查询结果。…...

Centos7常用服务脚本(.service)

Centos7常用服务脚本&#xff08;.service&#xff09; 注意&#xff1a;[Service]中配置路径必须使用绝对路径。 启停&#xff1a; systemctl { start | stop | restart | reload } xxx.service 自启动&#xff1a; systemctl { enable | disable } xxx.service nginx.se…...

MySQL 视图View的SQL语法和更新(视图篇 二)

视图语法基本操作 创建 -- [ ]表示可选 create [or replace] view 视图名称[(列名列表)] as select语句 [ with [cascaded | local ] check option ]; 添加&#xff08;虽然视图是虚拟表&#xff0c;但是向视图操作的数据实际上会影响到实际关联的表数据&#xff09; -- 视图添…...

38 翻转二叉树

翻转二叉树 理解题意&#xff0c;翻转即每个结点的左右子树翻转/对调题解1 递归——自下而上题解2 迭代——自上而下 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 提示&#xff1a; 树中节点数目范围在 [0, 100] 内-100 < Node.…...

数据结构-快速排序-C语言实现

引言&#xff1a;快速排序作为一种非常经典且高效的排序算法&#xff0c;无论是工作还是面试中广泛用到&#xff0c;作为一种分治思想&#xff0c;需要熟悉递归思想。下面来讲讲快速排序的实现和改进。 老规矩&#xff0c;先用图解来理解一下&#xff1a;&#xff08;这里使用快…...

玩客云Armbian_23.08.0-trunk_Onecloud_bookworm_edge_6.4.14.burn配置

固定IP # interface file auto-generated by buildrootauto lo iface lo inet loopback// 上面是默认的内容,下面是新增的内容,上下之间需要一个空行隔开 // 接口顶格写,属性的前面有一个tab的缩进 # The primary network interfaceauto eth0 iface eth0 inet staticaddress 1…...

Nginx查找耗时的接口

Nginx查找耗时的接口 # grep 是筛选的域名 awk中的$5是判断的状态码 sort中的15是指的upstream_response_time 当然也可以统计request_time的时间cat access.log | grep zhhll.icu | awk $5 200{print $0} | sort -k 15 -n -r | head -10 https://zhhll.icu/2021/linux/实…...

C++ Primer 一 变量和基本类型

本章讲解C内置的数据类型&#xff08;如&#xff1a;字符、整型、浮点数等&#xff09;和自定义数据类型的机制。下一章讲解C标准库里面定义的更加复杂的数据类型&#xff0c;比如可变长字符串和向量等。 1.基本内置类型 C内置的基本类型包括&#xff1a;算术类型和空类型。算…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...