面试之快速学习STL-无序关联式容器
- 和关联式容器一样,无序容器也使用键值对(pair 类型)的方式存储数据。不过,本教程将二者分开进行讲解,因为它们有本质上的不同:
关联式容器的底层实现采用的树存储结构,更确切的说是红黑树结构;
无序容器的底层实现采用的是哈希表的存储结构。 - C++ STL 底层采用哈希表实现无序容器时,会将所有数据存储到一整块连续的内存空间中,并且当数据存储位置发生冲突时,解决方法选用的是“链地址法”(又称“开链法”)
- 基于底层实现采用了不同的数据结构,因此和关联式容器相比,无序容器具有以下 2 个特点:
a. 无序容器内部存储的键值对是无序的,各键值对的存储位置取决于该键值对中的键,
和关联式容器相比,无序容器擅长通过指定键查找对应的值(平均时间复杂度为 O(1))
b. 但对于使用迭代器遍历容器中存储的元素,无序容器的执行效率则不如关联式容器。
unordered_map容器
模版
template
< class Key,class T,class Hash = hash<Key>, //容器内部存储键值对所用的哈希函数class Alloc = allocator<pair<const Key, T>> //判断各个键值对键相同的规则,默认情况下,使用 STL 标准库中提供的 equal_to<key> 规则,该规则仅支持可直接用 == 运算符做比较的数据类型。
>
std::unordered_map<std::string, std::string> umap;umap.emplace("Python教程","http://c.biancheng.net/python/");umap.emplace("Java教程", "http://c.biancheng.net/java/");umap.emplace("Linux教程", "http://c.biancheng.net/linux/");//遍历for(auto it = umap.begin(); it != umap.end(); ++it) {std::cout << it->first << " " << it->second << std::endl;}/*Linux教程 http://c.biancheng.net/linux/Java教程 http://c.biancheng.net/java/Python教程 http://c.biancheng.net/python/*/
这些内容都比较无聊,看点别的
STL无序容器底层实现原理(深度剖析)
- C++ STL 标准库中,不仅是 unordered_map 容器,所有无序容器的底层实现都采用的是哈希表存储结构。更准确地说,是用“链地址法”(又称“开链法”)解决数据存储位置发生冲突的哈希表,整个存储结构如图 :
- 其中,Pi 表示存储的各个键值对。
- 可以看到,当使用无序容器存储键值对时,会先申请一整块连续的存储空间,但此空间并不用来直接存储键值对,而是存储各个链表的头指针,各键值对真正的存储位置是各个链表的节点。
- TL 标准库通常选用 vector 容器存储各个链表的头指针。有意思~
- 不仅如此,在 C++ STL 标准库中,将图 1 中的各个链表称为桶(bucket),每个桶都有自己的编号(从 0 开始)。当有新键值对存储到无序容器中时,整个存储过程分为如下几步:
- 将该键值对中键的值带入设计好的哈希函数,会得到一个哈希值(一个整数,用 H 表示);
- 将 H 和无序容器拥有桶的数量 n 做整除运算(即 H % n),该结果即表示应将此键值对存储到的桶的编号;
- 建立一个新节点存储此键值对,同时将该节点链接到相应编号的桶上。
负载因子(load factor)
负载因子 = 容器存储的总键值对 / 桶数
- 默认情况下,无序容器的最大负载因子为 1.0。如果操作无序容器过程中,使得最大复杂因子超过了默认值,则容器会自动增加桶数,并重新进行哈希,以此来减小负载因子的值。
- 需要注意的是,此过程会导致容器迭代器失效,但指向单个键值对的引用或者指针仍然有效。
- 这也就解释了,为什么我们在操作无序容器过程中,键值对的存储顺序有时会“莫名”的发生变动。
成员方法 功能
bucket_count() 返回当前容器底层存储键值对时,使用桶的数量。
max_bucket_count() 返回当前系统中,unordered_map 容器底层最多可以使用多少个桶。
bucket_size(n) 返回第 n 个桶中存储键值对的数量。
bucket(key) 返回以 key 为键的键值对所在桶的编号。
load_factor() 返回 unordered_map 容器中当前的负载因子。
max_load_factor() 返回或者设置当前 unordered_map 容器的最大负载因子。
rehash(n) 尝试重新调整桶的数量为等于或大于 n 的值。如果 n 大于当前容器使用的桶数,则该方法会是容器重新哈希,该容器新的桶数将等于或大于 n。反之,如果 n 的值小于当前容器使用的桶数,则调用此方法可能没有任何作用。
reserve(n) 将容器使用的桶数(bucket_count() 方法的返回值)设置为最适合存储 n 个元素的桶数。
hash_function() 返回当前容器使用的哈希函数对象。
//创建空的umap1std::unordered_map<std::string, std::string> umap1;std::cout << "umap初始捅数 :" << umap1.bucket_count()<<std::endl;std::cout << "umap初始负载因子 :" << umap1.load_factor() << std::endl;std::cout << "umap 最大负载因子 : " << umap1.max_load_factor() << std::endl;/*umap初始捅数 :0umap初始负载因子 :0umap 最大负载因子 : 1*///设置 umap 使用最适合存储 9 个键值对的桶数umap1.reserve(9);std::cout << "umap新捅数 :" << umap1.bucket_count()<<std::endl;std::cout << "umap新负载因子 :" << umap1.load_factor() << std::endl;/*umap新捅数 :11umap新负载因子 :0*/umap1["Python教程"] = "http://c.biancheng.net/python/";umap1["Java教程"] = "http://c.biancheng.net/java/";umap1["Linux教程"] = "http://c.biancheng.net/linux/";std::cout << "umap新捅数 :" << umap1.bucket_count()<<std::endl;std::cout << "umap新负载因子 :" << umap1.load_factor() << std::endl;//调用 bucket() 获取指定键值对位于桶的编号std::cout << "以\"Python教程\"为键的键值对,位于桶的编号为:" << umap1.bucket("Python教程") << std::endl;//自行计算某键值对位于哪个桶auto fn = umap1.hash_function();std::cout << "计算以\"Python教程\"为键的键值对,位于桶的编号为:" << fn("Python教程") % (umap1.bucket_count()) << std::endl;
关于哈希表
- 常用的哈希函数的构造方法有 6 种:直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。
- 直接定址法
H(key)= key 或者 H(key)=a * key + b
-
数字分析法: 果关键字由多位字符或者数字组成,就可以考虑抽取其中的 2 位或者多位作为该关键字对应的哈希地址,在取法上尽量选择变化较多的位,避免冲突发生。
-
平方取中法是对关键字做平方操作,取中间得几位作为哈希地址。此方法也是比较常用的构造哈希函数的方法。
例如关键字序列为{421,423,436},对各个关键字进行平方后的结果为{177241,178929,190096},则可以取中间的两位{72,89,00}作为其哈希地址。
- 折叠法 是将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。此方法适合关键字位数较多的情况。
- 除留余数法:若已知整个哈希表的最大长度 m,可以取一个不大于 m 的数 p,然后对该关键字 key 做取余运算,即:
H(key)= key % p。
处理冲突的方法
- 开放定址法
H(key)=(H(key)+ d)MOD m(其中 m 为哈希表的表长,d 为一个增量)
- 当得出的哈希地址产生冲突时,选取以下 3 种方法中的一种获取 d 的值,然后继续计算,直到计算出的哈希地址不在冲突为止,这 3 种方法为:
- 线性探测法:d=1,2,3,…,m-1
- 二次探测法:d=12,-12,22,-22,32,…
- 伪随机数探测法:d=伪随机数
-
再哈希法
当通过哈希函数求得的哈希地址同其他关键字产生冲突时,使用另一个哈希函数计算,直到冲突不再发生。 -
链地址法
将所有产生冲突的关键字所对应的数据全部存储在同一个线性链表中。例如有一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79},其哈希函数为:H(key)=key MOD 13,使用链地址法所构建的哈希表如图 3 所示:
相关文章:

面试之快速学习STL-无序关联式容器
和关联式容器一样,无序容器也使用键值对(pair 类型)的方式存储数据。不过,本教程将二者分开进行讲解,因为它们有本质上的不同: 关联式容器的底层实现采用的树存储结构,更确切的说是红黑树结构&a…...

C++线程库
C线程库是C11新增的重要的技术之一,接下来来简单学习一下吧! thread类常用接口 函数名功能thread()构造一个线程对象,没有关联任何线程函数,即没有启动任何线程。thread(fn, args1, args2, ...)构造一个线程对象,并…...

一文看懂群晖 NAS 安装 Mysql 远程访问连接
文章目录 1. 安装Mysql2. 安装phpMyAdmin3. 修改User 表4. 本地测试连接5. 安装cpolar6. 配置公网访问地址7. 固定连接公网地址 群晖安装MySQL具有高效、安全、可靠、灵活等优势,可以为用户提供一个优秀的数据管理和分析环境。同时具有良好的硬件性能和稳定性&#…...

永久设置pip指定国内镜像源(windows内)
1.首先列出国内四个镜像源网站: 一、清华源 https://pypi.tuna.tsinghua.edu.cn/simple/ 二、阿里源 https://mirrors.aliyun.com/pypi/simple 三、中科大源 https://pypi.mirrors.ustc.edu.cn/simple/ 四、豆瓣源 http://pypi.douban.com/simple/ 2.一般下载所需要…...
【SA8295P 源码分析】27 - QNX Ethernet MAC 驱动 之 emac_tx_thread_handler 数据发送线程 源码分析
【SA8295P 源码分析】27 - QNX Ethernet MAC 驱动 之 emac_tx_thread_handler 数据发送线程 源码分析 系列文章汇总见:《【SA8295P 源码分析】00 - 系列文章链接汇总》 本文链接:《【SA8295P 源码分析】27 - QNX Ethernet MAC 驱动 之 emac_tx_thread_handler() 数据发送线程…...
爬虫抓取数据时显示超时,是代理IP质量不行?
很多人在做数据抓取的时候,会遇到显示超时了,然后就没有响应了。这是什么原因的?有的人回答是使用的代理IP质量不行,这种答案,对也不对。 数据抓取时,出现超时的原因时多方面影响的,主要分为目标…...

【管理运筹学】第 5 章 | 整数规划 (2,割平面法及 0-1 变量的特性)
文章目录 引言三、割平面法四、0-1 型整数规划4.1 0-1 变量的特性4.1.1 投资问题4.1.2 约束条件满足个数问题 写在最后 引言 前文我们介绍了整数规划的一种求解方法——分支定界法,可以求解纯整数和混合整数规划问题。现在我们来学习另一种整数规划求解方法——割平…...

Vscode详细安装教程
Vscode官网下载 官网地址:Download Visual Studio Code - Mac, Linux, Windows 通过链接可以直接跳转到下面的页面当中,支持的版本有Windows、Linux、Mac,可以选择适配自己电脑的版本,一般来说应该是Windows x64的。不要直接点W…...

法线矩阵推导
法线矩阵推导 https://zhuanlan.zhihu.com/p/72734738 https://juejin.cn/post/7113952418613690382 https://blog.csdn.net/wangjianxin97?typeblog 1、为什么需要法线矩阵 vec3 normalEyeSpace modelViewMatrix * normal;如果模型矩阵执行了非等比缩放, 顶点的改变会导致法…...

对容器、虚拟机和 Docker 的初学者友好介绍
一、说明 如果你是一个程序员或技术人员,你可能至少听说过Docker:一个有用的工具,用于在“容器”中打包,运输和运行应用程序。很难不这样做,这些天它得到了所有的关注 - 来自开发人员和系统管理员。即使是像谷歌、VMwa…...
linux部署clickhouse(单机)
一、下载安装 1.1、下载地址 阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区阿里巴巴开源镜像站,免费提供Linux镜像下载服务,拥有Ubuntu、CentOS、Deepin、MongoDB、Apache、Maven、Composer等多种开源软件镜像源,此外还提供域名解析DNS、…...
vue组件注册
组件注册分为全局注册和局部注册 全局注册 在 main.js 或者入口文件中 import { createApp } from vue; import MyComponent from ./components/MyComponent.vue;const app createApp();app.component(my-component, MyComponent);app.mount(#app); 我们首先通过createApp…...

day20 飞机大战射击游戏
有飞行物类 飞行 爆炸 的连环画, 飞行的背景图 , 子弹图, 还有游戏开始 暂停 结束 的画面图。 设计一个飞机大战的小游戏, 玩家用鼠标操作hero飞行机, 射出子弹杀死敌机,小蜜蜂。 敌机可以获得分数&…...

iOS设计规范是什么?都有哪些具体规范
iOS设计规范是苹果为移动设备操作系统iOS制定的设计指南。iOS设计规范的制定保证了苹果应用在外观和操作上的一致性和可用性,从而提高了苹果界面设计的用户体验和应用程序的成功性。本文将从七个方面全面分析iOS设计规范。 1.iOS设计规范完整版分享 由「即时设计」…...

动手学深度学习-pytorch版本(二):线性神经网络
参考引用 动手学深度学习 1. 线性神经网络 神经网络的整个训练过程,包括: 定义简单的神经网络架构、数据处理、指定损失函数和如何训练模型。经典统计学习技术中的线性回归和 softmax 回归可以视为线性神经网络 1.1 线性回归 回归 (regression) 是能为一个或多个…...

Spark 图计算ONEID 进阶版
0、环境信息 本文采用阿里云maxcompute的spark环境为基础进行的,搭建本地spark环境参考搭建Windows开发环境_云原生大数据计算服务 MaxCompute-阿里云帮助中心 版本spark 2.4.5,maven版本大于3.8.4 ①配置pom依赖 详见2-1 ②添加运行jar包 ③添加配置信…...

Comparable和Comparator区别
Comparable和Comparator接口都是实现集合中元素的比较、排序的,众所周知,诸如Integer,double等基本数据类型,java可以对他们进行比较,而对于类的比较,需要人工定义比较用到的字段比较逻辑。总体来讲&#x…...
JAVA知识点梳理
我的博客:lcatake_flume,spark,zookeeper-CSDN博客 看不懂的话进去看看 1.Java的三个版本 JAVASE 基本 JAVAME 微缩 JAVAEE 标准 3.java的特点 面向对象 跨平台:jvm将java文件转变为字节码文件(.class)在多个系统中运 行字…...

[SWPUCTF 2022 新生赛]ez_ez_php
这段代码是一个简单的PHP文件处理脚本。让我们逐行进行分析: error_reporting(0); - 这行代码设置了错误报告的级别为0,意味着不显示任何错误。 if (isset($_GET[file])) { - 这行代码检查是否存在一个名为"file"的GET参数。 if ( substr($_…...

GraphQL strawberry的使用回顾和体会
GraphQL vs RESTful 简单来说GraphQL 比起 RESTful 集成额外一些功能 出入参校验、序列化 (简化后端编程)自由可选的返回数据字段 (简化一些多余接口开发和沟通联调成本) 这些都是优点了。 开发效率在项目初期是很重要的,需要快速原型化。 但是后期稳定后&#…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...

图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...

html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...

R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...

自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...