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

数据结构之哈希表

常见的三种哈希结构

  • 数组
  • 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容器、算法的简单认识

几种模板首先认识一下函数模板、类模板、栈模板。函数模板函数模板就是一个模型&#xff0c;而模板函数是函数模板经过类型实例化的函数。如下template<class T>是一个简单的函数模板&#xff1a;template<class T> T Max(T a, T b) {return a > b ? a : b; } …...

把python开发的web服务,打包成docker镜像的方法

要将Python开发的服务打成Docker镜像&#xff0c;可以按照以下步骤操作&#xff1a;1. 创建一个Dockerfile文件&#xff0c;该文件描述了如何构建Docker镜像。例如&#xff0c;以下是一个简单的Dockerfile文件&#xff0c;用于构建一个基于Python的Web应用程序&#xff1a; FRO…...

【Linux】多线程

进程和线程进程&#xff1a;一个正在运行的程序。状态&#xff1a;就绪&#xff0c;运行&#xff0c;阻塞&#xff1b;线程是进程中的一个执行路径&#xff0c;一个进程中至少有一个主线程&#xff08;main函数&#xff09;&#xff1b;有多条执行路径为多线程。创建一个线程用…...

Qt 设置窗口背景图片的几种方法实例

1.在paintEvent事件中绘制图片 void Widget::paintEvent(QPaintEvent * ev) {QPainter painter(this);painter.drawPixmap(rect(),QPixmap(":/bg.jpg"),QRect()); } drawPixmap在Widget的整个矩形区域绘制背景图片&#xff0c;第三个参数为要绘制的图片区域&#x…...

springcloud微服务架构搭建过程

项目地址&#xff1a;源代码 仅作为学习用例使用&#xff0c;是我开发过程中的总结、实际的一部分使用方式 开发环境&#xff1a; jdk11 springboot2.7.6 springcloud2021.0.5 alibabacloud 2021.0.4.0 redis6.0 mysql8.0 一、项目搭建 wdz-api&#xff1a;存放远程服务调用相关…...

LeetCode:215. 数组中的第K个最大元素

&#x1f34e;道阻且长&#xff0c;行则将至。&#x1f353; &#x1f33b;算法&#xff0c;不如说它是一种思考方式&#x1f340;算法专栏&#xff1a; &#x1f449;&#x1f3fb;123 一、&#x1f331;215. 数组中的第K个最大元素 题目描述&#xff1a;给定整数数组nums和整…...

vue面试题(day06)

文章目录前言请谈谈WXML与标准的html的异同&#xff1f;请谈谈WXSS和CSS的异同&#xff1f;请谈谈微信小程序主要目录和文件的作用&#xff1f;请谈谈小程序的双向绑定和vue的异同&#xff1f;简单描述下微信小程序的相关文件类型&#xff1f;微信小程序有哪些传值(传递数据)方…...

22 k8s常用命令

一、k8s网络 service网络 pod网络 节点网络 》 svc、pod网络都是虚拟机网络&#xff0c;真实网络是节点网络 二、内核升级 因为coentos系统3.10存在一些bug&#xff0c;docker、kubernetes不稳定&#xff0c;建议升级到4.4版本以上 三、集群资源分类 名称空间级别&#xff1…...

基于ESP32做低功耗墨水屏时钟

基于ESP32做低功耗墨水屏时钟电子墨水屏概述ESP32实验低功耗电子时钟功能描述接线开发实验结果电子墨水屏 概述 电子墨水是一种革新信息显示的新方法和技术。和传统纸差异是电子墨水在通电时改变颜色&#xff0c;并且可以显示变化的图象&#xff0c;像计算器或手机那样的显示。…...

常见路由器开源系统(固件)简介

前段时间在折腾如何通过 SD-WAN 组网方式打通办公室和家里的异地局域网。需要用到路由器的静态路由表功能&#xff0c;但是遍历整个家用路由器市场几乎没有支持这个功能的路由器&#xff08;只有华硕 RT-AX57 有这个功能&#xff0c;但是成本超出了我的预算&#xff09;。所有就…...

HCIE-Cloud Computing LAB备考第二步:逐题攻破--第二题:FusionAccess-搭建FA实验环境之安装基础组件和初始化ITA组件

HCIE-Cloud Computing LAB备考第二步:逐题攻破–第二题:FusionAccess-思维导图+题目=建立逻辑 专业术语 名词描述备注FusionAccess华为推出的桌面云产品,是一种虚拟桌面应用,它主要通过在硬件上部署FusionAccess配套的软件基础上,虚拟化出相互隔离的桌面,用户通过瘦客户端…...

Android APP检查设备是否为平板

正文 Android APP判断设备是否为平板的三种方法&#xff1a; 通过屏幕尺寸判断。一般来说&#xff0c;平板电脑的屏幕尺寸比手机大很多&#xff0c;可以根据屏幕的长宽比和尺寸等信息来区分设备类型。通过屏幕像素密度判断。一般来说&#xff0c;平板电脑的屏幕像素密度比手机…...

MP:使用步骤、分页、queryWrapper

Mybatis-Plus 官网&#xff1a; MyBatis-Plus (baomidou.com) 1. 意义 mybatis-plus是一个插件&#xff0c;它不能单独使用&#xff0c;必须配合mybatis使用&#xff0c;作用是简化mybatis操作&#xff0c;通过使用MP提供的方法&#xff0c;自动生成SQL语句进行CRUD 2. 使用步骤…...

C++ string类

C string类讲解 1、为什么学习string类&#xff1f; C语言中的字符串 在C语言中&#xff0c;字符串是以’\0’结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列的库函数&#xff0c;但是这些库函数与字符串是分离开的&#xff0c;不太符…...

虚拟机断电centos无法启动

虚拟机断电后centos7无法正常启动 XFS(sda3) 首先需要查找日志 在界面中查找日志是 journalctl 1.由于我的电脑死机&#xff0c;虚拟机没有正常关闭导致重启后 node1节点&#xff1a;可以登陆但是出现XFS(sda3)&#xff1a;Corruption of in-memoru data detectednode2节点&…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

实现弹窗随键盘上移居中

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

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...

ArcPy扩展模块的使用(3)

管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如&#xff0c;可以更新、修复或替换图层数据源&#xff0c;修改图层的符号系统&#xff0c;甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...

基于Java项目的Karate API测试

Karate 实现了可以只编写Feature 文件进行测试,但是对于熟悉Java语言的开发或是测试人员,可以通过编程方式集成 Karate 丰富的自动化和数据断言功能。 本篇快速介绍在Java Maven项目中编写和运行测试的示例。 创建Maven项目 最简单的创建项目的方式就是创建一个目录,里面…...

学习 Hooks【Plan - June - Week 2】

一、React API React 提供了丰富的核心 API&#xff0c;用于创建组件、管理状态、处理副作用、优化性能等。本文档总结 React 常用的 API 方法和组件。 1. React 核心 API React.createElement(type, props, …children) 用于创建 React 元素&#xff0c;JSX 会被编译成该函数…...