从零带你底层实现unordered_map (1)
💯 博客内容:从零带你实现unordered_map
😀 作 者:陈大大陈
🚀 个人简介:一个正在努力学技术的准C++后端工程师,专注基础和实战分享 ,欢迎私信!
💖 欢迎大家:这里是CSDN,我总结知识和写笔记的地方,喜欢的话请三连,有问题请私信 😘 😘 😘
目录
超级容易踩坑的地方
unordered_map怎么实现
哈希冲突
开放寻址法
代码
unordered_map也就是哈希表,今天就来讲解它的用法。
unordered的意思是“无序”,这里强调了和map功能上的不同,因为map里面的东西是排好序的。
超级容易踩坑的地方
它是一个单向的迭代器。
为什么专门提到这个呢?因为这是我踩过坑的地方!!
单向迭代器压根就不能使用sort函数来排序!
std::unordered_map的迭代器类型是ForwardIterator,而不是sort函数要求的RandomAccessIterator,这里不符合。
我们要排序的话,还是将unordered_map里存的值,转存到vector<pair>里面。
然后我们再自定义一个排序方法,对vector<pair>进行排序。
可参考下面的代码:
class Solution {
public:struct comp{bool operator()(const pair<string,int>&p1,const pair<string,int>&p2){return p1.second>p2.second||(p1.second==p2.second&&p1.first<p2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> hash;for(auto &str:words) hash[str]++;vector<pair<string,int>> sortV(hash.begin(),hash.end());sort(sortV.begin(),sortV.end(),comp());vector<string> v;for(int i=0;i<k;i++){v.push_back(sortV[i].first);}return v;}
};
692. 前K个高频单词 - 力扣(LeetCode)
也可以使用std::set结构对键进行排序,如下所示:
std::unordered_map<int, int> unordered;
std::set<int> keys;
for (auto& it : unordered) keys.insert(it.first);
for (auto& it : keys) {std::cout << unordered[it] << ' ';
}
unordered_map怎么实现
哈希冲突
hash也叫散列。
举一个例子,学校图书馆提供借书义务,怎么快速找到某个同学借的书?
我们可以引入一个关键值(日期),借书记录存的位置。
哈希和散列就是这样。
关键值和存储位置,建立一个关联关系。
如果值的跳跃很大,那空间就会很浪费。
有一个方法可以减少空间浪费,就是让数值统一对一个数取模。
但是这样就又会衍生出一个问题,就是哈希碰撞,也叫做哈希冲突。
例如,3对10取模是3,33对10取模也是3
这样一来,本来不同位置的两个值,现在映射到了相同的位置。
对于闭散列,我们有一个方法来解决这种情况。
开放寻址法
当前空间已经被占用,在开放空间里按照某种规则,再寻找一个未被占用的位置存储。
开放寻址法有两种方法。
1.线性探测 hashi+i (i>=0)
2.二次探测 hashi+i^2 (i>=0)
不需要担心后面找不到位置,因为有负载因子在控制。
负载因子是当前值的个数和空间的比率,它会保持在一个值一下。
到一定程度,就会引发扩容。
负载因子太大,冲突可能会增加,效率降低。
负载因子太小,冲突会变少,但是空间消耗会增大,空间利用率降低。
要底层实现哈希表,有一个很尴尬的问题。
我们不知道如何判断一个位置有没有存值。
因为find是碰到空就停止,假设我们删除了20,那20的位置变为空。
我们再想寻找21,22,就找不到了,因为find在20的位置就停止了。
所以,我们需要区分开两种情况,一个位置是被删除了而导致空,还是本来就是空。
假设是本来就是空,那我们到这个位置就可以停止查找,假设是被删除才导致的空,我们就继续查找下去。
知道查找到这个值,或者查找到空为止。
不能直接扩容,因为映射关系会改变。
要扩容的话,要直接新开一段空间,重新映射,再释放旧空间。
代价很大,但是没有别的方式。
最难想到的就是扩容,咱们就新开一段空间,复用一下插入函数。
最后用swap交换一下新旧空间的内容。
这样写的好处是,函数调用完成后会自动释放空间。
下面是第一版的代码,之后的补全版本代码会在接下来几个博客中发出来。
代码
#pragma once
#include<vector>
namespace bit
{enum Status{EMPTY,EXIST,DELETE};template<class T, class V>struct HashData{pair<K, V> _kv;Status _s;//状态};template<class T,class V>class HashTable{public:HashTable(){_tables.resize(10);}bool insert(const pair<K, V>& kv){if (_n*10 / _tables.size() == 0.7) //因为整形相除不可能是0.7,所以乘10,也可以转换成double{size_t NewSize = _tables.size() * 2;HashTable<K, V> newHT;newHT._tables.resize(NewSize);for (int i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){newHT.insert(_tables[i].kv);}}_tables.swap(newHT._tables);}size_t hashi = kv.first % _tables.size();while (_tables[hashi]._s == EXIST){++hashi;//当等于存在时,往后查找hashi %= _tables.size();//防止越界访问}_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}private:vector<HashData> _tables;size_t _n = 0;//存储的关键字的个数};
}
相关文章:
从零带你底层实现unordered_map (1)
💯 博客内容:从零带你实现unordered_map 😀 作 者:陈大大陈 🚀 个人简介:一个正在努力学技术的准C后端工程师,专注基础和实战分享 ,欢迎私信! 💖 欢迎大家…...
第六届浙江省大学生网络与信息安全竞赛 2023年 初赛/决赛 WEB方向 Writeup
-------------------【初赛】------------------- easy php 简单反序列化 __debuginfo()魔术方法打印所需调试信息,反序列化时候执行! 链子如下: BBB::__debuginfo()->CCC::__toString()->AAA::__call()EXP: <?php…...
设计模式篇---装饰模式
文章目录 概念结构实例总结 概念 装饰模式:动态的给一个对象增加一些额外的职责。就扩展功能而言,装饰模式提供了 一种比使用子类更加灵活的替代方案。 装饰模式是一种对象结构型模式,它以对客户透明的方式动态地给一个对象附加上更多的责任…...
JAXB:根据Java文件生成XML schema文件
说明 JAXB有个schemagen脚本,可以根据Java文件生成XML schema。这个工具在JAXB独立发布包中有,可以从官网下载JAXB的独立发布包: https://eclipse-ee4j.github.io/jaxb-ri/ 示例 使用schemagen -d <path> <java files>格式 …...
opencv(5): 滤波器
滤波的作用:一幅图像通过滤波器得到另一幅图像;其中滤波器又称为卷积核,滤波的过程称为卷积。 锐化:边缘变清晰 低通滤波(Low-pass Filtering): 目标:去除图像中的高频成分&#…...
《微信小程序开发从入门到实战》学习二十二
3.3 开发创建投票页面 3.3.10 使用switch开关组件 用switch开关组件增加一个设置是否匿名投票的功能。 switch常用属性如下: checked 开还是关,默认false关 disabled 是否禁用,默认false不禁用࿰…...
LLM模型-讯飞星火与百度文心api调用
spark-wenxin 1-讯飞星火1_1-SparkApi.py1_2- Chat_spark.py1_3-调用api 2-百度文心2_1.code 3-两者之间比较与openai 1-讯飞星火 进入讯飞官网进行创建应用,获取相关密钥APPID,APISecret,APIKey,选择最新版本 首次调用讯飞官方a…...
AIGC ChatGPT 4 将数据接口文件使用Python进行入库Mysql
数据分析,数据处理的过程,往往将采集到的数据,或者从生产库过来的接口文件,我们都需要进行入库操作。 如下图数据: 将这样的数据接口文件,进行入库,插入到Mysql数据库中。 用Python代码来完成。 ChatGPT4来完成代码输入。 ChatGPT4完整内容如下: 这个任务可以使用`…...
Loguru:一个超酷的Python库
在项目中,了解代码运行情况至关重要,特别是遇到Bug需要排除问题的时候,而这正是日志记录发挥作用的地方。对于Python开发者来说,Loguru是一个简单但功能强大的日志记录库,它使得跟踪代码的行为变得轻松而高效。 什么是…...
cloud的概念
"Cloud"(云)通常指的是云计算(cloud computing)领域。云计算是一种通过网络(通常是互联网)提供计算资源和服务的模型。这些计算资源包括计算能力、存储空间、数据库、网络、分析能力等。云计算模…...
物联网赋能:WIFI HaLow在无线连接中的优势
在探讨无线网络连接时,我们不难发现,WIFI已经成为我们日常生活中不可或缺的一部分,承载了半数以上的互联网流量,并在家庭、学校、娱乐场所等各种场合广泛应用。然而,尽管WIFI4、WIFI5和WIFI6等协议无处不在,…...
淘宝商品详情数据接口(Taobao.item_get)
淘宝商品详情接口是一种程序化的接口,允许开发者根据商品ID或商品链接,获取淘宝平台上的商品详细信息。通过这个接口,开发者可以方便地获取商品的标题、价格、销量、描述等数据,进而提供给用户进行展示和购买。 使用淘宝商品详情…...
视频剪辑方法:一键批量调整色调的高效技巧
在视频剪辑的过程中,色调调整是一项非常重要的工作。它能够改变影片的氛围、情感和视觉效果,更好地沉浸在影片的情境中。然而,对于许多视频剪辑师来说,批量调整色调是一项非常繁琐的任务,需要耗费大量的时间和精力。色…...
NAS层协议栈学习笔记
NAS(Non-Access Stratum)是无线网络中非接入层及包括移动性管理(MM)和会话管理(SM)协议 ,在5G(NR)系统中连接管理(Connection Management)用于建立和释放UE与AMF之间的控制面(CP)信令连接。 5G中移动性管理是通过NAS信令在UE与核心网之间进行交互的,连接…...
前端食堂技术周刊第 105 期:TS 5.3 RC、Vite 5.0、W3C 新任 CEO、有害的 Pinia 模式、2024 更快的 Web
美味值:🌟🌟🌟🌟🌟 口味:金桂普洱 食堂技术周刊仓库地址:https://github.com/Geekhyt/weekly 大家好,我是童欧巴。欢迎来到前端食堂技术周刊,我们先来看下…...
jenkins 使用原生 git clone 命令,指定ssh密钥文件
使用环境变量 GIT_SSH_COMMAND 从Git版本2.3.0可以使用环境变量GIT_SSH_COMMAND,如下所示: GIT_SSH_COMMAND"ssh -i ~/.ssh/id_rsa_example" git clone example请注意,-i有时可以被您的配置文件覆盖,在这种情况下&…...
cobol数据类型
数据类型 数据部(data division)是用来描述程序中使用的变量的。 data name 数据名称 数据名称必须在数据部中定义,才能在过程部中使用。必须有一个用户自定义的名称,不能使用关键字,为存储实际数据的存储单元提供引…...
Java Web——JS中的BOM
1. Web API概述 Web API 是指浏览器提供的一套接口,这些接口允许开发人员使用 JavaScript(JS)来操作浏览器功能和页面元素。通过 Web API,开发人员可以与浏览器进行交互,以实现更复杂的功能和效果。 1.1. 初识Web AP…...
三十分钟学会Hive
Hive的概念与运用 Hive 是一个构建在Hadoop 之上的数据分析工具(Hive 没有存储数据的能力,只有使用数据的能力),底层由 HDFS 来提供数据存储,可以将结构化的数据文件映射为一张数据库表,并且提供类似 SQL …...
云计算发展
云计算,作为当今信息技术领域的核心力量,正在快速推动着我们社会的数字化转型。从智能家居到无人驾驶,从虚拟现实到人工智能,云计算的应用无处不在,它不仅仅是一个技术概念,更是一种全新的生活方式。在这个…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
