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

【C++】unordered_map(set)

前言

C++中的unordered容器(例如std::unordered_set、std::unordered_map等)底层是基于**哈希表(Hash Table)**实现的。哈希表是一种通过哈希函数将元素映射到特定“桶(bucket)”的容器,提供快速的查找、插入和删除操作。

unordered系列的实现(基哈希桶)

哈希表的基本结构

哈希表的核心思想是**将元素的值(或键)通过哈希函数(Hash Function)映射到哈希表中的某个桶(bucket)。每个桶通常是一个链表或其他数据结构,用来处理冲突。当不同的元素通过哈希函数得到相同的哈希值时,会出现哈希冲突(Hash Collision),**冲突的元素会被存储在同一个桶内。

哈希表的关键组成部分有:

  1. 哈希表(Hash Table)
    unordered_map 和 unordered_set 底层使用哈希表来存储元素。
    哈希表的核心是一个数组,这个数组的每个位置被称为一个“桶”(bucket)。
    每个桶可以存储一个或多个元素,这些元素的键通过哈希函数映射到该桶中。
  2. 哈希函数(Hash Function)
    哈希函数负责将键值映射到哈希表中的某个桶。
    C++ 标准库允许用户提供自定义的哈希函数,默认情况下使用 std::hash 提供的哈希函数。
    哈希函数的好坏直接影响到哈希表的性能:一个好的哈希函数应当均匀分布键值,减少冲突。
  3. 冲突处理(Collision Handling)
    哈希冲突发生在不同的键被映射到同一个桶时。
    C++ 的 unordered_map 和 unordered_set 使用 开链法(Chaining) 处理冲突。
    在开链法中,每个桶内部实际上是一个链表或类似的结构,用于存储多个哈希冲突的元素。
    这意味着即使有冲突发生,元素也不会丢失,而是通过链表来管理这些冲突的元素。
  4. 负载因子和扩展(Load Factor and Rehashing)
    负载因子(Load Factor)定义为元素数量与桶数量的比值。当负载因子超过一个预设的阈值时,哈希表会进行扩展(即再散列 rehashing)。
    扩展通常意味着分配一个更大的桶数组,并重新计算每个元素的哈希值,然后将它们放入新的桶中。
    再散列的过程可以确保在负载因子较高时,哈希表的操作仍然是高效的。
  5. 迭代顺序
    因为哈希表的存储结构无序,unordered_map 和 unordered_set 的迭代顺序是未定义的。
    迭代顺序依赖于哈希函数和元素的插入顺序,以及哈希表的大小和当前负载因子。
  6. 时间复杂度
    在理想情况下(即哈希冲突少),unordered_map 和 unordered_set 的插入、查找、删除操作的时间复杂度是 O(1)。
    但在最坏情况下(大量冲突),这些操作的时间复杂度可能退化为 O(n)。

存储结构

  • 类似于链表,在顺序表中存储一个一个节点。
template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}
};
  • table:使用 std::vector 存储多个链表,每个链表代表一个桶,链表中的元素是映射到这个桶的所有元素。
  • 记录_n进行负载因子的储存
  • class KeyofT是作为仿函数是为了配合K型和KV结构适应的
template<class K,class T,class KeyofT,class HashFunc = defaultHashfunc<K>>
class HashTable
{public:...private:vector<Node*> _table;size_t _n = 0;
};

哈希函数

  1. 在函数的内容的不确定的时候进行返回。
  2. 针对string字符串的直接进行特模板化。
  3. 针对26字母有不同的组合,要进行字符串的哈希化处理,目的是针对哈希冲突 (本次采用 BKDR算法)参考:字符串哈希算法
template<class T>
struct defaultHashfunc
{size_t operator()(const T& data){return (size_t)data;}
};
//模板特化
template<>
struct defaultHashfunc<string>
{size_t operator()(const string& str){size_t hash = 0;for (auto& ch : str){hash *= 131;hash += ch;}return hash;}
};

unordered插入操作

  1. 哈希计算
    当你插入一个元素(比如在unordered_map中插入一个键值对),首先会调用哈希函数对键(key)进行哈希计算。这个哈希函数返回一个哈希值(通常是一个无符号整数类型,如std::size_t)。
    这个哈希值会被用来确定元素应该存储在哪个桶(bucket)中。桶的数量通常是哈希表当前容量的一个因子。

  2. 桶的选择
    哈希表根据哈希值和桶的数量来确定目标桶的位置。通常这是通过取模运算来完成的,即 hf(kot(data)) % _table.size()
    在这个位置上,哈希表要检查这个桶是否已经存在元素,如果存在,则进行冲突处理。

  3. 冲突处理
    如果目标桶已经有其他元素(即发生了哈希冲突),unordered_map unordered_set 通过 开链法(chaining) 进行处理。
    开链法意味着每个桶实际上包含一个链表或链表的类似结构。新元素将被添加到这个链表中。

  4. 元素存储
    如果目标桶为空,则直接将新元素存储在该桶中。
    如果目标桶不为空(发生冲突),则将元素追加到该桶的链表中。
    unordered_map 中,如果插入的键已经存在,则插入操作不会改变哈希表,而是更新该键对应的值。

  5. 负载因子与再散列(Rehashing)
    每次插入操作都会检查哈希表的负载因子(即元素数量与桶数量的比值)。
    如果负载因子超过了哈希表的最大负载因子(max_load_factor()),哈希表会自动扩展,增加桶的数量并重新分配所有元素到新的桶中。这就是所谓的再散列(rehashing)
    再散列过程中,所有元素都将被重新哈希和插入新的桶中,这样可以保证哈希表的高效性

pair<iterator,bool> insert(const T& data)
{KeyofT kot;HashFunc hf;iterator it = Find(kot(data));if (it != end()){return make_pair(it,false);}if (_n == _table.size()){size_t newsize = _table.size() * 2;vector<Node*> newtable;newtable.resize(newsize,nullptr);for (int i = 0; i < _table.size() ;i++){HashFunc hf;size_t hashi = 0;Node* cur = _table[i];while (cur){Node* next = cur->_next;hashi = hf(kot(cur->_data)) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}size_t hashi = hf(kot(data)) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return make_pair(iterator(newnode,this),true);
}

unordered删除操作

删除操作的底层流程

  1. 哈希计算
    对于基于键删除的操作(如 erase(const key_type& k)),首先会对给定的键 k 进行哈希计算,计算出哈希值。
    根据哈希值确定该键可能存储在哪个桶中。

  2. 查找元素
    哈希表在确定了桶的位置后,会在对应的桶(链表)中查找目标元素。
    如果找到匹配的元素,哈希表会进行删除操作;如果未找到,erase 返回 0,表示没有元素被删除。

  3. 删除元素
    删除元素时,需要从桶的链表中移除该元素,并处理相应的链表指针调整,以确保链表结构的完整性。
    如果该桶中的链表只有一个元素,删除该元素后,该桶变为空。
    如果链表中有多个元素,删除操作只影响指定元素,并将链表的前后元素连接起来。

bool Erase(const K& key)
{HashFunc hf;KeyofT kot;size_t hashi = hf(kot(key)) % _table.szie();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;
}

unordered查找操作

  1. 桶的选择
    根据哈希值确定桶的位置(索引),通常通过哈希值对桶的数量取模来实现,即 bucket_index = hash_value % bucket_count。
    定位到桶之后,开始在该桶的链表中查找目标元素。
  2. 遍历桶的链表
    如果目标桶不为空,查找操作会遍历桶中的链表,比较每个元素的键与目标键 k 是否相同。
    如果找到匹配的键,find() 方法返回指向该元素的迭代器。如果未找到,返回 end()。
iterator Find(const K& key)
{HashFunc hf;KeyofT kot;size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur,this);}cur = cur->_next;}return iterator(nullptr, this);
}

unordered迭代器

迭代器的结构

  • 迭代器的构建需要_node的节点和哈希表的指针。
  • 节点的指针是进行返回当前节点的值。
template<class K,class T,class Ptr,class Ref,class KeyofT, class HashFunc>
struct HashIterator
{typedef HashNode<T> Node;typedef HashIterator<K, T, Ptr, Ref ,KeyofT, HashFunc> Self;typedef HashIterator<K, T, T*, T&, KeyofT, HashFunc> iterator;Node* _node;const HashTable<K, T, KeyofT, HashFunc>* _pht;};

迭代器的特点

  • 在迭代器内需要写普通迭代器的拷贝构造(const迭代器的构造函数)
  • 在迭代器实例化不同的类型,这个函数作用是不一样的。
  • 这个的目的是为了解决set的insert返回值的需求,map返回pair<iterator,bool>,由于利用同于一个适配器,需要适应不同的容器。
HashIterator(const iterator& it):_node(it._node),_pht(it._pht)
{

迭代器自增

  • if判断当前桶的是否还存在剩余节点,存在返回下一个,不存在调整至下一个不为空的桶。
Self& operator++()
{if (_node->_next){_node = _node->_next;}else{KeyofT kot;HashFunc hf;size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();++hashi;while (hashi < _pht->_table.size()){if (_pht->_table[hashi]){_node = _pht->_table[hashi];return *this;}else{++hashi;}}_node = nullptr;}return *this;
}

迭代器其余结构

  • 重载 * 、重载 -> 、重载== !=
Ref operator*()
{return _node->_data;
}Ptr operator->()
{return &_node->_data;
}
bool operator!=(const Self& s)
{return _node != s._node;
}
bool operator==(const Self& s)
{return _node->_data == s._node;
}

迭代器的封装

  • begin()返回第一个储存数据的节点
  • end()返回空指针
iterator begin()
{ for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){if (cur){return iterator(cur, this);}}}return iterator(nullptr, this);
}
iterator end()
{return iterator(nullptr, this);
}

map和set的封装

map的set的仿函数

  • 仿函数传过去是在实例化的时候为了取到不同的结构下的值
struct mapofT
{const K& operator()(const pair<K, T>& kv){return kv.first;}
};struct setofT
{const K& operator()(const K& key){return key;}
};

map的set的插入

  • 由于map储存键值对,返回pair,set为了适应结构返回也是pair
  • set的返回进行再次接受,哈希桶底层利用iterator,在这里返回const需要进行构造
pair<iterator,bool> insert(const pair<K, T>& kv)
{return _ht.insert(kv);
}pair<const_iterator,bool> insert(const K& data)
{pair<typename HashTable<K, K, setofT>::const_iterator, bool> ret = _ht.insert(data);return make_pair(ret.first, ret.second);
}

map的operator[]

  • 采用insert进行返回,存在key返回当前迭代器,不存在插入这个值。
  • 整体这个函数放回该值的pair的second。
T& operator[](const K& key)
{pair<iterator, bool> ret = insert(make_pair(key, T()));return ret.first->second;
}

相关文章:

【C++】unordered_map(set)

前言 C中的unordered容器&#xff08;例如std::unordered_set、std::unordered_map等&#xff09;底层是基于**哈希表&#xff08;Hash Table&#xff09;**实现的。哈希表是一种通过哈希函数将元素映射到特定“桶&#xff08;bucket&#xff09;”的容器&#xff0c;提供快速的…...

HTML 盒模型

盒模型&#xff08;box model&#xff09; 简介&#xff1a;盒模型&#xff08;Box Model&#xff09;是CSS中一个非常重要的概念&#xff0c;它定义了元素在网页上的布局和尺寸。 组成&#xff1a;内容&#xff08;Content&#xff09;、内边距&#xff08;Padding&#xff…...

node.js npm 安装和安装create-next-app -windowsserver12

1、官网下载windows版本NODE.JS https://nodejs.org/dist/v20.17.0/node-v20.17.0-x64.msi 2、安装后增加两个文件夹目录node_global、node_cache npm config set prefix "C:\Program Files\nodejs\node_global" npm config set prefix "C:\Program Files\nod…...

Android13 展锐平台拨号中视频彩铃界面方向未与设备方向一致

背景&#xff1a;拨号中视频彩铃界面方向未与设备方向一致&#xff0c;要求视频彩铃界面方向与设备方向一致&#xff0c;修改视频彩铃显示的地方&#xff1b; 如图所示&#xff1a; 修改&#xff1a; packages/services/Telecomm/src/com/android/server/telecom/VideoProvid…...

为什么IP首部的源IP地址和目的IP地址不变而MAC层的源MAC地址和目的MAC地址变

IP首部的源IP地址和目的IP地址不变&#xff0c;而MAC层的源MAC地址和目的MAC地址变化的原因‌主要涉及到计算机网络中的分层结构和数据包传输过程。在OSI&#xff08;开放系统互联&#xff09;模型中&#xff0c;计算机网络被分为不同的层&#xff0c;每层都有其特定的功能。IP…...

Django 数据库配置以及字段设置详解

配置PostGre 要在 Django 中配置连接 PostgreSQL 数据库&#xff0c;并创建一个包含“使用人”和“车牌号”等字段的 Car 表 1. 配置 PostgreSQL 数据库连接 首先&#xff0c;在 Django 项目的 settings.py 中配置 PostgreSQL 连接。 修改 settings.py 文件&#xff1a; …...

C++ 左值右值引用梳理

C 左值右值引用梳理 左值与右值的区别 在参考资料上看到这样一句话 https://www.internalpointers.com/post/understanding-meaning-lvalues-and-rvalues-c In C an lvalue is something that points to a specific memory location. On the other hand, a rvalue is somethi…...

向量化技术在机器学习领域的深度实践与探索

向量化技术的魅力初现 在机器学习的广袤天地中&#xff0c;数据是驱动模型学习与进化的核心燃料。然而&#xff0c;面对海量、高维的数据&#xff0c;如何高效地进行处理与利用&#xff0c;成为了研究者们必须面对的问题。向量化技术应运而生&#xff0c;通过将文本、图像、音…...

RuoYi若依框架学习:多环境配置

在开发过程中&#xff0c;项目往往需要在不同的环境&#xff08;如开发、测试和生产&#xff09;中运行。RuoYi框架支持通过配置文件轻松实现多环境管理。以下是如何配置和使用多环境的技术分析。 1. 环境配置文件 RuoYi框架使用application-{profile}.yml文件来管理不同环境…...

Linux-RedHat7.4-服务器搭建FTP

Linux FTP 1、安装vsftpd和lftp&#xff1a; yum -y install vsftpd lftp ftp 2、创建用户&#xff1a; vsftpd提供了三种认证方式&#xff1a;本地用户、虚拟用户、匿名用户&#xff0c;本文介绍本地用户的认证方式。 注&#xff1a;本文创建的本地用户为只能访问ftp&…...

遍历递归数结构,修改里的disabled值

返回参数中新增字段 disabled,后端给的值为1和2, disabled1时&#xff0c;代表该节点需要置灰&#xff0c;不可选中 现在需要将disabled的值,改为布尔类型; 后端给的数结构是对象类型,tree接收数组类型; 先将对象类型的数据,遍历递归,修改里面的disabled值,最后再加[ ],改为…...

怎么通过AI大模型开发一个网站?

目录 一、提示词与AI输出 二、网站效果 以前不会代码开发&#xff0c;写网站是不可能的事情&#xff0c;现在有了AI&#xff0c;一切都有了可能。以下是我通过通义千问大模型开发的简单网站。 一、提示词与AI输出 提示词1 你是python程序员&#xff0c;我有一个大的需求&am…...

【Kubernetes】常见面试题汇总(四十)

目录 93. Kubelet 与 kubeproxy 作用。Kubeproxy 的三种代理模式和各自的原理以及它们的区别。 特别说明&#xff1a; 题目 1-68 属于【Kubernetes】的常规概念题&#xff0c;即 “ 汇总&#xff08;一&#xff09;~&#xff08;二十二&#xff09;” 。 题目 69-113 属…...

数据仓库-数据命名标准规范

一:主题域 1.1 业务主题域1.2 分析主题域1.3 数据域二: 词根 2.2 业务词根三:对象数据规范 3.1 表规范 3.1.1 数据装载周期3.1.2 数据装载方式3.1.3 表命名规范3.2.1 分区字段3.2.2 其他通用字段3.3 指标规范 3.3.1 时间修饰词3.3.2 常用度量3.3.2 指标命名3.4 ETL命名规范...

OCR识别系统 YOLOv8 +Paddle 方案落地

YOLOv8 PaddleOCR 技术方案落地 Yolov8相关文档Step 1 证件模型的训练Step 2 Yolov8进行图片推理Step 3 PaddleOCR进行识别Step 4 整合Yolov8 PaddleOCR 进行OCR Yolov8相关文档 《yolov8 官方网站》 《Yolov8 保姆级别安装》 Ultralytics YOLOv8 是一款尖端的、最先进的 (S…...

828华为云征文|部署去中心化网络的 AI 照片管理应用 PhotoPrism

828华为云征文&#xff5c;部署去中心化网络的 AI 照片管理应用 PhotoPrism 一、Flexus云服务器X实例介绍二、Flexus云服务器X实例配置2.1 重置密码2.2 服务器连接2.3 安全组配置2.4 Docker 环境搭建 三、Flexus云服务器X实例部署 PhotoPrism3.1 PhotoPrism 介绍3.2 PhotoPrism…...

【PAM】Linux登录认证限制

PAM&#xff08;Pluggable Authentication Modules&#xff0c;可插拔认证模块&#xff09;是一种灵活的认证框架&#xff0c;用于在 Linux 和其他类 Unix 系统上管理用户的身份验证。PAM 允许系统管理员通过配置不同的认证模块来定制应用程序和服务的认证方式&#xff0c;而不…...

Go语言Mutex的优化与TryLock机制解析

解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 Go语言中的Mutex优化与goroutine调度机制 Go语言的开发团队于2011年6月30日对Mutex进行了重大调整,这次调整主要目的是优化并发场景下的锁竞争,尤其是在多goroutine争抢同一把锁时的处理。这次优化不仅改进了锁…...

基于TSN的实时通信网络延迟评估技术

论文标题&#xff1a;A TSN-based Technique for Real-Time Latency Evaluation in Communication Networks 作者信息&#xff1a; Alberto Morato, Claudio Zunino, Manuel Cheminod, Stefano Vitturi&#xff0c;来自意大利国家研究委员会&#xff0c;CNR-IEIIT。电子邮件:…...

初识ZYNQ——FPGA学习笔记15

一、ZYNQ简介 ZYNQ&#xff1a;Zynq-7000 All Programmable SoC&#xff08;APSoC&#xff09;&#xff0c;赛灵思公司&#xff08;AMD Xilinx&#xff09;推出的新一代全可编程片上系统 PS&#xff1a;Processing System&#xff0c;处理系统 PL&#xff1a;Program Logic&…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...