【C++进阶】用哈希实现unordered_set和unordered_map的模拟

🪐🪐🪐欢迎来到程序员餐厅💫💫💫

          主厨：邪王真眼

主厨的主页：Chef‘s blog  

所属专栏：c++大冒险
 

总有光环在陨落，总有新星在闪烁

前言：

        之前我们学完红黑树后对他进行了改造，使之成为map和set的底层容器，今天我们则要把哈希表进行修改并以此为基础实现unordered_set和unordered_map

一.哈希桶（修改版）

1.1.节点

template<class T>
struct HashNode
{HashNode<T> _next;T _data;HashNode(const T& data = T()):_next(nullptr), _data(data){}
};

注意事项：

  • 数据类型是T，因为要同时适用unordered_set（存储键值）和unordered_map（存储键值对）

类比咱们用红黑树写map和set时的做法。

1.2.迭代器

哈希表的迭代器类型是单向迭代器，没有反向迭代器

1.2.1成员变量

template<class K, class T, class KeyOfT, class HF>
class HashTable;
template<class K,class T, class Ref,class Ptr,class KeyOfT, class HF>
struct HashIterator
{typedef HashNode<T> Node;typedef HashIterator<K, T, Ref, Ptr, KeyOfT, HF> self;typedef HashIterator<K, T, T&, T*, KeyOfT, HF> iterator;typedef HashTable<K, T, KeyOfT, HF> HT;Node* _node;HT* _ht;
};

注意事项：

  •  增加了_ht成员变量，因为在重载++时，当一条单链表走到空，则需要走到下一个哈希桶的位置，需要通过哈希表的vector成员找下一个位置 
  • 因为HashTable是在后面实现的，所以我们要先写一个声明

1.2.2简单函数实现

HashIterator(Node*&node=nullptr,Node*&ht=nullptr):_node(node),_ht(ht)
{}
HashIterator(const iterator&it):_node(it._node), _ht(it._ht)
{}
Ref& operator*()const
{return _node->_data;
}
Ptr& operator->()const
{return &(_node->_data);
}
bool operator==(const self&se)
{return _node == se._node;
}
bool operator!=(const self& se)
{return _node != se._node;
}

注意事项：

  • 拷贝构造函数可以以普通迭代器拷贝出普通迭代器（普通迭代器调用时）以及const迭代器（const迭代器调用时）

1.2.3operator++

self& operator++()
{Node* node = _node;if (node->_next){_node = node->_next;return *this;}else{KeyOfT kot;size_t hash = HF(kot(_node->_data)) % _ht->_tables.size()+1;for (hash; hash < _ht->_tables.size(); hash++){if (_ht->tables[hash]){_node = _ht->tables[hash];return *this;}}_node = nullptr;return *this;}
}
self operator++(int)
{self new_self=*this;(*this)++;return new_self;
}

思路：

  1. 前置++的思路： 
    1. 下一个结点不为空，则跳到下一位
    2. 下一个结点为空，则先取模算出哈希地址，再往后探测不为空的哈希桶 
  2. 后置++：复用前置++，返回临时对象

1.3哈希桶本身

1.3.1成员变量

template<class K, class T, class KeyOfT, class HF>
class HashTable
{template<class K, class T, class Ref, class Ptr, class KeyOfT, class HF>friend struct HashIterator;typedef HashNode<T> Node;
public:
protected:vector<Node*> _tables;size_t _size = 0;//有效数据个数
};

注意事项：

  1. 迭代器要访问哈希桶的私有成员，所以要声明友元
  2. 模板参数KeyOfT是为了从类型T中取出键值
  3. 模板参数HF即是HashFunc，哈希函数，用于辅助键值转化为整型进行取模操作

1.3.2构造函数和析构函数

HashTable(size_t size = 10)
{_tables.resize(size);
}
~HashTable()
{for (auto hash_node : _tables){while (hash_node){Node* new_node = hash_node->_next;delete hash_node;hash_node = new_node;}}
}

1.3.3 begin和end 

typedef HashIterator< K,T, T&, T*,  KeyOfT,  HF> iterator;
typedef HashIterator< K, T, const T&, const T*,  KeyOfT,  HF> const_iterator;
iterator begin()
{for (size_t i = 0; i < _tables.size(); i++)if (_tables[i])return iterator(_tables[i], this);return iterator(nullptr, this);
}
const_iterator begin()const
{for (size_t i = 0; i < _tables.size(); i++)if (_tables[i])return const_iterator(_tables[i], this);return const_iterator(nullptr, this);
}
iterator end()
{return iterator(nullptr, this);
}
const_iterator end()
{return const_iterator(nullptr, this);
}

注意事项：

  1. begin返回最开始不为空的哈希桶的迭代器，而不是最开始的哈希桶的迭代器
  2. end返回空迭代器
  3. 构造迭代器需要传入哈希表本身的地址，这里直接传this指针即可

1.3.4Find函数 

iterator Find(const K&key)
{HF hf;KeyOfT kot;size_t hash = hf(key) % _tables.size();Node* cur = _tables[hash];while (cur){if (kot(cur->_data) == key)return iterator(cur,_tables);cur = cur->_next;}return iterator(nullptr,_tables);
}

注意事项：

  1. 返回值类型是迭代器
  2. 运用两个仿函数，，kot负责获取存储的键值，hf作为哈希函数把键值key转整型

1.3.5   Insert函数 

	pair<iterator,bool> Insert(T& data)
{KeyOfT kot;HF hf;iterator it = Find(kot(data));if (it._node){return make_pair(it, false);}if (_size == _tables.size()){vector<Node*> new_tables(_size * 2);for (auto node : _tables){while (node){Node* next = node->_next;size_t hash = hf(kot(node->_data)) % new_tables.size();node->_next = new_tables[hash];new_tables[hash] = node;node = next;}}_tables.swap(new_tables);}size_t hash = hf(kot(data)) % _tables.size();Node* cur = _tables[hash];Node* p(data);p->_next = cur;_tables[hash] = p;_size++;return make_pair(iterator(p,this),true);
}

注意事项：

  1. 返回值类型是pair，第一个参数为迭代器，第二个参数为布尔值（记录是否插入成功）
  2. 运用两个仿函数，，kot负责获取存储的键值，hf作为哈希函数把键值key转整型

1.3.6Erase函数 

	bool Erase(const K& key)
{HF hf;KeyOfT kot;size_t hash = hf(key) % _tables.size();Node* cur = _tables[hash];Node* pre = nullptr;while (cur){if (kot(cur->data) == key)break;pre = cur;cur = cur->_next;}if (cur == nullptr)return false;_size--;if (pre == nullptr)_tables[hash] = cur->_next;elsepre->_next = cur->_next;delete cur;return true;
}

二、unordered_set

2.1成员变量及仿函数 

template<class K,class HF=HashFunc<K>>
class unordered_set
{
public:struct SetKeyOfT{K& operator()(const K& key){return key;}};
protected:HashTable<K, K, SetKeyOfT, HF> _hf;
};

注意事项：

  •  1.这里的数据存储类型就是键值Key本身，所以SetKeyOfT直接返回key就行
  • 2.哈希函数不是固定的，可以根据需求自己进行实现并传到给定模板参数中

2.2 begin和end 

typedef typename HashTable<K, K, SetKeyOfT, HF>::iterator iterator;
typedef typename HashTable<K, K, SetKeyOfT, HF>::const_iterator const_iterator;
iterator begin()
{return _ht.begin();
}
const_iterator begin()const
{return _ht.begin();
}
iterator end()
{return _ht.end();
}
const_iterator end()const
{return _ht.end();
}

注意事项：

  • 在C++中，编译器默认iterator为变量名，如果作为类型名，需要在前面加上typename加上typename关键字。
  • unordered_set中存储的键值key不允许修改，所以其普通迭代器和const迭代器均为哈希表的const迭代器
  • 我们称set的begin为A，哈希的begin为B，A的实现是对B的调用，在A的参数是普通迭代器时，B也是普通迭代器，B的返回值也是普通迭代器，但A的返回值是const迭代器，所以这里需要用普通迭代器创建一个const迭代器的临时变量，这就用到之前写的拷贝构造函数了。

2.3Find 

wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw== 
iterator Find(const K&key)
{return _ht.Find(key);
}

注意事项： 

  •  此时也有从普通迭代器到const迭代器的转换 

2.4Insert

pair<iterator, bool> Insert(const K& key)
{return _ht.Insert(key);
}

注意事项： 

  1. 函数形参类型是K
  2. 此时也有从普通迭代器到const迭代器的转换

 2.5Erase

bool Erase(const K& key)
{return _ht.Erase(key);
}

三、unordered_map

unordered_map和unordered_set的实现有众多相似之处，

3.1 成员变量与仿函数

template<class K,class V,class HF=HashFunc<K>>
class unordered_map
{struct MapKeyOfT
{const K& operator()(const pair<K, V>&kv){return kv.first;}};
protected:HashTable<K, pair<const K, V>, MapKeyOfT, HF> _ht;
};

注意事项：

  • 1.这里节点存的数据类型是pair<K,V>,我们的MapKeyOfT作用是返回其中的键值key 
  • 2.哈希函数不是固定的，可以根据需求自己进行实现并传到给定模板参数中

3.2 begin和end

typedef typename HashTable<K, pair<K,V>, MapKeyOfT, HF>::iterator iterator;
typedef typename HashTable<K, pair<K,V>, MapKeyOfT, HF>::const_iterator const_iterator;
iterator begin()
{return _ht.begin();
}
const_iterator begin()const
{return _ht.begin();
}
iterator end()
{return _ht.end();
}
const_iterator end()const
{return _ht.end();
}

注意事项：

  1. 加上typename关键字，编译器才能识别类型
  2. unordered_map不允许修改key，故普通迭代器和const的pair中的K都要加上const修饰，但是允许修改存储的data，所以普通和const迭代器一一对应(好好想想这点map和set的处理差异)

3.3 find

iterator Find(const K& key)
{return _ht.Find(key);
}

3.4Insert

	pair<iterator, bool> Insert(const pair<const K, V>& kv){return _ht.Insert(kv);}

注意事项：

  • 形参类型是键值对而不是键值

3.5 operator[ ]

V& operator[](const& K key)
{return (*(_ht.Insert(make_pair(key, V()))).first).second;
}
//或者你也可以这么写
V& operator[](const K& key)
{pair<iterator, bool> cur = insert(make_pair(key, V()));return cur.first->second;
}

注意事项：

  1.  利用operator[]进行插入和修改操作是很方便的，所以要学会灵活运用哦 
  2. 返回值是value的引用，我们可以直接进行修改 

3.6 Erase 

bool Erase(const K& key)
{return _ht.Erase(key);
}

 

 如果你对该系列文章有兴趣的话不妨点个关注哦，我会持续更新相关博客的

🥰创作不易，你的支持对我最大的鼓励🥰

🪐~ 点赞收藏＋关注 ~🪐

 

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

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

相关文章

烧坏两块单片机，不知道原因？

烧坏两块单片机，不知道原因？

没有看你的原理图&#xff0c;以下是造成烧毁芯片的几个环节&#xff1a; 1. 最大的可能性是你的单片机电机控制输出与电机驱动电路没有隔离。 我的经验&#xff0c;使用STM32控制电机&#xff0c;无论是直流电机脉宽调制&#xff0c;还是步进电机控制&#xff0c;控制电路与…
阅读更多...
Ubuntu 20.04.06 PCL C++学习记录（十六）

Ubuntu 20.04.06 PCL C++学习记录（十六）

[TOC]PCL中点云分割模块的学习 学习背景 参考书籍&#xff1a;《点云库PCL从入门到精通》以及官方代码PCL官方代码链接,&#xff0c;PCL版本为1.10.0&#xff0c;CMake版本为3.16 学习内容 用一组点云数据做简单的平面的分割 源代码及所用函数 源代码 #include<iostr…
阅读更多...
机器学习笔记 - 深度学习遇到超大图像怎么办？使用 xT 对极大图像进行建模论文简读

机器学习笔记 - 深度学习遇到超大图像怎么办？使用 xT 对极大图像进行建模论文简读

作为计算机视觉研究人员，在处理大图像时，避免不了受到硬件的限制，毕竟大图像已经不再罕见，手机的相机和绕地球运行的卫星上的相机可以拍摄如此超大的照片，遇到超大图像的时候，我们当前最好的模型和硬件都会达到极限。 所以通常我们在处理大图像时会做出两个次优选择之一：…
阅读更多...
【频繁模式挖掘】FP-Tree算法（附Python实现）

【频繁模式挖掘】FP-Tree算法（附Python实现）

一、实验内容简介 该实验主要使用频繁模式和关联规则进行数据挖掘&#xff0c;在已经使用过Apriori算法挖掘频繁模式后&#xff0c;这次使用FP-tree算法来编写和设计程序&#xff0c;依然使用不同规模的数据集来检验效果&#xff0c;最后分析和探讨实验结果&#xff0c;看其是…
阅读更多...
微服务架构下，如何通过弱依赖原则保障系统高可用？

微服务架构下，如何通过弱依赖原则保障系统高可用？

前言 当我初次接触高可用这个概念的时候&#xff0c;对高可用的【少依赖原则】和【弱依赖原则】的边界感模糊&#xff0c;甚至有些“傻傻分不清楚”。这两个原则都关注降低模块之间的依赖关系&#xff0c;但它们之间的确存在某些差异。 那么&#xff0c;「少依赖原则」和「弱…
阅读更多...
15.队列集

15.队列集

1.简介 在使用队列进行任务之间的“沟通交流”时&#xff0c;一个队列只允许任务间传递的消息为同一种数据类型&#xff0c;如果需要在任务间传递不同数据类型的消息时&#xff0c;那么就可以使用队列集。FreeRTOS提供的队列集功能可以对多个队列进行“监听”&#xff0c;只要…
阅读更多...
Unity类银河恶魔城学习记录12-4 p126 Item Tooltip源代码

Unity类银河恶魔城学习记录12-4 p126 Item Tooltip源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili UI.cs using System.Collections; using System.Collections.Generic; usi…
阅读更多...
xilinx AXI CAN驱动开发

xilinx AXI CAN驱动开发

CAN收发方案有很多&#xff0c;常见的解决方案通过是采用CAN收发芯片&#xff0c;例如最常用的SJA1000,xilinx直接将CAN协议栈用纯逻辑实现&#xff0c;AXI CAN是其中一种&#xff1b; 通过这种方式硬件上只需外接一个PHY芯片即可 上图加了一个电平转换芯片 软件设计方面&…
阅读更多...
Scala大数据开发

Scala大数据开发

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl Scala简述 在此&#xff0c;简要介绍 Scala 的基本信息和情况。 Scala释义 Scala 源自于英语单词scalable&#xff0c;表示可伸缩的、可扩展的含义。 Scala作者 Scala编…
阅读更多...
【考研数学】张宇《1000题》刷不动，做不下来怎么办❓

【考研数学】张宇《1000题》刷不动，做不下来怎么办❓

学长肯定是用着效果不错才给你推荐的&#xff0c;但是习题册有很多&#xff0c;各自有不同的风格&#xff0c;1000题适不适合你的情况是你要考虑的点。 选书还是要结合自身的情况&#xff0c;如果当前用着不错的话&#xff0c;继续完全没有问题&#xff0c;核心就是要从自身的…
阅读更多...
IT外包服务：企业数据资产化加速利器

IT外包服务：企业数据资产化加速利器

随着数字化时代的兴起&#xff0c;数据成为企业最为重要的资源之一。数据驱动创新对于企业的竞争力和可持续发展至关重要。在这一进程中&#xff0c;IT外包服务发挥着关键作用&#xff0c;加速企业数据资产化进程&#xff0c;为企业提供了重要支持。 首先&#xff0c;IT外包服务…
阅读更多...
【学习心得】Python中的queue模块使用

【学习心得】Python中的queue模块使用

一、Queue模块的知识点思维导图 二、Queue模块常用函数介绍 queue模块是内置的&#xff0c;不需要安装直接导入就可以了。 &#xff08;1&#xff09;创建一个Queue对象 import queue# 创建一个队列实例 q queue.Queue(maxsize20) # 可选参数&#xff0c;默认为无限大&am…
阅读更多...
基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】

基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】

基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展&#xff0c;计算机的应用日渐成熟&#xff0c;其强大的功能给人们留下深刻的印象&#xff0c;它已经应用到了人类社会的各个层次的领域&#xff0c;发挥着重要的不可替换的作用。信息管理作为计算…
阅读更多...
【chrome扩展】简 Tab (SimpTab)‘每日一句名言’样式

【chrome扩展】简 Tab (SimpTab)‘每日一句名言’样式

背景&#xff1a;最初参考“每日诗词”发现总是那几句&#xff0c;可以更换API接口完成“每日一句名言” 声明&#xff1a;本人不会ajax及ccs样式&#xff0c;非专业人士&#xff0c;借助CHATGPT代码生成完成。请友善交流。 每一句名言API: "https://api.xygeng.cn/open…
阅读更多...
libVLC 提取视频帧

libVLC 提取视频帧

在前面的文章中&#xff0c;我们使用libvlc_media_player_set_hwnd设置了视频的显示的窗口。 libvlc_media_player_set_hwnd(vlc_mediaPlayer, (void *)ui.widgetShow->winId()); 如果我们想要提取每一帧数据&#xff0c;将数据保存到本地&#xff0c;该如何操作呢&#x…
阅读更多...
OPC UA遇见chatGPT

OPC UA遇见chatGPT

最近opc 基金会将召开一个会议&#xff0c;主题是”OPC UA meets IT“。由此可见&#xff0c;工业自动化行业也开始研究和评估chatGPT带来的影响了。 本文谈谈本人对OPC UA 与chatGPT结合的初步实验和思考。 构建OPC UA 信息模型 chatGPT 的确非常强大了&#xff0c;使用自然…
阅读更多...
用户登录时md5加密源码解析

用户登录时md5加密源码解析

首先&#xff0c;在登录的时候&#xff0c;将页面提交的密码password加密处理&#xff0c;即password DigestUtils.md5DigestAsHex(password.getBytes()); 接着按ctrl鼠标左键&#xff0c;进入md5DigestAsHex函数中进行查看&#xff1a; 可以发现&#xff0c;md5DigestAsHex函…
阅读更多...
Mysql底层原理六：InnoDB 数据页结构

Mysql底层原理六：InnoDB 数据页结构

1.行格式 1.1 Compact行格式 1.1.1 示意图 1.1.2 准备一下 1&#xff09;建表 mysql> CREATE TABLE record_format_demo (-> c1 VARCHAR(10),-> c2 VARCHAR(10) NOT NULL,-> c3 CHAR(10),-> c4 VARCHAR(10)-> ) CHARSETascii ROW_FORMATCOM…
阅读更多...
积木-蓝桥每日真题

积木-蓝桥每日真题

0积木 - 蓝桥云课 (lanqiao.cn) 题目描述 小明用积木搭了一个城堡。 为了方便&#xff0c;小明在搭的时候用的是一样大小的正方体积木&#xff0c;搭在了一个n行m列的方格图上&#xff0c;每个积木正好占据方格图的一个小方格。 当然&#xff0c;小明的城堡并不是平面的&#x…
阅读更多...
Discord注册教程：Discord刚注册就被封怎么办？附申诉教程！

Discord注册教程：Discord刚注册就被封怎么办？附申诉教程！

Discord如今在海外社交媒体平台中迅速崛起&#xff0c;许多社交媒体营销人员也纷纷利用其社群特性进行推广&#xff0c;Discord注册也就成为社媒营销人员必经之路。然而&#xff0c;很多人注册Discord账号时常常会想&#xff1a;“在国内使用Discord会封号吗&#xff1f;”事实…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023