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

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.底层结构 顺序结构以及平衡中&#xff0c;元素关键码与其存储位置之间没有相对应的关系&#xff0c;因此在查找一个元素时&#xff0c;要经过关键码的多次比较。顺序查找的时间复杂度为O(N)。 理想的搜索方法&#xff1a;可以不经过比较&#xff0c;依次直接从表中直接搜索…...

阿拉丁论文助手:一键点亮学术之路

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

视频码率到底是什么?详细说明

视频码率&#xff08;Video Bitrate&#xff09;是指在单位时间内&#xff08;通常是每秒&#xff09;传输或处理的视频数据量&#xff0c;用比特&#xff08;bit&#xff09;表示。它通常用来衡量视频文件的压缩程度和质量&#xff0c;码率越高&#xff0c;视频质量越好&#…...

嵌入式学习(17)-stm32F407串口使用注意事项

一、概述 配置串口时串口的接收一直不好使&#xff0c;对比例程发现了问题&#xff1a; 在网上也找了一些资料供参考“STM32F4的串口RX引脚不能被设置为输入是因为串口的接收&#xff08;RX&#xff09;功能是由硬件电路实现的&#xff0c;无法通过软件配置来控制。串口接收功…...

汽车48V电气系统

汽车48V电气系统 汽车48V电气系统汽车48V电气系统设计汽车48V电气系统测试汽车48V系统是48V供电和12V供电共存的么?48V供电系统是如何与12V供电系统共存的?48V电气系统测试的难点有哪些?在汽车48V电气系统通信测试中,如何向12V的控制器和48V的控制器供电?汽车48V电气系统通…...

【人工智能基础05】决策树模型习题

文章目录 1. 归一化对决策树的影响2. 选择决策树模型3. 决策树计算4. 基尼系数的优势5. 在叶子上使用线性模型的优缺点 1. 归一化对决策树的影响 题目&#xff1a;对于一些机器学习模型&#xff08;例如&#xff0c;神经网络&#xff09;&#xff0c;对特征进行归一化(normaliz…...

rockit 学习、开发笔记(六)(VENC)

前言 上节我们讲到了VDEC解码模块&#xff0c;那当然少不了VENC编码模块了&#xff0c;一般有编解码的需求都是为了压缩视频的大小&#xff0c;方便减少传输所占用的带宽。 概述 VENC 模块&#xff0c;即视频编码模块。本模块支持多路实时编码&#xff0c;且每路编码独立&am…...

spring技术点

引入对象 Autowired 和 Resource的区别 Autowired 和 Resource的区别 valid 参数校验 jarkata进行SpringMVC校验 常规当前进行校验的配置操作&#xff0c;参考文档如下进行操作。 SpringMVC校验注解不生效 List类型参数校验 由于list类型默认不能进行标注校验实现&#x…...

R语言使用“纽约市数据集中的优步皮卡”数据创建不同年度时间范围的可视化

一、项目背景 为了分析纽约市优步&#xff08;https://baike.baidu.com/item/Uber/14900884&#xff09;皮卡在不同年度的使用情况&#xff0c;需要利用R语言进行数据可视化。通过对比不同年度的数据&#xff0c;可以揭示出优步皮卡使用的趋势和变化。 二、数据准备 数据集&a…...

电阻计RM3544、RM3545的使用

目录&#xff1a; 一、电阻计与PC通讯 1、硬件连接 2、RmLogger.exe的使用 二、RM3545测量35uΩ电阻 一、电阻计与PC通讯 1、硬件连接 可以设置USB或COM口(串口)连接PC&#xff0c;也可以设置为“打印”输出。 1&#xff09;使用USB连接PC 2&#xff09;使用串口连接PC …...

Unity 策略游戏地图上的网格是如何实现的

在Unity中实现策略游戏地图上的网格&#xff0c;主要涉及到地图数据的处理、地图的加载与渲染、以及玩家在地图上的移动与碰撞检测等关键步骤。以下是对这些步骤的详细解释&#xff1a; 一、地图数据的处理 收集地图数据&#xff1a;这包括地形高度、地形纹理、建筑物、树木等…...

《鸟哥的Linux私房菜基础篇》---4 Linux档案的压缩与打包

目录 一、常见的压缩包的扩展名 二、常见的压缩和解压指令 1、tar 2、tar gzip&#xff08;.tar.gz&#xff09; (或 .tgz) 3、tar bzip2&#xff08;.tar.bz2&#xff09; 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 同时添加允许跨域处理会怎么样&#xff1f; 3 推荐参考资料 1摘要 跨域问题报错信息: Referrer Policy:strict-origin-when-cross-origin跨域问题是在前后端分离的情况…...

Spring中Bean的作用域深入剖析与技术实践

前言 Spring框架作为Java企业级应用开发中的中流砥柱&#xff0c;提供了强大的依赖注入&#xff08;DI&#xff09;和面向切面编程&#xff08;AOP&#xff09;等功能。在Spring框架中&#xff0c;Bean的作用域&#xff08;Scope&#xff09;是一个非常重要的概念&#xff0c;…...

Python爬虫实战:抓取拼多多商品详情数据(基于pdd.item_get接口)

在当前的电商市场中&#xff0c;拼多多以其独特的拼团模式和优惠价格吸引了大量用户&#xff0c;成为继淘宝、京东之后的又一大电商平台。对于数据分析和市场研究者来说&#xff0c;获取拼多多的商品详情数据显得尤为重要。本文将介绍如何使用Python爬虫技术&#xff0c;通过调…...

工具类-列表请求工具 useList

useList 用于列表请求的基于 vue 3 的 hooks&#xff0c;接收请求函数、请求参数等数据&#xff0c;自动生成请求请求函数&#xff0c;分页信息等 本文有涉及到 http 请求工具和接口返回格式的内容&#xff1a; http 工具&#xff1a;一个基于 axios 封装的请求工具Response…...

Scala中的正则表达式01

规则类型具体规则示例说明单字符大多数字符匹配自身正则表达式 abc&#xff0c;文本 abca 匹配 a&#xff0c;b 匹配 b&#xff0c;c 匹配 c方括号 [ ][ ] 定义字符集&#xff0c;匹配其一[abc]&#xff0c;文本 a、b 或 c[abc] 匹配 a、b 或者 c排除字符集 [^ ][^ ] 开头加 ^&…...

基于SpringBoot的养老院管理系统的设计与实现

一、前言 随着人口老龄化的加剧&#xff0c;养老院作为老年人养老的重要场所&#xff0c;其管理的高效性和科学性显得尤为重要。传统的养老院管理方式多依赖人工操作&#xff0c;存在信息记录不及时、不准确&#xff0c;管理流程繁琐&#xff0c;资源调配困难等问题。利用信息技…...

Ansible变量详解(变量定义+变量优先级+变量注册+层级定义变量+facts缓存变量)

本篇文章详细给大家介绍Ansible变量&#xff0c;变量适合管理剧本中每个项目的动态值&#xff0c;或是某些值在多个地方重复使用&#xff0c;如果将此值设置为变量再在其他地方调用会方便许多。会用变量&#xff0c;才算真正会用Ansible&#xff0c;话不多说&#xff0c;直接开…...

面向对象系统的分析和设计

来源&#xff1a;《设计模式精解-GOF23种设计模式解析》 作者&#xff1a;k_eckel k_eckels mindview - 博客园 (cnblogs.com) --------- 面向对象系统的分析和设计实际上追求的就是两点&#xff1a; &#xff08;1&#xff09;高内聚 &#xff08;2&#xff09;低耦合 …...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 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 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。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. 什么是消息队列&#xff1f;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 主题模式…...

短视频矩阵系统文案创作功能开发实践,定制化开发

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

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

PHP 8.5 即将发布:管道操作符、强力调试

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