【C++、数据结构】哈希表——散列表(一)(概念/总结)

「前言」

🌈个人主页: 代码探秘者
🌈C语言专栏:C语言
🌈C++专栏: C++ / STL使用以及模拟实现
🌈数据结构专栏: 数据结构 / 十大排序算法
🌈Linux专栏: Linux系统编程 / Linux网络编程(准备更新)
🌈喜欢的诗句:天行健,君子以自强不息.

pic_8da49713.png

🥙1.散列表的基本概念

在这里插入图片描述

  • 散列表(哈希表,Hash Table):是⼀种数据结构。特点是:可以根据数据元素的关键字计算出它在散列表中的存储地址
  • 散列函数(哈希函数)Addr=H(key) 建⽴了“关键字”→“存储地址”的映射关系。

例:某散列表的⻓度为13,散列函数 H(key)=key%13。依次将数据元素 19、14、23 插⼊散列表:
在这里插入图片描述
19%13=6
14%13=1
23%13=10

理想情况下,在散列表中查找⼀个元素的时间复杂度为O1

  • 冲突:在散列表中插⼊⼀个数据元素时,需要根据关键字的值确定其存储地址,若该地址已经存储了其他元素,则称这种情况为“冲突(碰撞)
  • 同义词:若不同的关键字通过散列函数映射到同⼀个存储地址,则称它们为“同义词”
    *在这里插入图片描述
    关于冲突:
  • 减少冲突构造更适合的散列函数,让各个关键字尽可能地映射到不同的存储位置,从⽽减少“冲突”
  • 处理冲突拉链法、开放定址法(包含四种探测方法)

🥙2.散列函数的构造

1.散列函数定义

在这里插入图片描述

  • 散列函数(哈希函数)Addr=H(key) 建⽴了“关键字”→“存储地址”的映射关系。

2.设计散列函数注意点

设计散列函数时应该注意什么
在这里插入图片描述
在这里插入图片描述

3.常见的散列函数

1.除留余数法

  • 除留余数法 —— H(key) = key % p

  • 在这里插入图片描述

  • 散列表表⻓为m,取⼀个不⼤于m但最接近或等于m的质数p
    比如:m=15,15 不是素数,我找一个比它小的素数,13 或11
    在这里插入图片描述

p选质数的原因:

  • 原因:对质数取余,可以分布更均匀,从⽽减少冲突
    在这里插入图片描述

2.直接定址法

  • 直接定址法 —— H(key) = key 或 H(key) = a*key + b

在这里插入图片描述

  • 其中,a和b是常数。这种⽅法计算最简单,且不会产⽣冲突。若关键字分布不连续,空位较多,则会造成存储空间的浪费

在这里插入图片描述

3.数字分析法

  • 数字分析法 —— 选取数码分布较为均匀的若⼲位作为散列地址
  • 在这里插入图片描述

在这里插入图片描述

4.平⽅取中法

  • 平⽅取中法——取关键字的平⽅值的中间⼏位作为散列地址
  • 在这里插入图片描述
    在这里插入图片描述

4.总结

在这里插入图片描述

🥙3.处理冲突的方法

一.处理冲突-拉链法

在这里插入图片描述

  • 拉链法(⼜称链接法、链地址法):把所有同义词”存储在⼀个链表中。

在这里插入图片描述

1.插入操作

例:若散列表⻓度为13,散列函数 H(key)=key%13,⽤拉链法解决冲突。依次插⼊关键字 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}
在这里插入图片描述
如何在散列表(拉链法解决冲突)中插⼊⼀个新元素?

  • Step 1:结合散列函数计算新元素的散列地址
  • Step 2:将新元素插⼊散列地址对应的链表(可⽤头插法,也可⽤尾插法

在这里插入图片描述

2.插入操作的优化

  • 新元素插⼊链表时,若能保持链表有序,可以略微提⾼“查找”效率。
    在这里插入图片描述

3.查找元素

查找⻓度——在查找运算中,需要对⽐关键字的次数称为查找⻓度

  • 查找成功
    在这里插入图片描述
  • 查找失败
    在这里插入图片描述
    默认只统计关键字对比次数(空指针次数-部分才要求)
    在这里插入图片描述
    在这里插入图片描述

4.删除操作

  • 删除成功
    在这里插入图片描述
    在这里插入图片描述
  • 删除失败
    在这里插入图片描述

5.总结

在这里插入图片描述

二.处理冲突-开放定址法

在这里插入图片描述

  • 开放定址法:如果发⽣“冲突”,就给新元素找另⼀个空闲位置
  • 为什么叫“开放定址”?—— ⼀个散列地址,既对同义词开放,也对⾮同义词开放

在这里插入图片描述
探测方法:⽤什么规则确定“另⼀个空闲位置”

  • di 表示第 i 次发⽣冲突时,下⼀个探测地址与初始散列地址的相对偏移量。
    在这里插入图片描述

在这里插入图片描述

1.线性探测法

  • 插入操作
    在这里插入图片描述
    在这里插入图片描述

在这里插入图片描述

2.平⽅探测法(⼆次探测法)

在这里插入图片描述

3.双散列法

例:⻓度为13的散列表状态如下图所示,散列函数 H(key)=key%13,采⽤双散列法解决冲突,假设hash2(key)=13-(key %13)
分析:插⼊元素1、查找元素1 的过程。

在这里插入图片描述

  • 两个散列函数,第一个不行,开始使用第二个,计算di
    在这里插入图片描述

4.伪随机序列法

在这里插入图片描述
在这里插入图片描述

4.查找操作(统一)

查找操作原理类似,根据探测序列依次对⽐各存储单元内的关键字。

  • 若探测到⽬标关键字,则查找成功
  • 若探测到空单元,则查找失败

5.删除操作

如何删除⼀个元素:

  • Step 1:先根据散列函数算出散列地址,并对⽐关键字是否匹配。若匹配,则“查找成功”
  • Step 2:若关键字不匹配,则根据“探测序列”对⽐下⼀个地址的关键字,直到“查找成功”或“查找失败”
  • Step 3:若“查找成功”,则删除找到的元素

注:题⽬⼀定会说明具体是采⽤哪种探测序列(线性探测法、平⽅探测法、双散列法、伪随机序列法)

错误示范(注意-线性探测演示)

  • 先找15,删15
    在这里插入图片描述
  • 再要删1(开始探测了,会发现,找到原来放15的地方遇到空,这样就停止探测了)
    在这里插入图片描述

正确示范(逻辑删除)

  • 删15
    在这里插入图片描述
  • 找1
    在这里插入图片描述

注意

采⽤“开放定址法”(线性探测法、平⽅探测法、双散列法、伪随机序列法原)时,删除元素不能简单地将被删元素的空间置为空,否则将截断在它之后的探测路径,可以做⼀个“已删除”标记,进⾏逻辑删除

  • 逻辑删除定义一个flag=1, 删除则变0。(避免查找操作探测时,本来存在的数,没查到就停止探测了)。

在这里插入图片描述

6.总结

在这里插入图片描述

三.扩展:关于四种方法的探测覆盖率

线性探测法:采⽤线性探测法,⼀定可以探测到散列表的每个位置

  • 只要散列表中有空闲位置,就⼀定可以插⼊成功
  • 理想情况下,若散列表表⻓=m,则最多发⽣ m-1 次冲突即可“探测”完整个散列表

平⽅探测法:采⽤平⽅探测法,⾄少可以探测到散列表中⼀半的位置
在这里插入图片描述

  • 即便散列表中有空闲位置,也未必能插⼊成功
  • 若散列表⻓度 m 是⼀个可以表示成4j + 3的素数(如 7、11、19),平⽅探测法就能探测到所有位置

双散列法未必能探测到散列表的所有位置

  • 双散列法的探测覆盖率取决于第⼆个散列函数hash2(key) 设计的是否合理

  • hash2(key) 计算得到的值与散列表表⻓m互质,就能保证双散列发可以探测所有单元
    在这里插入图片描述

伪随机序列法:di 是⼀个伪随机序列,由程序员⼈为设计

  • 采⽤伪随机序列法,是否能探测到散列表中全部位置,取决于伪随机序列的设计是否合理

总结

在这里插入图片描述

🥙4.模拟实现哈希表

点击这里!

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

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

相关文章

WindowsDocker安装到D盘,C盘太占用空间了。

Windows安装 Docker Desktop的时候,默认位置是安装在C盘,使用Docker下载的镜像文件也是保存在C盘,如果对Docker使用评率比较高的小伙伴,可能C盘空间,会被耗尽,有没有一种办法可以将Docker安装到其它磁盘,同时Docker的数据文件也保存在其他磁盘呢? 答案是有的,我们可以…

mac|安装redis及RedisDesk可视化软件

一、安装 通过Homebrew安装 brew install redis 在安装过程可以得到以下信息: 1、启动redis或重新登陆redis brew services start redis 如果只想在前端运行,而不是在后端,则使用以下命令 /opt/homebrew/opt/redis/bin/redis-server /opt…

程序中怎样用最简单方法实现写excel文档

很多开发语言都能找到excel文档读写的库,但是在资源极其受限的环境下开发,引入这些库会带来兼容性问题。因为一个小功能引入一堆库,我始终觉得划不来。看到有项目引用的jar包有一百多个,看着头麻,根本搞不清谁依赖谁。…

重读《人月神话》(12)-未雨绸缪(Plan to Throw One Away)

对程序员而言,一个不容忽视的事实是:任何系统都将经历变更,最初精心设计的软件也可能因不断的修补而变得面目全非。无论设计多么完美,随着时间推移,系统难免陷入混乱,只是程度和速度有所不同。因此&#xf…

(附项目源码)python开发语言,基于python Web的高校毕业论文管理系统 51,计算机毕设程序开发+文案(LW+PPT)

摘 要 随着信息化技术的迅速发展,人类信息化文明的到来,为人类的日常生活以及日常生产活动提供了非常大的便利,有效地解决了很多曾经无法解决的问题。本次基于python Web的高校毕业论文管理系统的开发是针对我国传统的高校毕业论文管理模式沟…

计算机网络:网络层 —— 网络地址转换 NAT

文章目录 网络地址转换 NAT 概述最基本的 NAT 方法NAT 转换表的作用 网络地址与端口号转换 NAPTNAT 和 NAPT 的缺陷 网络地址转换 NAT 概述 尽管因特网采用了无分类编址方法来减缓 IPv4 地址空间耗尽的速度,但由于因特网用户数量的急剧增长,特别是大量小…

C++进阶:unordered_map和unordered_set的使用

目录 一.unordered_set系列 1.1unordered_set类的介绍 1.2unordered_set与set的差异 二.unordered_map的系列 三.unordered_multimap/unordered_multiset 一.unordered_set系列 1.1unordered_set类的介绍 • unordered_set的声明如下,Key就是unordered_set底层…

【6G 需求与定义】ITU(国际电联)对全球6G标准的愿景

博主未授权任何人或组织机构转载博主任何原创文章,感谢各位对原创的支持! 博主链接 本人就职于国际知名终端厂商,负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作,目前牵头6G技术研究。 博客内容主要围绕…

java:题目:用Java实现简单的自取取款操作

import java.util.Scanner; public class ATM {public static void main(String[] args){//自主取款主类Scanner scnew Scanner(System.in);System.out.println("请输入账户号码:");String BankAccoutsrsc.nextLine();/BankAccout3 newBankAccoutnew Bank…

Windows 部署非安装版Redis

1.下载Redis https://github.com/microsoftarchive/redis/releases 选择下载zip包,如Redis-x64-3.0.504.zip,并解压 2.启动非安装版redis服务 进入到redis目录,打开cmd 执行命令 redis-server.exe redis.windows.conf 3.登录redis客户端…

【连续多届检索,ACM出版】第四届大数据、人工智能与风险管理国际学术会议 (ICBAR 2024,11月15-17)--冬季主会场

第四届大数据、人工智能与风险管理国际学术会议 (ICBAR 2024)--冬季主会场 2024 4th International Conference on Big Data, Artificial Intelligence and Risk Management 会议官网:www.icbar.net 2024 4th International Conference on Big Data, Artificial I…

HTML 基础概念:什么是 HTML ? HTML 的构成 与 HTML 基本文档结构

文章目录 什么是 HTML ?HTML 的构成 ?什么是 HTML 元素?HTML 元素的组成部分HTML 元素的特点 HTML 基本文档结构如何打开新建的 HTML 文件代码查看 什么是 HTML ? HTML(超文本标记语言,HyperText Markup L…

网络编程 TCP编程 Linux环境 C语言实现

所有基于数据传输通信的程序,都会被分成两种角色: 1. 服务端:又称为服务器 server 提供一种通信服务的进程 基本工作过程是:1> 接收请求数据 2> 处理请求数据 3> 发送处理结果 2. 客户端:client 使用一种通…

第二十九章 Vue之插槽

目录 一、引言 二、默认插槽 2.1. 默认插槽基本语法 2.2. 完整代码 2.2.1. main.js 2.2.2. App.vue 2.2.3. MyDialog.vue 2.3. 运行效果 三、插槽后备内容(默认值) 3.1. 插槽后备内容基本语法 3.2. 完整代码 3.2.1. main.js 3.2.2. App.vu…

宠物领养救助管理软件有哪些功能 佳易王宠物领养救助管理系统使用操作教程

一、概述 佳易王宠物领养救助管理系统V16.0,集宠物信息登记、查询,宠物领养登记、查询, 宠物领养预约管理、货品进出库库存管理于一体的综合管理系统软件。 概述: 佳易王宠物领养救助管理系统V16.0,集宠物信息登记…

【ESP32+MicroPython】开发环境部署

本教程将指导你如何在Visual Studio Code(VSCode)中设置ESP32的MicroPython开发环境。我们将涵盖从安装Python到烧录MicroPython固件的整个过程,以及如何配置VSCode以便与ESP32进行交互。 准备工作 安装Python 确保你的计算机上安装了Pyth…

前端Nginx的安装与应用

目录 一、前端跨域方式 1.1、CORS(跨域资源共享) 1.2、JSONP(已过时) 1.3、WebSocket 1.4、PostMessage 1.5、Nginx 二、安装 三、应用 四、命令 4.1、基本操作命令 4.2、nginx.conf介绍 4.2.1、location模块 4.2.2、反向代理配置 4.2.3、负载均衡模块 4.2.4、通…

mysql之命令行基础指令

一:安装好mysql后,注册好账号密码。 二:在命令行进行登录的指令如下 mysql -u用户名 -p 例如:mysql -uroot -p; 然后按下回车,进入输入密码。 三:基本指令: 1:查看当前账户的所有…

小白直接冲!BiTCN-BiLSTM-Attention双向时间卷积双向长短期记忆神经网络融合注意力机制多变量回归预测

小白直接冲!BiTCN-BiLSTM-Attention双向时间卷积双向长短期记忆神经网络融合注意力机制多变量回归预测 目录 小白直接冲!BiTCN-BiLSTM-Attention双向时间卷积双向长短期记忆神经网络融合注意力机制多变量回归预测效果一览基本介绍程序设计参考资料 效果一…