数据结构之哈希表
常见的三种哈希结构
- 数组
- set(集合)
- map(映射)
set(集合)
| 集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
| std::multiset | 红黑树 | 有序 | 是 | 否 | O(log n) | O(log n) |
| std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。
当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
map(映射)
| 映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(log n) | O(log n) |
| std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。
map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。
哈希法
虽然std::set、std::multiset 的底层实现是红黑树,不是哈希表,std::set、std::multiset 使用红黑树来索引和存储,不过给我们的使用方式,还是哈希法的使用方式,即key和value。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。 map也是一样的道理。
这里在说一下,一些C++的经典书籍上 例如STL源码剖析,说到了hash_set hash_map,这个与unordered_set,unordered_map又有什么关系呢?
实际上功能都是一样一样的, 但是unordered_set在C++11的时候被引入标准库了,而hash_set并没有,所以建议还是使用unordered_set比较好,这就好比一个是官方认证的,hash_set,hash_map 是C++11标准之前民间高手自发造的轮子。
总结
总结一下,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。
如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法!
相关文章:
数据结构之哈希表
常见的三种哈希结构 数组set(集合)map(映射) set(集合) 集合底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率std::set红黑树有序否否O(log n)O(log n)std::multiset红黑树有序是否O(log n)O(log n)std::unordere…...
linux信号理解
linux信号:用户、系统或进程发送给目标进程的信息,以通知目标进程中某个状态的改变或是异常。 信号产生原因:软中断或者硬中断。可细分为如下几种原因: ①系统终端Terminal中输入特殊的字符来产生一个信号,比如按下&am…...
HC小区管理系统window系统安装教程
实操视频 HC小区管理系统局域网window物理机部署教程_哔哩哔哩_bilibili 一、下载安装包 百度网盘: 链接:https://pan.baidu.com/s/1XAjxtpeBjHIQUZs4M7TsRg 提取码:hchc 或者 123盘 hc-window.zip官方版下载丨最新版下载丨绿色版下…...
自动化测试工具软测界的不二之选,还不快速来了解
目录 引言: 前言: 一.龙测AI-TestOps云平台使用教程 1.如何登录龙测AI-TestOps云平台 登录方法① 登录方法② 2.龙测AI-TestOps云平台界面布局 3.龙测AI-TestOps云平台菜单功能 ①创建项目 ②应用管理 ③设备管理 ④订单 二.总结 引言&#…...
centos系统/dev/mapper/centos-root目录被占满的解决方式
最近在做虚拟机部署docker微服务时,发现磁盘内存占满,无法进行操作。open /var/lib/dpkg/info/libc6:amd64.templates: no space left on device接下来就写下我在备份虚拟机上如何解决根目录被占满的问题:1、查看虚拟机磁盘使用情况df -h可以…...
【C++】STL容器、算法的简单认识
几种模板首先认识一下函数模板、类模板、栈模板。函数模板函数模板就是一个模型,而模板函数是函数模板经过类型实例化的函数。如下template<class T>是一个简单的函数模板:template<class T> T Max(T a, T b) {return a > b ? a : b; } …...
把python开发的web服务,打包成docker镜像的方法
要将Python开发的服务打成Docker镜像,可以按照以下步骤操作:1. 创建一个Dockerfile文件,该文件描述了如何构建Docker镜像。例如,以下是一个简单的Dockerfile文件,用于构建一个基于Python的Web应用程序: FRO…...
【Linux】多线程
进程和线程进程:一个正在运行的程序。状态:就绪,运行,阻塞;线程是进程中的一个执行路径,一个进程中至少有一个主线程(main函数);有多条执行路径为多线程。创建一个线程用…...
Qt 设置窗口背景图片的几种方法实例
1.在paintEvent事件中绘制图片 void Widget::paintEvent(QPaintEvent * ev) {QPainter painter(this);painter.drawPixmap(rect(),QPixmap(":/bg.jpg"),QRect()); } drawPixmap在Widget的整个矩形区域绘制背景图片,第三个参数为要绘制的图片区域&#x…...
springcloud微服务架构搭建过程
项目地址:源代码 仅作为学习用例使用,是我开发过程中的总结、实际的一部分使用方式 开发环境: jdk11 springboot2.7.6 springcloud2021.0.5 alibabacloud 2021.0.4.0 redis6.0 mysql8.0 一、项目搭建 wdz-api:存放远程服务调用相关…...
LeetCode:215. 数组中的第K个最大元素
🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀算法专栏: 👉🏻123 一、🌱215. 数组中的第K个最大元素 题目描述:给定整数数组nums和整…...
vue面试题(day06)
文章目录前言请谈谈WXML与标准的html的异同?请谈谈WXSS和CSS的异同?请谈谈微信小程序主要目录和文件的作用?请谈谈小程序的双向绑定和vue的异同?简单描述下微信小程序的相关文件类型?微信小程序有哪些传值(传递数据)方…...
22 k8s常用命令
一、k8s网络 service网络 pod网络 节点网络 》 svc、pod网络都是虚拟机网络,真实网络是节点网络 二、内核升级 因为coentos系统3.10存在一些bug,docker、kubernetes不稳定,建议升级到4.4版本以上 三、集群资源分类 名称空间级别࿱…...
基于ESP32做低功耗墨水屏时钟
基于ESP32做低功耗墨水屏时钟电子墨水屏概述ESP32实验低功耗电子时钟功能描述接线开发实验结果电子墨水屏 概述 电子墨水是一种革新信息显示的新方法和技术。和传统纸差异是电子墨水在通电时改变颜色,并且可以显示变化的图象,像计算器或手机那样的显示。…...
常见路由器开源系统(固件)简介
前段时间在折腾如何通过 SD-WAN 组网方式打通办公室和家里的异地局域网。需要用到路由器的静态路由表功能,但是遍历整个家用路由器市场几乎没有支持这个功能的路由器(只有华硕 RT-AX57 有这个功能,但是成本超出了我的预算)。所有就…...
HCIE-Cloud Computing LAB备考第二步:逐题攻破--第二题:FusionAccess-搭建FA实验环境之安装基础组件和初始化ITA组件
HCIE-Cloud Computing LAB备考第二步:逐题攻破–第二题:FusionAccess-思维导图+题目=建立逻辑 专业术语 名词描述备注FusionAccess华为推出的桌面云产品,是一种虚拟桌面应用,它主要通过在硬件上部署FusionAccess配套的软件基础上,虚拟化出相互隔离的桌面,用户通过瘦客户端…...
Android APP检查设备是否为平板
正文 Android APP判断设备是否为平板的三种方法: 通过屏幕尺寸判断。一般来说,平板电脑的屏幕尺寸比手机大很多,可以根据屏幕的长宽比和尺寸等信息来区分设备类型。通过屏幕像素密度判断。一般来说,平板电脑的屏幕像素密度比手机…...
MP:使用步骤、分页、queryWrapper
Mybatis-Plus 官网: MyBatis-Plus (baomidou.com) 1. 意义 mybatis-plus是一个插件,它不能单独使用,必须配合mybatis使用,作用是简化mybatis操作,通过使用MP提供的方法,自动生成SQL语句进行CRUD 2. 使用步骤…...
C++ string类
C string类讲解 1、为什么学习string类? C语言中的字符串 在C语言中,字符串是以’\0’结尾的一些字符的集合,为了操作方便,C标准库中提供了一些str系列的库函数,但是这些库函数与字符串是分离开的,不太符…...
虚拟机断电centos无法启动
虚拟机断电后centos7无法正常启动 XFS(sda3) 首先需要查找日志 在界面中查找日志是 journalctl 1.由于我的电脑死机,虚拟机没有正常关闭导致重启后 node1节点:可以登陆但是出现XFS(sda3):Corruption of in-memoru data detectednode2节点&…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
