当前位置: 首页 > 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;低耦合 …...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...