当前位置: 首页 > 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节点&…...

FModel:虚幻引擎资源解析的技术突破与实践指南

FModel&#xff1a;虚幻引擎资源解析的技术突破与实践指南 【免费下载链接】FModel Unreal Engine Archives Explorer 项目地址: https://gitcode.com/gh_mirrors/fm/FModel 在游戏开发与逆向工程领域&#xff0c;资源解析工具的选择直接影响工作效率与成果质量。当面对…...

OpenClaw人人养虾:接入iMessage

此方案为旧版 iMessage 接入方式&#xff0c;仅适用于 macOS 且配置复杂。新用户请优先使用 BlueBubbles 方案&#xff0c;它更稳定且功能更丰富。 前置要求 macOS 12 Monterey 或更高版本&#xff08;仅支持 macOS&#xff09;已登录 Apple ID 并激活 iMessageHomebrew 包管…...

如何通过自动化工具高效获取阴阳师游戏资源?完整实践指南

如何通过自动化工具高效获取阴阳师游戏资源&#xff1f;完整实践指南 【免费下载链接】OnmyojiAutoScript Onmyoji Auto Script | 阴阳师脚本 项目地址: https://gitcode.com/gh_mirrors/on/OnmyojiAutoScript 阴阳师自动化工具是一款功能强大的智能辅助应用&#xff0c…...

SEO_2024年最新SEO趋势分析与实战策略解读

<h1 id"2024seo">2024年最新SEO趋势分析与实战策略解读</h1> <p>在数字营销的快速发展中&#xff0c;搜索引擎优化&#xff08;SEO&#xff09;作为提升网站流量的重要手段&#xff0c;一直备受关注。2024年&#xff0c;SEO领域再度发生了一些重要…...

SpringCloud Alibaba与Nacos版本不匹配?手把手教你解决‘Client not connected‘错误

SpringCloud Alibaba与Nacos版本兼容性实战&#xff1a;彻底解决Client not connected问题 微服务架构的复杂性往往隐藏在细节之中。当SpringCloud Alibaba项目启动时控制台突然抛出Client not connected, current status:STARTING的红色警告&#xff0c;不少开发者都会心头一紧…...

OneMore插件:提升OneNote效率的160+实用功能全解析

OneMore插件&#xff1a;提升OneNote效率的160实用功能全解析 【免费下载链接】OneMore A OneNote add-in with simple, yet powerful and useful features 项目地址: https://gitcode.com/gh_mirrors/on/OneMore 作为一名科研工作者&#xff0c;李明每天需要处理数十页…...

RWKV7-1.5B-g1a实操手册:基于CSDN GPU平台的完整调用流程

RWKV7-1.5B-g1a实操手册&#xff1a;基于CSDN GPU平台的完整调用流程 1. 模型简介 rwkv7-1.5B-g1a 是基于新一代 RWKV-7 架构的多语言文本生成模型&#xff0c;特别适合中文场景下的轻量级应用。这个1.5B参数的版本在保持较高生成质量的同时&#xff0c;对硬件要求非常友好&am…...

Vue3最新版二维码生成避坑指南:从基础配置到企业级定制(附GitHub源码)

Vue3企业级二维码生成实战&#xff1a;从核心原理到性能优化 二维码作为连接物理世界与数字世界的桥梁&#xff0c;在现代Web应用中扮演着重要角色。本文将带您深入Vue3的二维码生成技术栈&#xff0c;不仅涵盖基础实现&#xff0c;更聚焦企业级应用中的高阶技巧与性能优化方案…...

无障碍辅助利器:OpenClaw+GLM-4.7-Flash语音控制电脑实操

无障碍辅助利器&#xff1a;OpenClawGLM-4.7-Flash语音控制电脑实操 1. 为什么我们需要语音控制电脑 去年夏天&#xff0c;我的一位程序员朋友因意外导致手部受伤&#xff0c;暂时失去了正常使用键盘鼠标的能力。看着他艰难地用语音输入法逐字敲代码&#xff0c;我开始思考&a…...

s2-pro效果展示:多说话人语音合成(同一模型切换不同音色)

s2-pro效果展示&#xff1a;多说话人语音合成&#xff08;同一模型切换不同音色&#xff09; 1. 专业级语音合成效果展示 s2-pro作为Fish Audio开源的专业级语音合成模型&#xff0c;其最惊艳的能力在于同一模型支持多种音色切换。通过上传不同的参考音频&#xff0c;模型可以…...