c++进阶——哈希表

在这里插入图片描述

嗨喽大家好呀，今天阿鑫给大家带来的是c++进阶——哈希表，好久不见啦，下面让我们进入本节博客的内容吧！

c++进阶——哈希表

  1. 枚举的介绍
  2. unordered系列的底层结构
  3. 哈希表的改造

哈希是一种思想(映射)，哈希表(值和存储位置建立的映射关系)是一种数据结构。

1.枚举

某些具有相同类别的变量没有支持的类型，用枚举来自定义一组命名的整数常量（0，1，2）来解决这一问题
与结构体的具有多个成员不同，每个枚举类型的变量都只能选择一个成员变量，但都属于自定义类型

注意：成员只能是枚举常量，这些常量在定义时会被赋予整数值（默认为从0开始的递增整数，但可以显式指定）。是一组整数值，但是有名字，提高了代码的可读性（0，1，2三个数可以表示三种颜色）
简单说：三个名字表示三种情况，但是这三个名字底层都是整数值

在这里插入图片描述

#include <iostream>  // 定义一个枚举类型Weekday，用于表示星期几  
enum Weekday {  Monday,  Tuesday,  Wednesday,  Thursday,  Friday,  Saturday,  Sunday  
};  int main() {  // 声明一个Weekday类型的变量today，并将其初始化为Wednesday  Weekday today = Wednesday;  // 使用switch语句根据today的值执行不同的操作  switch (today) {  case Monday:  std::cout << "今天是星期一" << std::endl;  break;  case Tuesday:  std::cout << "今天是星期二" << std::endl;  break;  case Wednesday:  std::cout << "今天是星期三" << std::endl;  break;  case Thursday:  std::cout << "今天是星期四" << std::endl;  break;  case Friday:  std::cout << "今天是星期五" << std::endl;  break;  case Saturday:  std::cout << "今天是星期六" << std::endl;  break;  case Sunday:  std::cout << "今天是星期日" << std::endl;  break;  }  return 0;  
}

在这里插入图片描述

2. unordered系列的底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。
在这里插入图片描述

2.1常见的哈希函数

1.直接定址法（用key的值映射一个绝对位置或相对位置）
优点：快，没有冲突
缺点：只适合范围集中
在这里插入图片描述
2.除留余数法（key模表的大小后,都可以映射到表中一个位置）
hashi = key%N（N是表的大小）
哈希冲突：不同的值取模后的值，映射到了表中的相同位置

2.2解决哈希冲突的方法

  1. 闭散列：开放地址法->去其他位置(规则)找一个空的位置在这里插入图片描述

  2. 开散列：哈希桶

在这里插入图片描述

#pragma once
#include<vector>
enum State//状态标记
{EXIST,EMPTY,EDLETE
};
template<class K,class T>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K, class V>
class HashTable
{
private:vector<HashData<K, V>> _tables;size_t _n =0//表中存储数据个数
};

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

扩容时进行了Insert的复用

bool Insert(const pair<K, V>& kv){如果key已经存在则插入失败if (Find(kv.first))return false;// 扩容if (_n * 10 / _tables.size() >= 7){//vector<HashData<K, V>> newTables(_tables.size() * 2); 遍历旧表， 将所有数据映射到新表 ...//_tables.swap(newTables);HashTable<K, V, Hash> newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hs;size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}

由于在实现Erase时，只是单纯将某个位置的状态标记置空，并没有抹除数据，所以在Find时，需要同时满足状态标记为存在以及key值相等才能返回true。

HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;return true;}}

哈希表需要支持类型之间的相互转换，因此需要提供一个哈希函数
当仿函数实现的功能相同，但是接受对象的类型不同时，就需要实现仿函数的特化

  1. 可以和整形之间相互转化
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
  1. 类似string类型不能和整形之间相互转换，需要支持一个特化的HashFunc
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
}

在这里插入图片描述

namespace hash_bucket
{template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_tables.resize(10, nullptr);}private:vector<Node*> _tables;  // 指针数组size_t _n = 0;			// 表中存储数据个数};

在这里插入图片描述
和闭散列直接插入(先new节点，再delete节点)不同，节点的重复利用可以节省时间

bool Insert(const pair<K, V>& kv){Hash hs;size_t hashi = hs(kv.first) % _tables.size();// 负载因子==1扩容if (_n == _tables.size()){/*HashTable<K, V> newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while(cur){newHT.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newHT._tables);*/vector<Node*> newtables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 旧表中节点，挪动新表重新映射的位置size_t hashi = hs(cur->_kv.first) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}

节点的删除分为头节点和其他节点
头节点：指针数组中的指针指向头节点的下一个节点
其余节点：当前节点的前一个节点指向当前节点的下一个节点，释放当前节点
在这里插入图片描述

bool Erase(const K& key)
{Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else//此时说明销毁节点不是头节点{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;
}

下面给出一份完整的闭散列解决哈希冲突的实现代码

namespace hash_bucket
{template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable(){_tables.resize(10, nullptr);}~HashTable(){// 依次把每个桶释放for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}bool Insert(const pair<K, V>& kv){Hash hs;size_t hashi = hs(kv.first) % _tables.size();// 负载因子==1扩容if (_n == _tables.size()){/*HashTable<K, V> newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while(cur){newHT.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newHT._tables);*/vector<Node*> newtables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 旧表中节点，挪动新表重新映射的位置size_t hashi = hs(cur->_kv.first) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}Node* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hs;size_t hashi = hs(key) % _tables .size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private://vector<list<pair<K, V>>> _tables;  // 指针数组//struct Bucket//{//	list<pair<K, V>> _lt;//	map<K, V> _m;//	size_t _bucketsize;   // >8 map  <=8 list//};//vector<Bucket> _tables;vector<Node*> _tables;  // 指针数组size_t _n = 0;			// 表中存储数据个数};

好啦，今天我们的学习就到这里哦，本节课内容还是有点难度的，下节课我们将学习如何将哈希表用于实现unordered系列，希望大家能够好好吸收理解，期待我们的下一次再见

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

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

相关文章

搭建Docker私有仓库管理本地的Docker镜像，通过harbor实现Web UI访问和管理私有仓库

搭建Docker私有仓库管理本地的Docker镜像，通过harbor实现Web UI访问和管理私有仓库

要在本地搭建一个Docker私有仓库&#xff0c;你可以按照以下步骤进行设置&#xff1a; 安装Docker 确保你已经安装了Docker。如果还没有安装&#xff0c;可以按照官方指南进行安装&#xff1a; 对于Ubuntu系统&#xff0c;你可以运行以下命令来安装Docker&#xff1a; sudo ap…
阅读更多...
十一、C语言：字符串函数

十一、C语言：字符串函数

目录 一、strlen 二、strcpy 三、strcat 四、strcmp 五、strstr 六、strtok 七、strerror 一、strlen 注意&#xff1a;strlen()函数的返回值是size_t&#xff0c;两个size_t相减仍为无符号数 int main() {char arr[10] "abc";char brr[10] "abc123&quo…
阅读更多...
OpenCV结构分析与形状描述符（11）椭圆拟合函数fitEllipse()的使用

OpenCV结构分析与形状描述符（11）椭圆拟合函数fitEllipse()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 围绕一组2D点拟合一个椭圆。 该函数计算出一个椭圆&#xff0c;该椭圆在最小二乘意义上最好地拟合一组2D点。它返回一个内切椭圆的旋转矩形。使…
阅读更多...
【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82， 237

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82， 237

总结&#xff0c;删除链表节点问题使用到列表&#xff0c;哈希表&#xff0c;递归比较容易超时&#xff0c;我觉得使用计数排序比较稳&#xff0c;处理起来也不是很难。 1. 力扣3217&#xff1a;从链表中移除在数组中的节点 1.1 题目&#xff1a; 给你一个整数数组 nums 和一…
阅读更多...
【Linux】应用层http协议

【Linux】应用层http协议

一、HTTP协议 1.1 简要介绍一下HTTP 我们在网络的应用层中可以自己定义协议&#xff0c;但是&#xff0c;已经有大佬定义了一些现成的&#xff0c;非常好用的应用层协议&#xff0c;供我们直接使用&#xff0c;HTTP&#xff08;超文本传输协议&#xff09;就是其中之一。 在互…
阅读更多...
yolo算法小结

yolo算法小结

文章目录 yolov1工作原理限制 yolov2网络结构改进点 yolov3改进点 yolov4网络结构图改进点 yolov5改进点 参考资料 YOLO的核心思想是将物体检测视为一个回归问题&#xff0c;它不采用传统的区域提议方法&#xff0c;而是通过单一的神经网络对整个图像进行预测。这意味着YOLO只需…
阅读更多...
C/C++两点坐标求距离以及C++保留两位小数输出，秒了

C/C++两点坐标求距离以及C++保留两位小数输出，秒了

目录 1. 前言 2. 正文 2.1 问题 2.2 解决办法 2.2.1 思路 2.2.2 代码实现 3. 备注 1. 前言 依旧是带来一个练手的题目&#xff0c;目的就一个&#xff0c;方法千千万&#xff0c;通向终点的方式有很多种&#xff0c;没有谁与谁&#xff0c;我们都是为了成为更好的自己。…
阅读更多...
使用亚马逊Bedrock的Stable Diffusion XL模型实现文本到图像生成：探索AI的无限创意

使用亚马逊Bedrock的Stable Diffusion XL模型实现文本到图像生成：探索AI的无限创意

引言 什么是Amazon Bedrock&#xff1f; Amazon Bedrock是亚马逊云服务&#xff08;AWS&#xff09;推出的一项旗舰服务&#xff0c;旨在推动生成式人工智能&#xff08;AI&#xff09;在各行业的广泛应用。它的核心功能是提供由顶尖AI公司&#xff08;如AI21 Labs、Anthropic…
阅读更多...
python中的循环结构

python中的循环结构

注意&#xff1a;range&#xff08;&#xff09;函数 累加和&#xff1a; 注意&#xff1a;if 下面如果有好几行&#xff0c;只执行一行 print必须和 for 开头相同格数 例题&#xff1a;水仙花数 注意在print语句中&#xff0c;一句好“ 。。。。。 ”后面必须有逗号然后再写变…
阅读更多...
C++（一）----C++基础

C++（一）----C++基础

1.C的发展史 C语言诞生后&#xff0c;很快普及使用&#xff0c;但是随着编程规模增大且越来越复杂&#xff0c;并且需要高度的抽象和建模时&#xff0c;C语言的诸多短板便表现了出来&#xff0c;为了解决软件危机&#xff0c;上世纪八十年代&#xff0c;计算机界提出了oop&…
阅读更多...
linux top命令介绍以及使用

linux top命令介绍以及使用

文章目录 介绍 top 命令1. top 的基本功能2. 如何启动 top3. top 的输出解释系统概况任务和 CPU 使用情况内存和交换空间进程信息 4. 常用操作 总结查看逻辑CPU的个数查看系统运行时间 介绍 top 命令 top 是一个在类 Unix 系统中广泛使用的命令行工具&#xff0c;用于实时显示…
阅读更多...
WebGL系列教程二（环境搭建及初始化Shader）

WebGL系列教程二（环境搭建及初始化Shader）

目录 1 前言2 新建html页面3 着色器介绍3.1 顶点着色器、片元着色器与光栅化的概念3.2 声明顶点着色器3.3 声明片元着色器 4 坐标系(右手系)介绍5 着色器初始化5.1 给一个画布canvas5.2 获取WebGL对象5.3 创建着色器对象5.4 获取着色器对象的源5.5 绑定着色器的源5.6 编译着色器…
阅读更多...
ChatGPT 3.5/4.0使用手册：解锁人工智能的无限潜能

ChatGPT 3.5/4.0使用手册：解锁人工智能的无限潜能

1. 引言 在人工智能的浪潮中&#xff0c;ChatGPT以其卓越的语言理解和生成能力&#xff0c;成为了一个革命性的工具。它不仅仅是一个聊天机器人&#xff0c;更是一个能够协助我们日常工作、学习和创造的智能伙伴。随着ChatGPT 3.5和4.0版本的推出&#xff0c;其功能和应用范围…
阅读更多...
windows电脑自动倒计时关机

windows电脑自动倒计时关机

今天聊一聊其他的。我时不时的有一个需求&#xff0c;是关于在windows电脑上定时关机。 不知道怎么地&#xff0c;我好几次都忘了这个自动定时关机的终端命令&#xff0c;于是每一次都要去网上查。 1.鼠标右击【开始菜单】选择【运行】或在键盘上按【 WinR】快捷键打开运行窗口…
阅读更多...
线性代数|机器学习-P36在图中找聚类

线性代数|机器学习-P36在图中找聚类

文章目录 1. 常见图结构2. 谱聚类 感觉后面几节课的内容跨越太大&#xff0c;需要补充太多的知识点&#xff0c;教授讲得内容跨越较大&#xff0c;一般一节课的内容是书本上的一章节内容&#xff0c;所以看视频比较吃力&#xff0c;需要先预习课本内容后才能够很好的理解教授讲…
阅读更多...
网络学习-eNSP配置VRRP

网络学习-eNSP配置VRRP

虚拟路由冗余协议(Virtual Router Redundancy Protocol&#xff0c;简称VRRP) VRRP广泛应用在边缘网络中&#xff0c;是一种路由冗余协议&#xff0c;它的设计目标是支持特定情况下IP数据流量失败转移不会引起混乱&#xff0c;允许主机使用单路由器&#xff0c;以及即使在实际…
阅读更多...
模版的价值工程

模版的价值工程

我们在做什么 工作吗 最终不过是在做模版工程模版&#xff0c;最终会进化 沦为后世的参考文档。仅此而已&#xff01; 或者已经沦为了文档类别 其他&#x1f4c4; 最终我们会选择EXIT 指令 尽快它是 window桌面 我们只是图像 人字&#x1f31f;的&#x1f9a3; &#x1f631;…
阅读更多...
leveldb源码剖析（二）——LSM Tree

leveldb源码剖析（二）——LSM Tree

LSM Tree LSM Tree&#xff1a;Log-Structured Merge Tree&#xff0c;日志结构合并树。是一种频繁写性能很高的数据结构。 LSM Tree将写入操作与合并操作分离&#xff0c;数据首先写入磁盘中的日志文件&#xff08;WAL&#xff09;&#xff0c;随后写入内存缓存&#xff0c;…
阅读更多...
Adobe After Effects的插件--------CC Particle World

Adobe After Effects的插件--------CC Particle World

CC Particle World是一个粒子效果器，用于在三维空间中生成和模拟各种粒子系统，包括火焰、雨、雪、爆炸、烟雾等等。它会自动随时间变化发射粒子。 本文部分参照 https://www.163.com/dy/article/IEJVDN760536FE6V.html 使用条件 使用该插件的图层需是2D图层。 我们新建一个…
阅读更多...
Matlab simulink建模与仿真 第十一章（端口及子系统库）【上】

Matlab simulink建模与仿真 第十一章（端口及子系统库）【上】

参考视频&#xff1a;simulink1.1simulink简介_哔哩哔哩_bilibili 一、端口及子系统库中的模块概览 注&#xff1a;In模块、Out模块和Subsystem模块在第二章中均有介绍&#xff0c;本章不再赘述&#xff1b;Subsystem Examples子系统实例模块也不进行介绍。 二、使能及其子模…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发