C++哈希(一)
1.底层结构
顺序结构以及平衡中,元素关键码与其存储位置之间没有相对应的关系,因此在查找一个元素时,要经过关键码的多次比较。顺序查找的时间复杂度为O(N)。
理想的搜索方法:可以不经过比较,依次直接从表中直接搜索到指定元素,如果构造一种数据结构,通过某种函数使元素的存储位置与它的关键码之间能够建立----映射关系,就可以很快的查找到指定的元素。
插入元素:根据插入元素的关键码,用函数计算出这个元素的存储位置并存放
查找元素:对元素的关键码进行计算,得到的函数值去取出此位置的存储元素,并把输入的元素与此元素进行比较,若关键码相等,则查找成功
该方式为哈希(散列)方法,哈希方法中的转换函数为哈希函数,构造出来的结构为哈希表
一般是用关键码膜上该结构的总容量,得到的值就为映射后的位置下标。
2.哈希冲突
对于俩个数据元素的关键码通过哈希函数后得到的值一样,不同关键字通过相同哈希函数计算出相同的哈希值地址,该现象称为哈希冲突或哈希碰撞。
3.哈希函数
引起哈希冲突的原因可能:哈希函数设计不够合理
哈希函数设计原则:
哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址,则值域必须在[0 m-1]之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数形式相对简单
除留余数法
设散列表中允许存储的地址数位m个,取一个不大于m的数p,且p最接近或者等于m的质数作为除数,Hush(key)=key%p(p<m) ,将关键码转换为哈希地址
补充:
key%2^16表示的是取后十六位,然后key>>(32-n)(假设n=16)是把前16位移到后16位,最后把前16位和后16位异或的结果作为哈希值(key的前16位和后16位都到同一位置也就是后16位上了),把key的每一位都参与到计算,这样得出的哈希值冲突会更少一些。
哈希冲突解决
闭散列:也叫开放地址法,当发生哈希冲突时,如果哈希表未被填满,说明哈希表中心必然还有空位置,那么可以把key存放到冲突位置的下一个位置去。
找到空位置
1.线性探测
如下图要插入元素44,先通过哈希函数计算出哈希地址,44%10=4,应在4的位置,但是这个位置已经放了数据了,所以要从发生冲突的位置开始依次向后找,直到寻找到空位置为止
2.删除
采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其它元素的搜索,比如删除4,那么查找44时根据计算的哈希地址就是4的位置,当44不在4位置在后面。所以通过枚举用标记的方式来删除元素。
enum State
{
EMPTY,
EXIST,
DELETE
};
3.哈希表扩容
散列表的载荷因子定义:a=填入表中的个数/散列表的长度
对于开放定址法, 载荷因子应该限制在0.7~0.8以下,
线性探测优点:实现简单
线性探测缺点:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据堆积,在查找时需要进行多次比较,导致搜索效率降低。
二次探测
线性探测的缺陷是产生冲突的数据堆积到一块,这与其找找的下一个位置有关,从发生冲突的位置向后找空位置可能会发生的问题,二次探测就是为了避免该现象的出现。
hash=hash0+i^2 or hash=hash0+i^2
代码实现
1.枚举定义状态
设置三个状态存在,空,删除
enum State
{EXIST,EMPTY,DELETE
};
2.定义存在哈希表里面的数据
pair模板,first表示键值,second表示值
template<class K,class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};
3.哈希表的构造
内联函数里面提供的数字就是质数,有28个,这里lower_bound是选一个大于等于n的数字,这里的n也就是哈希表的存储个数,返回处使用了三目操作符,如果不是最后一个就是pos,如果是最后一个就要返回最后一个的前一个。
HashTable():_tables(__stl_next_prime(0)),_n(0)
{}
inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}
4.哈希表的插入
首先要判断插入的元素是否已经存在,接着是判断载荷因子是否超过0.7,这里把_n*10所以和7比较,如果大于7就要扩容了,哈希表扩容则原来的存储位置在新的里面是不一样的,因为之前的存储是旧的size,扩容后是新的size,哈希函数得出的值改变了,所以存储位置要重新计算,这里newht的空间还是去之前的28个里面选,这里+1是因为28个数字对应不同区间,所以只需要加一就会到下一个区间,还要判断旧表每一个位置的状态是否是存在的,说明之前是由元素在这个位置上,则把此处的元素再作为Insert的参数重新插入,最后交换地址,如果没超过0.7,则就正常插入,通过模来得到哈希值,然后还要线性检测是否此位置为空位置,while循环后就找到了空位置,则插入并改变状态为存在,并把已经存储的个数n++。
bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;if (_n * 10 / _tables.size() >= 7){HashTable<K, V> newht;newht._tables.resize(__stl_next_prime(_tables.size() + 1));for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hash0 = kv.first % _tables.size();size_t hashi = hash0;size_t i = 1;int flag = 1;while (_tables[hashi]._state == EXIST){hashi = (hash0 + i) % _tables.size();++i;///二次探测////// hashi=(hash0+(i*i*flag))%_tables.size();/// ///}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}
5.哈希表的查找
这里查找需要注意的是位置被占了,可能在哈希函数得出的值的后面或者前面,先得到要查找的键的哈希值,然后用循环来寻找,先看是否为空,空说明不存在,如果不为空还要判断键值是否一样,不一样就线性检测去遍历,找到就返回此处的地址。
HashData<K, V>* Find(const K& key)
{size_t hash0 = key % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi = (hash0 + i) % _tables.size();++i;}return nullptr;
}
6.哈希表的删除
前面已经提到不能删除,只改变状态为删除状态就行,先用Find去找到指定位置,判断是否找到,找到就只改变状态变量。
bool Erase(const K& key)
{HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;return true;}else{return false;}
}
总代码
HashTable.h
#pragma once#include<vector>enum State
{EXIST,EMPTY,DELETE
};template<class K,class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K,class V>
class HashTable
{
public:HashTable():_tables(__stl_next_prime(0)),_n(0){}inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] = {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;if (_n * 10 / _tables.size() >= 7){HashTable<K, V> newht;newht._tables.resize(__stl_next_prime(_tables.size() + 1));for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hash0 = kv.first % _tables.size();size_t hashi = hash0;size_t i = 1;int flag = 1;while (_tables[hashi]._state == EXIST){hashi = (hash0 + i) % _tables.size();++i;///二次探测////// hashi=(hash0+(i*i*flag))%_tables.size();/// ///}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){size_t hash0 = key % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi = (hash0 + i) % _tables.size();++i;}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n;
};
test.c
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<set>
#include<unordered_set>using namespace std;
#include"HashTable.h"
int main()
{//int a[] = { 19,30,52,63,11,22 };int a[] = { 19,30,5,36,13,20,21,12 };HashTable<int, int> ht;for (auto e : a){ht.Insert({ e, e });}//ht.Insert({ 15, 15 });ht.Erase(30);if (ht.Find(20)){cout << "找到了" << endl;}if (ht.Find(30)){cout << "找到了" << endl;}else{cout << "没有找到" << endl;}return 0;
}
相关文章:

C++哈希(一)
1.底层结构 顺序结构以及平衡中,元素关键码与其存储位置之间没有相对应的关系,因此在查找一个元素时,要经过关键码的多次比较。顺序查找的时间复杂度为O(N)。 理想的搜索方法:可以不经过比较,依次直接从表中直接搜索…...

阿拉丁论文助手:一键点亮学术之路
在学术研究的海洋中,每一位学者都渴望拥有一盏能够照亮前行道路的神灯。阿拉丁论文助手,正是这样一盏神奇的灯,它以其先进的人工智能技术和丰富的学术资源,为学者们的学术写作提供了全方位的支持。 一、阿拉丁论文助手简介 阿拉丁…...

视频码率到底是什么?详细说明
视频码率(Video Bitrate)是指在单位时间内(通常是每秒)传输或处理的视频数据量,用比特(bit)表示。它通常用来衡量视频文件的压缩程度和质量,码率越高,视频质量越好&#…...

嵌入式学习(17)-stm32F407串口使用注意事项
一、概述 配置串口时串口的接收一直不好使,对比例程发现了问题: 在网上也找了一些资料供参考“STM32F4的串口RX引脚不能被设置为输入是因为串口的接收(RX)功能是由硬件电路实现的,无法通过软件配置来控制。串口接收功…...
汽车48V电气系统
汽车48V电气系统 汽车48V电气系统汽车48V电气系统设计汽车48V电气系统测试汽车48V系统是48V供电和12V供电共存的么?48V供电系统是如何与12V供电系统共存的?48V电气系统测试的难点有哪些?在汽车48V电气系统通信测试中,如何向12V的控制器和48V的控制器供电?汽车48V电气系统通…...

【人工智能基础05】决策树模型习题
文章目录 1. 归一化对决策树的影响2. 选择决策树模型3. 决策树计算4. 基尼系数的优势5. 在叶子上使用线性模型的优缺点 1. 归一化对决策树的影响 题目:对于一些机器学习模型(例如,神经网络),对特征进行归一化(normaliz…...

rockit 学习、开发笔记(六)(VENC)
前言 上节我们讲到了VDEC解码模块,那当然少不了VENC编码模块了,一般有编解码的需求都是为了压缩视频的大小,方便减少传输所占用的带宽。 概述 VENC 模块,即视频编码模块。本模块支持多路实时编码,且每路编码独立&am…...
spring技术点
引入对象 Autowired 和 Resource的区别 Autowired 和 Resource的区别 valid 参数校验 jarkata进行SpringMVC校验 常规当前进行校验的配置操作,参考文档如下进行操作。 SpringMVC校验注解不生效 List类型参数校验 由于list类型默认不能进行标注校验实现&#x…...
R语言使用“纽约市数据集中的优步皮卡”数据创建不同年度时间范围的可视化
一、项目背景 为了分析纽约市优步(https://baike.baidu.com/item/Uber/14900884)皮卡在不同年度的使用情况,需要利用R语言进行数据可视化。通过对比不同年度的数据,可以揭示出优步皮卡使用的趋势和变化。 二、数据准备 数据集&a…...

电阻计RM3544、RM3545的使用
目录: 一、电阻计与PC通讯 1、硬件连接 2、RmLogger.exe的使用 二、RM3545测量35uΩ电阻 一、电阻计与PC通讯 1、硬件连接 可以设置USB或COM口(串口)连接PC,也可以设置为“打印”输出。 1)使用USB连接PC 2)使用串口连接PC …...
Unity 策略游戏地图上的网格是如何实现的
在Unity中实现策略游戏地图上的网格,主要涉及到地图数据的处理、地图的加载与渲染、以及玩家在地图上的移动与碰撞检测等关键步骤。以下是对这些步骤的详细解释: 一、地图数据的处理 收集地图数据:这包括地形高度、地形纹理、建筑物、树木等…...
《鸟哥的Linux私房菜基础篇》---4 Linux档案的压缩与打包
目录 一、常见的压缩包的扩展名 二、常见的压缩和解压指令 1、tar 2、tar gzip(.tar.gz) (或 .tgz) 3、tar bzip2(.tar.bz2) 4、zip 5、gzip 6、bzip2 7、xz 8、rar 9、7z 三、安装解压工具 一、常见的压缩包的扩展…...

Springboot 2.7+解决跨域问题,到底是在SpringBoot中添加拦截器还是修改Nginx配置
文章目录 1摘要2 核心代码2.1 SpringBoot 全局跨域拦截器2.2 Nginx 配置跨域处理2.3 Nginx 和 SpringBoot 同时添加允许跨域处理会怎么样? 3 推荐参考资料 1摘要 跨域问题报错信息: Referrer Policy:strict-origin-when-cross-origin跨域问题是在前后端分离的情况…...
Spring中Bean的作用域深入剖析与技术实践
前言 Spring框架作为Java企业级应用开发中的中流砥柱,提供了强大的依赖注入(DI)和面向切面编程(AOP)等功能。在Spring框架中,Bean的作用域(Scope)是一个非常重要的概念,…...
Python爬虫实战:抓取拼多多商品详情数据(基于pdd.item_get接口)
在当前的电商市场中,拼多多以其独特的拼团模式和优惠价格吸引了大量用户,成为继淘宝、京东之后的又一大电商平台。对于数据分析和市场研究者来说,获取拼多多的商品详情数据显得尤为重要。本文将介绍如何使用Python爬虫技术,通过调…...
工具类-列表请求工具 useList
useList 用于列表请求的基于 vue 3 的 hooks,接收请求函数、请求参数等数据,自动生成请求请求函数,分页信息等 本文有涉及到 http 请求工具和接口返回格式的内容: http 工具:一个基于 axios 封装的请求工具Response…...
Scala中的正则表达式01
规则类型具体规则示例说明单字符大多数字符匹配自身正则表达式 abc,文本 abca 匹配 a,b 匹配 b,c 匹配 c方括号 [ ][ ] 定义字符集,匹配其一[abc],文本 a、b 或 c[abc] 匹配 a、b 或者 c排除字符集 [^ ][^ ] 开头加 ^&…...

基于SpringBoot的养老院管理系统的设计与实现
一、前言 随着人口老龄化的加剧,养老院作为老年人养老的重要场所,其管理的高效性和科学性显得尤为重要。传统的养老院管理方式多依赖人工操作,存在信息记录不及时、不准确,管理流程繁琐,资源调配困难等问题。利用信息技…...
Ansible变量详解(变量定义+变量优先级+变量注册+层级定义变量+facts缓存变量)
本篇文章详细给大家介绍Ansible变量,变量适合管理剧本中每个项目的动态值,或是某些值在多个地方重复使用,如果将此值设置为变量再在其他地方调用会方便许多。会用变量,才算真正会用Ansible,话不多说,直接开…...
面向对象系统的分析和设计
来源:《设计模式精解-GOF23种设计模式解析》 作者:k_eckel k_eckels mindview - 博客园 (cnblogs.com) --------- 面向对象系统的分析和设计实际上追求的就是两点: (1)高内聚 (2)低耦合 …...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...

PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...