C++基础学习——哈希表的封装

目录

​编辑

一，实现一个可封装的哈希表

1，哈希表的节点

 2，哈希表的成员

 3，哈希表成员方法的实现

 4，迭代器的实现

 5，在哈希表中加入迭代器

二，封装哈希表

1，unorder_map封装

2，unordered_set的封装

 

一，实现一个可封装的哈希表

1，哈希表的节点

在哈希表的封装中，分为两类：unordered_map,unordered_set。其中map的元素类型为pair<K,V>类型，set的类型为K类型。

Node实现如下：

   template<class T>struct Node{Node<T>* _next;T val;};

 2，哈希表的成员

哈希表的成员有两个，一个是记录哈希表节点个数的成员_n，一个是成员为Node*类型的vector<Node*>数组。

HashTable实现如下：

template<class T>class HashTables{typedef Node<T> Node;public:private:vector<Node*>_tables;size_t _n;};

 3，哈希表成员方法的实现

（1），Find(V&key)方法

Find方法实现的是在一个哈希表中寻找某个值存不存在。步骤如下：1，找到这个值对应的hashi（在哈希表中的下标）。2，遍历这个下标上挂载的链表上是否有该值。3，有则返回true,没有就返回false.

要找到hashi: 先实现两个方法Getkey()与GetHashi()

Getkey()：

    template <class K,class V>struct Getkey{K operator()(const V& val)//一般的成员直接返回val,遇到特殊pair类型的则返回val.first(先不实现){return val;}};

 GetHashi()：

template <class T>//一般情况下struct GetHashi{size_t operator(T& val){return (size_t)val;}};template<>//模板特化，当这个成员的类型为string类型时struct GetHashi<string>{size_t operator()(string& val){size_t ret = 0;for (int i = 0;i < val.size();i++){ret += ret * 31 + val[i];}return ret;}};

Find():

       bool Find(V& val){size_t hashi = GetHashi(Getkey(val)) % _tables.size();//计算hashiNode* cur = _tables[hashi];//找到对应的位置上的链表while (cur)//开始寻找{if (cur->val == _val) return true;}return false;}

（2），Insert（T&key）

 实现插入函数：(1)，满载时要扩容，扩容逻辑是创建一个新的vector<Node*>temp并且把这个表的大小扩为旧表的二倍。 (2)，将旧表中的元素拆下来头插到新表中。（3），将就表中的值全部变为nullptr,防止二次析构。（4），将新表交换给旧表

Insert函数代码： 

bool Insert(const V& val){if (Find(val)) return false;//存在过则直接返回插入失败if (_n == _tables.size())//检查是否需要扩容{int newsize = 2*(_n == 0? 1 : _n);//新的大小vector<Node*>temp;//开一个临时数组temp.resize(newsize);//扩大为原来哈希表的二倍for (int i = 0;i < _tables.size();i++){Node* cur = _tables[i];Node* next = nullptr;if (cur){while (cur){size_t hashi = GetHashi(Getkey(cur->_val))%_tables.size();//计算新的哈希值//保存下一个值，并更新就哈希表上的值next = cur->_next;_tables[i] = next;//头插到新的哈希表中cur->_next = temp[hashi];temp[hashi] = cur;cur = next;}}}//扩容好后便夺回来for (int i = 0;i < _tables.size();i++){_tables[i] = nullptr;}_tables.swap(temp);}int hashi = GetHashi(Getkey(val))%_tables.size();Node* newNode = new Node(val);//头插newNode->_next = _tables[hashi];_tables[hashi] = newNode;_n++;return true;}

 （3）Erase(V&val)

实现：先找到这个值，再删除。

Erase（V&val）代码：

       bool Erase(const V& val){int hashi = GetHashi(Getkey(val)) % _tables.size();//计算hashiNode* pre = nullptr;//记录hashi前面的指针Node* cur = _tables[hashi];//当前指针while (cur){if (cur->_val == val)//有相同的便开始执行删除逻辑{if(pre)pre->_next = cur->_next;//加上条件防止头删出错delete cur;cur = nullptr;_n--;return true;}pre = cur;cur = cur->_next;}return false;}

 4，迭代器的实现

（1），迭代器的成员

迭代器的成员：1，一个Node*类型的成员_node（因为迭代器就是一种模拟指针的行为所以要有哈希表元素的指针）。2，哈希表的指针和当前的_node对应的位置（主要是为了方便实现++）。

代码如下：

        typedef HTiterator<K, V, ref, ptr, Getkey, GetHashi> self;//迭代器类型typedef Node<V> Node;Node* _node;//哈希表成员的指针typedef HashTables<K, V, Getkey, GetHashi>*  pht;pht _pht;//哈希表的指针size_t _hashi;//迭代器在哈希表中的位置

（2）迭代器++的实现

1，找到下一个不为nullptr的点（这里要用到哈希表的指针和当前指针的位置） 。  2，返回一个迭代器。3，在实现++之前得实现一个迭代器的构造函数。

构造函数代码：

        HTiterator(Node* node,pht Hp,size_t hashi)//构造函数:_node(node),_pht(Hp),_hashi(hashi){}

实现迭代器operator++()代码：

//实现++self operator ++(){if (_node->_next){_node = _node->_next;}else{_hashi++;while (_hashi < _pht->_tables.size()){if (_pht->_tables[_hashi]){_node = _pht->_tables[_hashi];return HTiterator(_node, _pht, _hashi);//找到了直接返回构造的iterator}_hashi++;}_node = nullptr;//找不到就将_node置为nullptr在构造}return  HTiterator(_node, _pht, _hashi);}

（3）实现operator*()，operator->(),operator!=()

*:返回值是_node里面的val。->:返回值是_node->val的地址。！=：比较的是_node

 代码：

        ref operator*(){return _node->_val;}ptr operator->(){return& _node->_val;}bool operator!=(const self& s){return _node != s._node;}

 5，在哈希表中加入迭代器

       typedef HTiterator<K, V, V&, V*> iterator;//定义一个迭代器类型iterator begin()//实现begin(){for (int hashi = 0;hashi < _tables.size();hashi++){if (_tables[hashi]) return iterator(_tables[hashi], this, hashi);}return end();}iterator end()//实现end(){return iterator(nullptr, this, -1);}

二，封装哈希表

1，unorder_map封装

(1)unordered_map的成员

unordered_map的底层便是一个哈希表，所以unordered_map的成员便是一个哈希表。

代码：

cq::HashTables<K,pair<K, V>, Getkey<K,V>> HT;

（2）unordered_map的方法

在实现这些方法之前，先得把哈希表里的Insert()和Find()方法的返回值改一下，改成如下形式：pair<iterator,bool>，方便后面的operator[]的实现。

代码：

pair<iterator,bool> Insert(const V& val)//改成pair<iterator,bool>类型{iterator it = Find(val);if (it != end()) return make_pair(it, false);if (_n == _tables.size())//检查是否需要扩容{int newsize = 2*(_n == 0? 1 : _n);//新的大小vector<Node*>temp;//开一个临时数组temp.resize(newsize);for (int i = 0;i < _tables.size();i++){Node* cur = _tables[i];Node* next = nullptr;if (cur){while (cur){size_t hashi = GetHashi(Getkey(cur->_val))%_tables.size();//计算新的哈希值//保存下一个值，并更新就哈希表上的值next = cur->_next;_tables[i] = next;//头插到新的哈希表中cur->_next = temp[hashi];temp[hashi] = cur;cur = next;}}}//扩容好后便夺回来for (int i = 0;i < _tables.size();i++){_tables[i] = nullptr;}_tables.swap(temp);}size_t hashi = GetHashi(Getkey(val))%_tables.size();Node* newNode = new Node(val);//头插newNode->_next = _tables[hashi];_tables[hashi] = newNode;_n++;return   make_pair(iterator(newNode, this, hashi),true);}

（2） 实现V& operator[](K&key)

operator[]的作用是让我们能够通过key值来访问val值。

代码：

       V& operator[](const K& key){pair<iterator,bool> ret = HT.Insert(make_pair(key,V()));return  ret.first->second;//返回的是一个pair<iterator,bool>,first代表iterator，然后再调用iterator的->找到val值}

（3）unordered_map里其它的成员方法

其它的成员方法都是通过调用哈希表里面实现的方法实现的。

       iterator begin(){return HT.begin();}iterator end(){return HT.end();}pair<iterator, bool> insert(const pair<K,V>& val){return HT.Insert(val);}bool erase(const V& val){return HT.Erase(val);}pair<iterator,bool> Find(const V& val){return HT.Find(val);}

unordered_map封装代码：

	template < class K,class V>struct Getkey{K operator()(const pair<K,V>& val){return val.first;}};template <class K, class V>class my_unordered_map{typedef typename cq::HashTables<K, pair<K,V>, Getkey<K,V>>::iterator iterator;public:iterator begin(){return HT.begin();}iterator end(){return HT.end();}pair<iterator, bool> insert(const pair<K,V>& val){return HT.Insert(val);}bool erase(const V& val){return HT.Erase(val);}pair<iterator,bool> Find(const V& val){return HT.Find(val);}V& operator[](const K& key){pair<iterator,bool> ret = HT.Insert(make_pair(key,V()));return  ret.first->second;}private:cq::HashTables<K,pair<K, V>, Getkey<K,V>> HT;};

 

2，unordered_set的封装

unordered_set的封装与unordered_map的封装类似。但是不用实现operator[]。

 代码如下：

	template < class K>//set的模板参数只要一个struct Getkey{K operator()(const K& val){return val;}};template <class K>class my_unordered_set{typedef typename cq::HashTables<K, K, Getkey<K>>::iterator iterator;public:iterator begin(){return HT.begin();}iterator end(){return HT.end();}pair<iterator, bool> insert(const K& val){return HT.Insert(val);}bool erase(const K& val){return HT.Erase(val);}pair<iterator, bool> Find(const K& val){return HT.Find(val);}private:cq::HashTables<K, K, Getkey<K>> HT;//内部成员哈希表};

 

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

win10安装使用AxurePR9

win10安装使用AxurePR9

背景&#xff1a;win10 安装、汉化 Axure Pr9 下载 安装包 链接&#xff1a;https://pan.baidu.com/s/1taMgh2zLbaFK7VTfUXTHdQ 提取码&#xff1a;kygo 安装 修改安装目录 打开是英文的 汉化 复制lang包到Axure安装包 再打开就是中文 问题 发布html后火狐无法打开 一、…
阅读更多...
抖音数据挖掘软件|视频内容提取

抖音数据挖掘软件|视频内容提取

针对用户获取抖音视频的需求&#xff0c;我们开发了一款功能强大的工具&#xff0c;旨在解决用户在获取抖音视频时需要逐个复制链接、下载的繁琐问题。我们希望用户能够通过简单的关键词搜索&#xff0c;实现自动批量抓取视频&#xff0c;并根据需要进行选择性批量下载。因此&a…
阅读更多...
实现外网手机或者电脑随时随地远程访问家里的电脑主机(linux为例)

实现外网手机或者电脑随时随地远程访问家里的电脑主机(linux为例)

文章目录 一、背景概要二、安装配置花生壳软件(linux版本)三、手机端(外网)验证连接四、安装ubuntu20server版系统遇到的问题记录 一、背景概要 由于经常在遇到某些问题的时候&#xff0c;针对某一个场景的理解&#xff0c;需要借助于自己的电脑去编译(aosp/linux/qemu)代码查…
阅读更多...
PHP语言检测用户输入密码及调用Python脚本

PHP语言检测用户输入密码及调用Python脚本

现在有一份计算流体力学N-S方程的Python脚本&#xff0c;想要在用户登录网站后可以可以运行该脚本&#xff0c;然后将脚本运行后绘制的图片显示在用户网页上。 建一个名为N_S.py的python脚本文件&#xff0c;这个脚本在生成图像后会自行关闭&#xff0c;随后将图片保存在指定的…
阅读更多...
SpringMVC 学习（三）之 @RequestMapping 注解

SpringMVC 学习（三）之 @RequestMapping 注解

目录 1 RequestMapping 注解介绍 2 RequestMapping 注解的位置 3 RequestMapping 注解的 value 属性 4 RequestMapping 注解的 method 属性 5 RequestMapping 注解的 params 属性&#xff08;了解&#xff09; 6 RequestMapping 注解的 headers 属性&#xff08;了解&…
阅读更多...
【Android】坐标系

【Android】坐标系

Android 系统中有两种坐标系&#xff0c;分别为 Android 坐标系和 View 坐标系。了解这两种坐标系能够帮助我们实现 View 的各种操作&#xff0c;比如我们要实现 View 的滑动&#xff0c;你连这个 View 的位置都不知道&#xff0c;那如何去操作呢&#xff1f; 一、Android 坐标…
阅读更多...
【Flink精讲】Flink 内存管理

【Flink精讲】Flink 内存管理

面临的问题 目前&#xff0c; 大数据计算引擎主要用 Java 或是基于 JVM 的编程语言实现的&#xff0c;例如 Apache Hadoop、 Apache Spark、 Apache Drill、 Apache Flink 等。 Java 语言的好处在于程序员不需要太关注底层内存资源的管理&#xff0c;但同样会面临一个问题&…
阅读更多...
【接口加密】接口加密的未来发展与应用场景

【接口加密】接口加密的未来发展与应用场景

目录 3.1 接口加密与区块链技术的结合 3.1.1 区块链技术的安全特性与优势 3.1.2 接口加密在区块链中的应用案例 3.2 接口加密与物联网安全 3.2.1 物联网安全的挑战与需求 3.2.2 接口加密在物联网领域的实际应用 3.3 接口加密在金融与电子商务领域的应用 随着信息技术的不…
阅读更多...
Java中的常量与变量：初探Java世界的基石

Java中的常量与变量：初探Java世界的基石

✨✨ 所属专栏&#xff1a; Java基石&#xff1a;深入探索Java核心基础✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; 目录 引言 一. 常量与变量的概念 常量 变量 总结 二. 常量的分类 1. 字面常量 2. 常量变量 3. 枚举常量…
阅读更多...
8 buuctf解题

8 buuctf解题

[BJDCTF2020]just_a_rar 1 下载&#xff0c;得到 发现有加密 使用ARCHPR设置四位数掩码爆破 得到口令2016&#xff0c;解压得到图片&#xff0c;flag在图片exif中 在备注里面看见了flag [HBNIS2018]excel破解 1 下载下来是attachment.xls 修改后缀为rar 使用010 Editor打开&a…
阅读更多...
力扣技巧题：丢失的数字

力扣技巧题：丢失的数字

先排后找可以让结果更简单 int cmp(const void* a, const void* b){return *(int*)a - *(int*)b; } int missingNumber(int* nums, int numsSize){qsort(nums, numsSize, 4, cmp);for(int i0; i<numsSize; i){if(nums[i] i){continue;}else{return i;}}return numsSize; }…
阅读更多...
RandAugment（NeurIPS 2020）论文速读

RandAugment（NeurIPS 2020）论文速读

paper&#xff1a;RandAugment: Practical automated data augmentation with a reduced search space third-party implementation&#xff1a;https://github.com/open-mmlab/mmpretrain/blob/main/mmpretrain/datasets/transforms/auto_augment.py 存在的问题 自动增强策…
阅读更多...
k8s学习笔记-基础概念

k8s学习笔记-基础概念

&#xff08;作者&#xff1a;陈玓玏&#xff09; deployment特别的地方在于replica和selector&#xff0c;docker根据镜像起容器&#xff0c;pod控制容器&#xff0c;job、cronjob、deployment控制pod&#xff0c;job做离线任务&#xff0c;pod大多一次性的&#xff0c;cronj…
阅读更多...
React 模态框的设计（一）拖动组件的设计

React 模态框的设计（一）拖动组件的设计

春节终结束了&#xff0c;忙得我头疼。终于有时间弄自己的东西了。今天来写一个关于拖动的实例讲解。先看效果&#xff1a; 这是一个简单的组件设计&#xff0c;如果用原生的js设计就很简单&#xff0c;但在React中有些事件必须要多考虑一些。这是一个系列的文章&#xff0c;…
阅读更多...
UI设计中，2D、2.5D、3D、4D该如何辨别？教会你

UI设计中，2D、2.5D、3D、4D该如何辨别？教会你

hello&#xff0c;我是大千UI工场&#xff0c;从事UI设计8年之久&#xff0c;在日常工作中经常听到一些概念&#xff0c;现在将这些概念图文并茂的呈现给您&#xff0c;欢迎点赞评论&#xff0c;如有设计需求&#xff0c;可以私信我们。 在UI设计中&#xff0c;2D、2.5D、3D和4…
阅读更多...
企业计算机服务器中了babyk勒索病毒怎么办？Babyk勒索病毒解密数据恢复

企业计算机服务器中了babyk勒索病毒怎么办？Babyk勒索病毒解密数据恢复

随着网络技术的应用与普及&#xff0c;越来越多的企业采用了数字化办公模式&#xff0c;数字化办公模式可以为企业提供强有力的数据支撑&#xff0c;可以为企业的发展方向与产品业务调整做好基础工作。但网络是一把双刃剑&#xff0c;在为企业提供便利的同时&#xff0c;也为企…
阅读更多...
Visual Studio 打开.edmx文件不显示表并报错：没有可用于.edmx的编辑器

Visual Studio 打开.edmx文件不显示表并报错：没有可用于.edmx的编辑器

打开.edmx文件时&#xff0c;呈现的是xml视图&#xff0c;不显示Diagram视图&#xff0c;且弹出报错“没有可用于.edmx的编辑器” 解决方案&#xff1a;在.edmx文件上右键&#xff0c;选择ado.net entity data model designer&#xff0c;即可正常显示表
阅读更多...
EasyRecovery2024数据恢复软件深度评测与使用教程

EasyRecovery2024数据恢复软件深度评测与使用教程

一、EasyRecovery数据恢复软件是否好用&#xff1f; EasyRecovery是一款业界知名的数据恢复软件&#xff0c;具有强大的恢复能力和广泛的数据兼容性。它能帮助用户从各种存储设备中恢复丢失或删除的数据&#xff0c;包括硬盘、U盘、SD卡等。以下是关于EasyRecovery的详细分析&…
阅读更多...
《C++面向对象程序设计》✍学习笔记

《C++面向对象程序设计》✍学习笔记

C的学习重点 C 这块&#xff0c;重点需要学习的就是一些关键字、面向对象以及 STL 容器的知识&#xff0c;特别是 STL&#xff0c;还得研究下他们的一些源码&#xff0c;下面是一些比较重要的知识&#xff1a; 指针与引用的区别&#xff0c;C 与 C 的区别&#xff0c;struct 与…
阅读更多...
25-k8s集群中-RBAC用户角色资源权限

25-k8s集群中-RBAC用户角色资源权限

一、RBAC概述 1&#xff0c;k8s集群的交互逻辑&#xff08;简单了解&#xff09; 我们通过k8s各组件架构&#xff0c;知道各个组件之间是使用https进行数据加密及交互的&#xff0c;那么同理&#xff0c;我们作为“使用”k8s的各种资源的使用者&#xff0c;也是通过https进行数…
阅读更多...
最新文章

Copyright @ 2022~2023