【算法】- 查找 - 散列表查询(哈希表)
文章目录
- 前言
- 一、哈希表的思想
- 二、哈希表
- 总结
前言
散列技术:在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)
哈希表:采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表
一、哈希表的思想
创建哈希表结构体:创建哈希表数据结构HashTable,用来存放散列地址和该散列表存放的数据个数。
//创建哈希表结构
typedef struct HashTable
{int count;//记录哈希表中元素个数int* elem;//创建哈希表
}HashTable;
初始化哈希表:初始化哈希表主要还是动态开辟存放数据的数组,再初始化count的个数,并将哈希表中的值赋值为空,这里用NULLKEY标志来表示为空。
//初始化哈希表
void InitHashTable(HashTable* HT)
{int i;m = MAXSIZE;//动态开辟内存HT->elem = (int*)malloc(m * sizeof(int));HT->count = MAXSIZE;for (i = 0; i < m; i++){HT->elem[i] = NULLKEY;}}
插入哈希表:插入哈希表,通过哈希函数Hash来计算出散列地址,判断该地址是否为NULLKEY,是的话就直接插入,不是的话就将散列地址赋值为下一个地址,继续判断,直到找到了就执行插入操作。
//哈希表的插入
void InsertHashTable(HashTable* HT, int key)
{int addr;addr = Hash(key);//求散列地址while (HT->elem[addr] != NULLKEY){addr = (addr + 1) % m;}HT->elem[addr] = key;
}
查询哈希表:先通过哈希函数获得散列地址,再通过散列地址查询访问。在查询时如果通过散列地址找到的值和key值不等,则散列地址找到下一个操作,直到循环一圈或则通过地址找到的地址为NULLKEY就返回查找失败,成功则返回查找成功。
//哈希表查找
int SearchHash(HashTable HT, int key)
{int addr = Hash(key);int begin = addr;while (HT.elem[addr] != key){addr = (addr + 1) % m;if (HT.elem[addr] == NULLKEY || addr == begin)return 0;}return 1;
}
二、哈希表
#define MAXSIZE 12
#define NULLKEY -32768
#include <iostream>
using namespace std;//哈希表查找//创建哈希表结构
typedef struct HashTable
{int count;//记录哈希表中元素个数int* elem;//创建哈希表
}HashTable;int m = 0;//初始化哈希表
void InitHashTable(HashTable* HT)
{int i;m = MAXSIZE;//动态开辟内存HT->elem = (int*)malloc(m * sizeof(int));HT->count = MAXSIZE;for (i = 0; i < m; i++){HT->elem[i] = NULLKEY;}}//散列函数
int Hash(int key)
{return key % m;
}//哈希表的插入
void InsertHashTable(HashTable* HT, int key)
{int addr;addr = Hash(key);//求散列地址while (HT->elem[addr] != NULLKEY){addr = (addr + 1) % m;}HT->elem[addr] = key;
}//哈希表查找
int SearchHash(HashTable HT, int key)
{int addr = Hash(key);int begin = addr;while (HT.elem[addr] != key){addr = (addr + 1) % m;if (HT.elem[addr] == NULLKEY || addr == begin)return 0;}return 1;
}int main()
{int i,result,key;HashTable HT;int arr[MAXSIZE] = { 12,67,56,16,25,37,22,29,15,47,48,34 };//初始化哈希表InitHashTable(&HT);key = 39;for (i = 0; i < m; i++){InsertHashTable(&HT, arr[i]);}result = SearchHash(HT,key);if (result)printf("查找 %d 成功 \n", key);elseprintf("查找 %d 失败。\n", key);for (i = 0; i < m; i++){key = arr[i];result = SearchHash(HT, key);if (result)printf("查找 %d 成功 \n", key);elseprintf("查找 %d 失败。\n", key);}return 0;
}
总结
散列表查找的效率是最高的,因为它的时间复杂度为O(1)。可惜在实际情况中,会产生冲突(不同的数据在同一地址的情况),但散列表查询还是非常值得的。
相关文章:
【算法】- 查找 - 散列表查询(哈希表)
文章目录 前言一、哈希表的思想二、哈希表总结 前言 散列技术:在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key) 哈希表:采用散列技术将记录存储在一块连续的存储空间中,这块连…...
货币政策工具
本文为个人学习笔记,内容源于教材;整理记录的同时也作为一种分享。 1. 简介 货币政策工具作为央行实现货币政策目标的经济手段,以期达到最终目标,即物价稳定,充分就业,经济增长,国际收支平衡。…...
std::async概念和使用方法
std::async是 C 标准库中的一个函数模板,用于启动一个异步任务,并返回一个std::future对象,该对象可用于获取异步任务的结果。 1、概念 std::async允许你以异步的方式执行一个函数或者可调用对象,它会在后台启动一个新的线程或者…...
Chatgpt 原理解构
一、背景知识 1. 自然语言处理的发展历程 自然语言处理在不同时期呈现出不同的特点和发展态势。萌芽期,艾伦・图灵在 1936 年提出 “图灵机” 概念,为计算机诞生奠定基础,1950 年他提出著名的 “图灵测试”,预见了计算机处理自然…...
【每日刷题】Day135
【每日刷题】Day135 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. LCR 011. 连续数组 - 力扣(LeetCode) 2. 【模板】二维前缀和_牛客题霸_牛客…...
Linux运维01:VMware创建虚拟机
视频链接:05.新建VM虚拟机_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1nW411L7xm/?p14&spm_id_from333.880.my_history.page.click&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5 1.点击“创建虚拟机” 2.选择“自定义(高级࿰…...
服务器平均响应时间和数据包大小关系大吗?
服务器的平均响应时间与数据包大小有一定的关系,但这只是影响响应时间的众多因素之一。具体来说,数据包大小对服务器响应时间的影响可以从以下几个方面来理解: 1. 数据传输时间 影响: 较大的数据包需要更多的时间在网络上传输,因此…...
Vue入门-指令学习-v-show和v-if
v-show: 作用:控制元素的显示隐藏 语法:v-show"表达式" 表达式值true显示,false隐藏 v-if 作用:控制元素的显示隐藏(条件渲染) 语法: vif"表达式" 表达式tr…...
nacos多数据源插件介绍以及使用
概述 在微服务架构中,服务配置的集中管理和动态调整是至关重要的。Nacos 提供了配置管理和服务发现的功能,其中配置管理支持动态数据源的切换,增强了其在复杂环境中的适用性。默认情况下,Nacos 支持 MySQL 和Derby,但…...
国庆档不太热,影视股“凉”了?
今年国庆档票房止步21亿元,属实有点差强人意。 根据国家电影局统计,2024年国庆档(2024年10月1日至7日)全国电影票房为21.04亿元,观影人次为5209万,总票房成绩、观影总人次同比均有所下滑。 作为传统观影高…...
QtDesign预览的效果与程序运行的结果不一致的解决方法
存在的问题 使用Qt designer软件设计出来的界面,与转换成python程序运行出来的结果不一致,具体看下图 Qt designer预览结果 程序运行出来的结果 原因分析 我自己的电脑是2560*1600分辨率的屏幕,采用的是200%的缩放比例,出现这种…...
模运算和快速幂
文章目录 模运算快速幂 模运算 模运算是大数运算中的常用操作。如果一个数太大,无法直接输出,或者不需要直接输出,则可以对它取模,缩小数值再输出。取模可以防止溢出,这是常见的操作。 取模运算一般要求a和m的符号一…...
【机器学习】——神经网络与深度学习:从基础到应用
文章目录 神经网络基础什么是神经网络?神经网络的基本结构激活函数 深度学习概述什么是深度学习?常见的深度学习算法 深度学习的工作流程深度学习的实际应用结论 引言 近年来,神经网络和深度学习逐渐成为人工智能的核心驱动力。这类模型模仿人…...
Unity各个操作功能+基本游戏物体创建与编辑+Unity场景概念及文件导入导出
各个操作功能 部分功能 几种操作游戏物体的方式: Center:有游戏物体父子关系的时候,中心点位置 Global/Local:世界坐标系方向/自身坐标系方向 :调试/暂停/下一帧 快捷键 1.Alt鼠标左键:可以实现巡游角度查看场景 2.鼠标滚轮…...
QT入门教程攻略 QT入门游戏设计:贪吃蛇实现 QT全攻略心得总结
Qt游戏设计:贪吃蛇 游戏简介 贪吃蛇是一款经典的休闲益智类游戏,玩家通过控制蛇的移动来吃掉地图上的食物,使蛇的身体变长。随着游戏的进行,蛇的移动速度会逐渐加快,难度也随之增加。当蛇撞到墙壁或自己的身体时&…...
Linux No space left on device分析和解决
报错解释: "No space left on device" 错误表示你的Linux设备(通常是磁盘分区)上没有剩余空间了。这可能是因为磁盘已满,或者inode已满。磁盘空间是指磁盘上的实际空间,而inode是用来存储文件元数据的数据结…...
Qt实现Halcon窗口显示当前图片坐标
一、前言 Halcon加载图片的窗口,不仅能放大和缩小图片,还可以按住Ctrl键显示鼠标下的灰度值,这种方式很方便我们分析缺陷的灰度和对比度。 二、实现方式 ① 创建显示坐标和灰度的widget窗口 下图的是widget部件,使用了4个label控…...
构建宠物咖啡馆:SpringBoot框架的实现策略
1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及,互联网成为人们查找信息的重要场所,二十一世纪是信息的时代,所以信息的管理显得特别重要。因此,使用计算机来管理基于Spring Boot的宠物咖啡馆平台的设计与…...
Qt开发环境的搭建
个人主页:C忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C忠实粉丝 原创 Qt开发环境的搭建 收录于专栏【Qt开发】 本专栏旨在分享学习Qt的一点学习笔记,欢迎大家在评论区交流讨论💌 目录 1. Qt开发工具概述 Qt…...
docker-compose查看容器日志和实时查看日志
要查看 docker-compose up 过程中容器启动的错误日志,可以使用以下方法: ### 1. **使用 docker-compose logs 命令** 1. 在终端中进入包含 docker-compose.yml 文件的目录。 2. 运行以下命令来查看所有容器的日志: bash docker-compose…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
