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

C++——哈希结构

1.unordered系列关联式容器

本节主要介绍unordered_map和unordered_set两个容器,底层使用哈希实现的

unordered_map

1.unordered_map是储存<key,value>键值对的关联式容器,其允许通过key快速查找到对应的value,和map非常相似,但是底层实现完全不同

2.unoredered_map没有对<key,value>进行排序,而是映射一个对象,其内容与其键相关联,键和映射值的类型可能不同

2.底层结构

unordered系列的关联式容器之所以效率比较高,是因为底层实现了哈希结构

哈希概念

构造一种储存结构,通过某种函数使元素的储存位置与他的关键码建立一一映射的关系,那么在查找该元素的时候很快就能找到

这个顺序表叫做哈希表,但是还有一个问题,如果插入44会出现什么问题?

哈希冲突

不同关键字通过相同的哈希函数计算出相同的哈希地址,这种现象称为哈希冲突

这种情况我们通常用开放定址法和哈希桶解决

常见哈希函数

常用的除留余数法

就是用我们插入的数据模上哈希表的长度,得出的余数,就是我们得到的插入位置的下标;

哈希表什么时候扩容

开放定址法实现哈希

#pragma once
#include<vector>template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};namespace open_address
{enum State{EXIST,EMPTY,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable(){_tables.resize(10);}bool Insert(const pair<K,V>& kv){if (Find(kv.first)){return false;}//扩容if (_n * 10 / _tables.size() >= 7){HashTable<K, V> newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hs;size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state ==EXIST){++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST &&_tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;--_n;return true;}}private:vector<HashData<K, V>> _tables;size_t _n = 0;};

相关文章:

C++——哈希结构

1.unordered系列关联式容器 本节主要介绍unordered_map和unordered_set两个容器&#xff0c;底层使用哈希实现的 unordered_map 1.unordered_map是储存<key,value>键值对的关联式容器&#xff0c;其允许通过key快速查找到对应的value&#xff0c;和map非常相似&#x…...

智能小程序 Ray 开发面板 SDK —— 无线开关一键执行模板教程(一)

1. 准备工作 前提条件 已阅读 Ray 新手村任务&#xff0c;了解 Ray 框架的基础知识已阅读 使用 Ray 开发万能面板&#xff0c;了解 Ray 面板开发的基础知识 构建内容 在此 Codelab 中&#xff0c;您将利用面板小程序开发构建出一个支持一键执行及自动化的无线开关面板&…...

rockDB(1)

文章目录 概述编译rocksdb压缩库 基本接口 小结 概述 RocksDB 是 Facebook 的一个实验项目&#xff0c;目的是希望能开发一套能在服务器压力下&#xff0c;真正发挥高 速存储硬件性能的高效数据库系统。这是一个C库&#xff0c;允许存储任意长度二进制 KV 数据。支持原 子读写…...

[element-ui] 自动获取el-input的焦点

<el-input v-model"filterPlanName" ref"autoFocus" ></el-input>this.$nextTick((_) > {this.$refs.autoFocus.focus(); })参考&#xff1a; [element-ui]自动获取el-input的焦点...

智能闹钟的睡眠评估算法是如何工作的呢

智能闹钟的睡眠评估算法是智能闹钟功能的核心部分&#xff0c;它主要通过以下几个步骤来工作&#xff1a; 一、数据收集 传感器数据&#xff1a;智能闹钟内置多种传感器&#xff0c;如心率传感器、呼吸传感器、体动传感器以及环境传感器&#xff08;如温度、湿度、光线传感器…...

Vue + View-ui-plus Upload实现手动上传

本文实现Vue Upload组件多文件手动上传&#xff0c;支持上传图片&#xff08;image&#xff09;、压缩文件(zip/rar)、表格(excel)、pdf 一、dom结构 <Row><Col :span"19"></Col><Col :span"2"><div class"ivu-btn-uplo…...

Radxa ROCK 3C开发板编译Opencv,支持调用树莓派摄像头模块V2

目录 1、ROCK 3C和树莓派摄像头模块V2介绍2、ROCK 3C在rsetup开启支持3、测试指令4、编译Opencv4.1 增加swap&#xff0c;确保内存够用4.2 安装依赖和下载opencv4.3 编译参考链接 5、使用opencv调用树莓派摄像头模块V2 1、ROCK 3C和树莓派摄像头模块V2介绍 ROCK 3C 是一款基于…...

Spring02

文章目录 1. IOC/DI注解开发2. IOC/DI注解开发管理第三方bean3. Spring整合4. AOP简介5. AOP入门案例6. AOP工作流程7. AOP配置管理8. AOP事务管理 1. IOC/DI注解开发 注解开发定义bean用的是2.5版提供的注解&#xff0c;纯注解开发用的是3.0版提供的注解 pom.xml添加依赖 &l…...

Linux系统中的高级内核模块调试技术

引言 在Linux系统中进行高级内核模块开发时&#xff0c;调试是不可或缺的重要环节。调试技术能够帮助开发人员发现和解决代码中的错误和问题&#xff0c;提高开发效率和代码质量。本文将深入探讨Linux系统中高级内核模块调试的技术和方法&#xff0c;包括常用的调试工具、调试…...

竞赛报名管理系统asp.net+sqlserver

竞赛报名管理系统 功能简单 内容单调 适合学习 asp.net 三层架构 sqlserver2022数据库 账号登陆注册 用户管理 克赛管理 竞赛报名 竞赛评分 公告维护 修改密码 新增竞赛 2019数据库版本低 附加不了 需要高版本数据库 说明文档 运行前附加数据库.mdf&#xff08;或sql生成数据…...

Python爬虫核心面试题2

网络爬虫 1. 什么是HTTP协议&#xff1f;它有哪些常见的请求方法&#xff1f;2. 在进行网络爬虫时&#xff0c;如何判断一个网站是否允许被爬取&#xff1f;3. 在使用HTTP请求时&#xff0c;如何处理重定向&#xff1f;4. 解释HTTP状态码200、404、500的含义。5. 什么是Session…...

【2024年华数杯全国大学生数学建模竞赛】C题:老外游中国 问题思路分析及Python代码实现

【2024 年华数杯全国大学生数学建模竞赛】C题&#xff1a;老外游中国 问题思路分析及Python代码实现 1 题目 最近&#xff0c;“city 不 city”这一网络流行语在外国网红的推动下备受关注。随着我国过境免签政策的落实&#xff0c;越来越多外国游客来到中国&#xff0c;通过网…...

HTTP/2:让网络飞起来

文章目录 一、HTTP/2 的基本概念和背景二、HTTP/2 的主要特性和优势2.1 二进制帧2.2 多路复用2.3 头部压缩2.4 服务器推送 三、HTTP/2 的实现和部署四、HTTP/2 与现有技术的比较五、HTTP/2 与 Web 性能优化六、结束语&#xff1a;让 HTTP/2 助力你的 Web 开发 今天我们来聊聊一…...

C++ primer plus 第17 章 输入、输出和文件:刷新输出缓冲区

C primer plus 第17 章 输入、输出和文件&#xff1a;刷新输出缓冲区 C primer plus 第17 章 输入、输出和文件&#xff1a;刷新输出缓冲区 文章目录 C primer plus 第17 章 输入、输出和文件&#xff1a;刷新输出缓冲区17.2.3刷新输出缓冲区 17.2.3刷新输出缓冲区 如果程序使…...

项目总结2

文件的分片上传 格外功能是&#xff1a;秒传&#xff0c;断点续传。 今天最惨&#xff0c;上午找bug&#xff0c;下午一直在修改&#xff0c;晚上脑子what了&#xff0c;混乱的很&#xff0c;数据表之间的逻辑不清晰&#xff0c;导致我传值&#xff0c;还有操作数据库一直有问…...

PXE实现自动批量安装部署操作系统

PXE简介 PXE&#xff08;Preboot eXecution Environment&#xff09;是一种在计算机启动时使用网络接口从远程服务器获取操作系统安装和启动信息的技术。通过PXE&#xff0c;计算机可以从局域网中的PXE服务器上下载操作系统安装文件&#xff0c;并进行自动化的操作系统部署或故…...

Cyber Weekly #18

赛博新闻 1、Google 狂卷小模型&#xff0c;2B 参数 Gemma 2 赶超 GPT-3.5 Google本周发布了开源的轻量级、高性能模型 Gemma 2 2B。它拥有 20 亿参数&#xff0c;是从更大规模的模型中提炼而来的&#xff0c;在 LMSYS 大模型竞技场的得分超越了 GPT-3.5 和 Mixtral 8x7B。该…...

Open Interpreter - 开放解释器

文章目录 一、关于演示它是如何工作的&#xff1f;与 ChatGPT 的代码解释器比较 二、快速开始三、更多操作1、互动聊天2、程序化聊天3、开始新的聊天4、保存和恢复聊天5、自定义系统消息6、更改模型7、在本地运行 Open Interpreter终端Python上下文窗口&#xff0c;最大令牌 8、…...

“八股文”:程序员的福音还是梦魇?

——一场关于面试题的“代码战争” 在程序员的世界里&#xff0c;“八股文”这个词儿可谓是“如雷贯耳”。不&#xff0c;咱们可不是说古代科举考试中的那种八股文&#xff0c;而是指程序员面试中的那些固定套路的题目。如今&#xff0c;各大中小企业在招聘程序员时&#xff0…...

数据结构第2天作业 8月3日

单向链表 typedef int datatype; //由于有效数据不一定是正数&#xff0c;所以将数据重命名。typedef struct lklst{ //不能是无名结构体了&#xff0c;因为定义指针域的时候需要使用union{int len; //头结点时候使用&#xff1b;datatype data; …...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

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

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

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...

前端调试HTTP状态码

1xx&#xff08;信息类状态码&#xff09; 这类状态码表示临时响应&#xff0c;需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分&#xff0c;客户端应继续发送剩余部分。 2xx&#xff08;成功类状态码&#xff09; 表示请求已成功被服务器接收、理解并处…...

spring boot使用HttpServletResponse实现sse后端流式输出消息

1.以前只是看过SSE的相关文章&#xff0c;没有具体实践&#xff0c;这次接入AI大模型使用到了流式输出&#xff0c;涉及到给前端流式返回&#xff0c;所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...