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

unordered_map/set的哈希封装

【C++笔记】unordered_map/set的哈希封装

🔥个人主页大白的编程日记

🔥专栏C++笔记


文章目录

  • 【C++笔记】unordered_map/set的哈希封装
    • 前言
    • 一. 源码及框架分析
    • 二.迭代器
    • 三.operator[]
    • 四.使用哈希表封装unordered_map/set
    • 后言

前言

哈喽,各位小伙伴大家好!上期我们讲了哈希表的底层实现。今天我们来讲一下unordered_map/set的哈希封装。话不多说,我们进入正题!向大厂冲锋
在这里插入图片描述

一. 源码及框架分析

SGI-STL30版本源代码中没有unordered_map和unordered_set,SGI-STL30版本是C++11之前的STL版本,这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表,只容器的名字是hash_map和hash_set,他是作为非标准的容器出现的,非标准是指非C++标准规定必须实现的,源代码在
hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中

hash_map和hash_set的实现结构框架核心部分截取出来如下:

// stl_hash_set
template <class Value, class HashFcn = hash<Value>,class EqualKey = equal_to<Value>,class Alloc = alloc>
class hash_set
{
private:typedef hashtable<Value, Value, HashFcn, identity<Value>,EqualKey, Alloc> ht;ht rep;
public:typedef typename ht::key_type key_type;typedef typename ht::value_type value_type;typedef typename ht::hasher hasher;typedef typename ht::key_equal key_equal;typedef typename ht::const_iterator iterator;typedef typename ht::const_iterator const_iterator;hasher hash_funct() const { return rep.hash_funct(); }key_equal key_eq() const { return rep.key_eq(); }
};
// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>,class EqualKey = equal_to<Key>,class Alloc = alloc>
class hash_map
{
private:typedef hashtable<pair<const Key, T>, Key, HashFcn,select1st<pair<const Key, T> >, EqualKey, Alloc> ht;ht rep;
public:typedef typename ht::key_type key_type;typedef T data_type;typedef T mapped_type;typedef typename ht::value_type value_type;typedef typename ht::hasher hasher;typedef typename ht::key_equal key_equal;typedef typename ht::iterator iterator;typedef typename ht::const_iterator const_iterator;
};
// stl_hashtable.h
template <class Value, class Key, class HashFcn,class ExtractKey, class EqualKey,class Alloc>
class hashtable {
public:typedef Key key_type;typedef Value value_type;typedef HashFcn hasher;typedef EqualKey key_equal;
private:hasher hash;key_equal equals;ExtractKey get_key;typedef __hashtable_node<Value> node;vector<node*, Alloc> buckets;size_type num_elements;
public:typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,Alloc> iterator;pair<iterator, bool> insert_unique(const value_type& obj);const_iterator find(const key_type& key) const;
};
template <class Value>
struct __hashtable_node
{__hashtable_node* next;Value val;
};
  • 框架分析
    这里我们就不再画图分析了,通过源码可以看到,结构上hash_map和hash_set跟map和set的完全类似,复用同一个hashtable实现key和key/value结构,通过一个参数T来封装map和set,hash_set传给hash_table的是key,hash_map传给hash_table的是pair<const key, value>。通过仿函数取出T中的key。同时哈希表还要多传一个哈希函数的仿函数。

二.迭代器

  • iterator实现的大框架跟list的iterator思路是一致的,用⼀个类型封装结点的指针,再通过重载运算符实现,迭代器像指针⼀样访问的行为,要注意的是哈希表的迭代器是单向迭代器。
  • 这里的难点是operator++的实现。iterator中有⼀个指向结点的指针,如果当前桶下面还有结点,则结点的指针指向下⼀个结点即可。如果当前桶走完了,则需要想办法计算找到下⼀个桶。这里的难点是反而是结构设计的问题,参考上面的源码,我们可以看到iterator中除了有结点的指针,还有哈希表对象的指针,这样当前桶走完了,要计算下一个桶就相对容易多了,用key值计算出当前桶位置,依次往后找下⼀个不为空的桶即可。
  • begin()返回第⼀个不为空的桶中第⼀个节点指针构造的迭代器,这里end()返回迭代器可以用空表示。
  • unordered_set的iterator也不支持修改,我们把unordered_set的第⼆个模板参数改成const K即
    可, HashTable<K, const K, SetKeyOfT, Hash> _ht;
  • unordered_map的iterator不支持修改key但是可以修改value,我们把unordered_map的第二个模板参数pair的第⼀个参数改成const K即可, HashTable<K, pair<const K, V>,MapKeyOfT, Hash> _ht;

三.operator[]

unoredered_map实现operator[]主要是通过insert支持。
通过insert返回的pair中的迭代器,再返回迭代器中数据即可

v& operator[](const k& key)
{pair<iterator, bool> ret = insert({ key,v()});return ret.first._node->_data.second;
}

四.使用哈希表封装unordered_map/set

  • 其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂⼀点,但是
    大框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K,还是pair<K, V>,
    那么insert内部进行插入时要用K对象转换成整形取模和K比较相等,因为pair的value不参与计算取模,且默认支持的是key和value⼀起比较相等,我们需要时的任何时候只需要比较K对象,所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT,然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象,再转换成整形取模和K比较相等,具体细节参考如下代码实现。
	template<class T>struct HashData{HashData<T>* _next;T _data;HashData(const T& key):_next(nullptr),_data(key){}};template<class k, class T, class KeyofT, class HashFun>class HashTable;//前置声明,解决相互依赖template<class k, class T, class Ref, class Ptr, class KeyofT, class HashFun>struct HashIterator{using node = HashData<T>;using self = HashIterator<k, T, Ref, Ptr, KeyofT, HashFun>;using ht = HashTable<k, T, KeyofT, HashFun>;const ht* _ht;node* _node;HashIterator(const ht* const& HT,node* node):_ht(HT), _node(node){}Ref operator*(){return _node->_data;}Ptr operator&(){return &_node->_data;}bool operator==(const self& tmp) const{return _node == tmp._node;}bool operator!=(const self& tmp) const{return _node != tmp._node;}self& operator++(){KeyofT kot;HashFun hash;if (_node->_next){_node = _node->_next;}else{size_t hash0 = hash(kot(_node->_data)) % _ht->_table.size();hash0++;while (hash0<_ht->_table.size()){if (_ht->_table[hash0]){break;}else{hash0++;}}if (hash0 == _ht->_table.size()){_node = nullptr;}else{_node = _ht->_table[hash0];}}return *this;}};template<class k, class T, class KeyofT, class HashFun>class HashTable{template<class k, class T, class Ref, class Ptr, class KeyofT, class HashFun>friend struct HashIterator;//友元声明public:HashTable():_table(__stl_next_prime(0)), _n(0){}using node = HashData<T>;using Iterator = HashIterator<k, T, T&, T*, KeyofT, HashFun>;using Const_Iterator=HashIterator<k, T, const T&, const T*, KeyofT, HashFun>;Iterator  End(){return Iterator(this, nullptr);}Iterator  Begin(){for (int i = 0; i < _table.size(); i++){if (_table[i]){return Iterator(this, _table[i]);}}return End();}Const_Iterator End() const{return Const_Iterator(this, nullptr);}Const_Iterator Begin() const{for (int i = 0; i < _table.size(); i++){if (_table[i]){return Const_Iterator(this, _table[i]);}}return End();}pair<Iterator,bool> Insert(const T& kv){HashFun hash;KeyofT kot;Iterator it = Find(kot(kv));if (it!=End()){return { it,false };}if (_n * 10 / _table.size() >= 7){vector<node*> newtable;newtable.resize(__stl_next_prime(newtable.size() + 1));for (auto& x : _table){node* cur = x;x = nullptr;while (cur){size_t hash0 = hash(kot(cur->_data)) % newtable.size();node* next = cur->_next;cur->_next=newtable[hash0];newtable[hash0] = cur;cur = next;}}_table.swap(newtable);}size_t hash0 = hash(kot(kv)) % _table.size();node* cur = new node(kv);cur->_next = _table[hash0];_table[hash0] = cur;_n++;return { Iterator(this,cur),true};}Iterator Find(const k& key){HashFun hash;KeyofT kot;size_t hash0 = hash(key) % _table.size();node* cur = _table[hash0];while (cur){if (kot(cur->_data) == key){return Iterator(this, cur);}cur = cur->_next;}return End();}bool Erase(const k& key){HashFun hash;KeyofT kot;size_t hash0 = hash(key) % _table.size();node* cur = _table[hash0];node* pre = nullptr;while (cur){if (kot(cur->_data) == key){if (cur == _table[hash0]){_table[hash0] = cur->_next;}else{pre->_next = cur->_next;}return true;}else{pre = cur;cur = cur->_next;}}return false;}private:vector<node*> _table;size_t _n;};


后言

这就是unordered_map/set的哈希封装。大家自己好好消化!今天就分享到这!感谢各位的耐心垂阅!咱们下期见!拜拜~

相关文章:

unordered_map/set的哈希封装

【C笔记】unordered_map/set的哈希封装 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;C笔记 文章目录 【C笔记】unordered_map/set的哈希封装前言一. 源码及框架分析二.迭代器三.operator[]四.使用哈希表封装unordered_map/set后言 前言 哈…...

机器学习专业毕设选题推荐合集 人工智能

目录 前言 毕设选题 开题指导建议 更多精选选题 选题帮助 最后 前言 大家好,这里是海浪学长毕设专题! 大四是整个大学期间最忙碌的时光&#xff0c;一边要忙着准备考研、考公、考教资或者实习为毕业后面临的升学就业做准备,一边要为毕业设计耗费大量精力。学长给大家整理…...

软件工程导论三级项目报告--《软件工程》课程网站

《软件工程》课程网站 摘要 本文详细介绍了《软件工程》课程网站的设计与实现方案&#xff0c;包括可行性分析、需求分析、总体设计、详细设计、测试用例。首先&#xff0c;通过可行性分析从各方面确认了该工程的可实现性&#xff0c;接着需求分析明确了系统的目标用户群和功能…...

物联网领域的MQTT协议,优势和应用场景

MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;作为轻量级发布/订阅协议&#xff0c;凭借其低带宽消耗、低功耗与高扩展性&#xff0c;已成为物联网通信的事实标准。其核心优势包括&#xff1a;基于TCP/IP的异步通信机制、支持QoS&#xff08;服务质量&…...

缓存类为啥使用 unordered_map 而不是 map

性能考虑&#xff1a; std::unordered_map 是基于哈希表实现的&#xff0c;而 std::map 是基于红黑树实现的。对于查找操作&#xff0c;std::unordered_map 的平均查找时间复杂度是 O ( 1 ) O(1) O(1)&#xff0c;而 std::map 的查找时间复杂度是 O ( l o g n ) O(log n) O(l…...

产品经理的人工智能课 02 - 自然语言处理

产品经理的人工智能课 02 - 自然语言处理 1 自然语言处理是什么2 一个 NLP 算法的例子——n-gram 模型3 预处理与重要概念3.1 分词 Token3.2 词向量化表示与 Word2Vec 4 与大语言模型的交互过程参考链接 大语言模型&#xff08;Large Language Models, LLMs&#xff09;是自然语…...

2024年MySQL 下载、安装及启动停止教程(非常详细),涉及命令行net start mysql80提示发生系统错误5的解决方案

一、安装包下载 官方网址&#xff1a; https://www.mysql.com/ MySQL 官方提供了两种不同的版本&#xff1a; 1.社区版本&#xff08; MySQL Community Server &#xff09; &#xff1a;免费&#xff0c; 但MySQL 不提供任何技术支持 2.商业版本&#xff08; MySQL Enterp…...

19.[前端开发]Day19-王者荣项目耀实战(二)

01_(掌握)王者荣耀-main-banner展示实现 完整代码 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewpor…...

lmk内存压力测试工具mem-pressure源码剖析

背景&#xff1a; android系统开发过程中&#xff0c;经常会遇到一些low memory kill的问题&#xff0c;在分析这些系统低内存导致被杀问题时候&#xff0c;经常因为不好复现而成为一个比较烦恼的阻碍。因为这种低内存问题本身就不属于一种功能操作类型的问题&#xff0c;属于…...

企业四要素如何用Java进行调用

一、什么是企业四要素&#xff1f; 企业四要素是在企业三要素&#xff08;企业名称、统一社会信用代码、法定代表人姓名&#xff09;的基础上&#xff0c;增加了一个关键要素&#xff0c;通常是企业注册号或企业银行账户信息。这种接口主要用于更全面的企业信息验证&#xff0c…...

修剪二叉搜索树(力扣669)

这道题还是比较复杂&#xff0c;在递归上与之前写过的二叉树的题目都有所不同。如果当前递归到的子树的父节点不在范围中&#xff0c;我们根据节点数值的大小选择进行左递归还是右递归。为什么找到了不满足要求的节点之后&#xff0c;还要进行递归呢&#xff1f;因为该不满足要…...

一款由 .NET 官方团队开源的电子商务系统 - eShop

项目介绍 eShop是一款由.NET官方开源的&#xff0c;基于.NET Aspire构建的用于参考学习的服务架构电子商务系统&#xff0c;旨在展示如何利用.NET框架及其相关技术栈构建一个现代化的电子商务网站。该项目采用服务架构&#xff0c;将应用程序分解为多个独立的服务&#xff0c;…...

论最新技术编程类有什么,值得关注的点有什么呢?

在2025年的编程领域,新技术层出不穷。编程语言方面,Zig作为新一代系统级编程语言,凭借无隐藏控制流、出色的优化性能以及良好的C语言兼容性,被视作C语言强有力的替代者;Rust的应用范围不断拓展,在系统开发和Web后端开发中表现亮眼,其“零成本抽象”特性在保障内存安全的…...

Java入门进阶

文章目录 1、常用API 1.1、Math1.2、System1.3、Object1.4、Arrays1.5、基本类型包装类 1.5.1、基本类型包装类概述1.5.2、Integer1.5.3、int和String相互转换1.5.4、自动装箱和拆箱 1.6、日期类 1.6.1、Date类1.6.2、SimpleDateFormat类 1.6.2.1、格式化&#xff08;从Date到…...

Java并发编程面试题:ThreadLocal(8题)

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;精通Java编…...

Zabbix7.0安装(Ubuntu24.04+LNMP)

1.选择版本 下载Zabbix 2.安装虚拟机 这里选择在Ubuntu24.04上安装Zabbix. 安装链接https://blog.csdn.net/weixin_58189050/article/details/145446065 配置源 vim /etc/apt/sources.list deb https://mirrors.aliyun.com/ubuntu/ noble main restricted universe multive…...

从 0 到 1 构建数仓之DWD层

在企业数字化转型进程中&#xff0c;数据仓库的建设至关重要&#xff0c;而 DWD 层&#xff08;明细粒度事实层&#xff09;作为数据仓库的核心支撑层&#xff0c;其搭建质量直接影响企业数据的分析价值与决策效率。本文将结合实际案例与行业经验&#xff0c;详细阐述企业如何从…...

S4 HANA手工记账Tax Payable – FB41

本文主要介绍在S4 HANA OP中手工记账Tax Payable – FB41。具体请参照如下内容&#xff1a; 手工记账Tax Payable – FB41 该事务代码用于手工处理税码统驭科目的记账&#xff0c;一般税码科目需要设置为只能自动记账&#xff0c;因此无法手工对税码统驭科目记账&#xff0c;但…...

【自然语言处理(NLP)】NLP实战:IMDB影评情感分析项目

文章目录 介绍IMDB影评情感分析项目数据集项目实现1. 导包2. 加载IMDB数据3. 查看部分数据4. 分词5. 加载数据整合6. 构建模型7. 词嵌入8. 初始化模型和权重9. glove词向量10. 训练和评估11. 预测 个人主页&#xff1a;道友老李 欢迎加入社区&#xff1a;道友老李的学习社区 介…...

DIY Shell:探秘进程构建与命令解析的核心原理

个人主页&#xff1a;chian-ocean 文章专栏-Linux 前言&#xff1a; Shell&#xff08;外壳&#xff09;是一个操作系统的用户界面&#xff0c;它提供了一种方式&#xff0c;使得用户能够与操作系统进行交互。Shell 是用户与操作系统之间的桥梁&#xff0c;允许用户通过命令行…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

Python第七周作业

Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt&#xff0c;并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径&#xff0c;并创建logs目录&#xff08;若不存在&#xff09; 3.递归遍历目录data&#xff0c;输出所有.csv文件的路径…...

Element-Plus:popconfirm与tooltip一起使用不生效?

你们好&#xff0c;我是金金金。 场景 我正在使用Element-plus组件库当中的el-popconfirm和el-tooltip&#xff0c;产品要求是两个需要结合一起使用&#xff0c;也就是鼠标悬浮上去有提示文字&#xff0c;并且点击之后需要出现气泡确认框 代码 <el-popconfirm title"是…...