unordered_map/unorderd_set使用与哈希介绍

在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 O(logN),即最差情况下 需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次 数就能够将元素找到,因此在C++11中,STL又提供了4个unordered系列的关联式容器。

unordered_map/unordered_set/unordered_multimap/unordered_multiset

这四个容器与关联式容器(map、set、multimap、multiset)使用方式基本类似,它们都属于关联式容器,但是主要区别有(主要分析unordered_map与map,其他都是对应相同的):

  • 底层结构不同:map底层是红黑树,时间复杂度是O(logN);unordered_map底层是哈希桶,时间复杂度为O(1)。unordered_map相对于map来说效率更高一些;
  • 因为底层结构的不同,unorderde_map遍历出来是无序的,map遍历出来是有序的;
  • map与unordered_map存储的都是一个pair<>键值对,但是做map的key需要支持比较大小,因为底层是红黑树,红黑树是二叉搜索树,遍历是按照key来比较的,遍历出是有序的。做unordered_map的key需要支持取模,如果不能支持取模,需要写一个hash函数将其转换成为整形进行取模。还要支持= =,因为查找的时候找到对应的桶了,那是通过 = =去比较确认是不是要找的值;
  • map与unorderde_map都实现了直接访问操作符(operator[]);

哈希

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

哈希概念

哈希就是一种数据结构,它是将一个元素的关键码通过哈希函数计算出该元素在哈希表当中的位置进行存放,使元素的位置与它的关键码能够建立一一映射的关系,在查找时候通过该哈希函数也能很快的找到。

哈希冲突

如果不同元素的关键字通过哈希哈数计算出相同的哈希地址,就叫做哈希冲突或者哈希碰撞。其实产生哈希冲突的主要原因就是哈希函数设计的不合理,设计哈希函数需要尽可能的保证计算出来的地址能均匀分布在整个空间中 。常见哈希函数:

  • 1、直接定址法:取关键字的某个线性函数为散列地址,比如在一串字符串中找出第一次只出现一次的字符。适用场景:数据量比较小,并且比较集中,需要事先 知道关键字的分布情况,不存在哈希冲突。
  • 2、除留余数法:如果表的大小为m,那么取一个不大于m,但最接近或者等于m的质数作为除数,由此计算出散列地址。适用场景:数据量很大,但是存在哈希冲突。
  • 3、平方取中法:假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为 4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 ,适用场景:不知道关键字的分布,而位数又不是很大的情况 。

哈希函数还可以根据程序员的需求通过自己设定,写出一个仿函数来计算散列地址,然后将unordered_map的第三个模板参数显示指出对应的自己设定的仿函数。

注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

如何解决哈希冲突(闭散列与开散列)

闭散列(又叫开放地址法):当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那 么可以把key存放到冲突位置中的“下一个” 空位置中去。但是如何找到下一个空位置?

  • 方法①—》线性探测:从发生冲突的位置开始,依次向后继续探测,直到找到一个空的位置为止结束探测。Hash(key)+ i (i = 0,1,2,3…)

  • 方法②—》二次探测:从发生冲突的位置开始,并不挨个进行探测,而是每次都增加一个 i ^2。Hash(key) + i ^2(i = 0,1,2,3,4…)。

    线性探测实现简单,但是一旦发生冲突就会冲突成为一片。所以二次探测就是线性探测的优化,但是二次探测仍旧会产生冲突

    注意1:在插入和查找时,找到空的位置就分别插入和结束,但是在进行删除的时候不能够直接删出,因为可能有个元素与要删除的元素产生的哈希冲突经过线性探测映射到了其他位置,如果直接删除会影响其他元素的搜索,比如删除元素4,如果直接删除掉,44查找起来可能会受影响:
    在这里插入图片描述
    所以,为每一个空间采用一个状态标识来解决直接删除带来的问题,当删除元素时将该对应空间设置为DELETE;在进行查找某个元素时,判断标识位如果是EXIST和DELETE就继续往后探测查找,直到遇到EMPTY结束:

    哈希表每个空间进行标记:
    EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除 
    enum State{EMPTY, EXIST, DELETE}; 
    

    注意2:为了避免哈希冲突,当哈希表满足一定条件时还需要进行增容,如何增容是通过负载因子来确定的。负载因子 = 存储的实际数据个数 / 表的大小。负载因子越大,哈希冲突越大,哈希查找效率就越低;负载因子越小,空间利用率就越低。所以对于开放地址法,应该将负载因子设置到0.7~0.8以下。C++JAVA中将负载因子限制为0.75,超过这个值将resize散列表。
    注意3:散列表增容不能直接增容,需要重新开空间,将元素重新进行映射。

开散列(拉链法):首先对关键码用散列函数计算散列地址,具有相同地址的关键码 通过一个单链表链接起来形成一个哈希桶,将哈希桶的头结点存储在哈希表中。
在这里插入图片描述
从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。

  • 注意1:桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可能会导致一 个桶中链表节点非常多,会影响的哈希表的性能,因此在一定条件下需要对哈希表进行增容,那该条件
    怎么确认呢?开散列最好的情况是:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时(也就是负载因子
    == 1时候),可以给哈希表进行增容。

  • 注意2:散列表增容不能直接增容,需要重新开空间,将元素重新进行映射。

开散列的思考:

  • 如果key为整形,就不需要转换;如果为字符串类型就需要转成整形。
  • 同闭散列一样,除留余数法,最好模一个素数。
  • 如果某一个桶太多,就考虑将该桶挂成红黑树。

热门文章

暂无图片
编程学习 ·

Nginx学习笔记

1.Nginx简介 Nginx 是一个高性能的HTTP和反向代理服务器,特点是占内存少,并发能力强。Nginx转为性能优化而开发,性能是器最重要的考量,实现上非常注重效率,能经受住高负载的考验,有报告表明能支持的高达50000个并发连接数。 百度,腾讯,网易,淘宝等都在使用Nginx. 2.反…
暂无图片
编程学习 ·

二、21【设计模式】之状态模式

今天的博客主题设计模式 ——》 设计模式之状态模式状态模式 SP (State Pattern)定义允许对象在内部状态发生改变时改变它的行为,看起来好像修改了它的类。类的行为是由状态决定的,不同的状态下该类有不同的行为。就是一个对象在其内部改变的时候,它的行为也随之改变。核心…
暂无图片
编程学习 ·

《剑指 Offer》——调整数组顺序使奇数位于偶数前面

1. 本题知识点 数组 2. 题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。 例如: Input: [1,2,3,4,5]Output: [1,3,5,2,4]3. 解题思路 …
暂无图片
编程学习 ·

Docker在阿里云上(Centos)下载安装

Docker作用 简单来说就是可以不在考虑项目的运行环境直接转移部署项目,只需要一个镜像文件,甚至可以理解为一个虚拟机(windows的VM软件里安装linux系统)。 卸载旧版本 sudo yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker…
暂无图片
编程学习 ·

MySql简单入门_第四篇(1)_视图

4、使用视图【将视图用于检索SELECT 而不用于更新INSERT,UPDATE和DELETE】视图是虚拟的表,与包含数据的表不一样,视图只包含使用时动态检索数据的查询。视图提供了一种MySQL的SELECT语句层次的封装,可用来简化数据处理以及重新格式化基础数据或保护基础数据。【视图仅仅是用…
暂无图片
编程学习 ·

springboot aop 切到service层,不生效

今天发现一个问题,使用aop切到service层方法上,idea会有切成功的标志,编译也不报错,但就是不生效。研究了下发现,是因为我切的方法被同一个service中的其他方法调用,这样的话就不生效了,暂不清楚原因,解决方法时切到调用它的方法上,这只是切点不生效的一种情况,希望能…
暂无图片
编程学习 ·

AssemblyInfo.cs文件参数具体讲解

AssemblyInfo.cs文件参数具体讲解 原文地址:https://www.cnblogs.com/scy251147/archive/2010/10/23/1859576.html 在asp.net中有一个配置文件AssemblyInfo.cs主要用来设定生成的有关程序集的常规信息dll文件的一些参数,下面是默认的AssemblyInfo.cs文件的内容具体介绍 //是否…
暂无图片
编程学习 ·

直播软件开发中的音视频编码转换怎么实现

2.1、下载ffmpeg。 下载网址:[url]http://www.ffmpeg.org/download.html[/url] 2.2、解压缩tar -zxvf ffmpeg-2.0.1.tar.gz2.3、编辑profile文件: vi /etc/profile 在文件末尾加上两句话:export FFMPEG_HOME=/usr/local/ffmpeg export PATH=$FFMPEG_HOME/bin:$PATH2.4、配置…
暂无图片
编程学习 ·

Maven工程配置(build/run委托,skipTests)

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是…
暂无图片
编程学习 ·

vue前端代码优化-1

也许有人会感觉CR没有什么卵用,只要我代码实现了功能,我完成了开发任务,我就OK了,为啥还要CR??但是CR真的是有必要的,你不仅可以发现自己代码中的不足之处,待优化点,简洁明了的代码易读别人接手也会很快。1. 比如在vue项目中只有某一个组件用某一个特别长的常量对象,…
暂无图片
编程学习 ·

HDU 4686 Arc of Dream (矩阵快速幂)

题意:An Arc of Dream is a curve defined by following function:where a 0 = A0 a i = a i-1 * AX+AY b 0 = B0 b i = b i-1 * BX+BY 给出n,A0,AX,AY,B0,BX,BY,What is the value of AoD(N) modulo 1,000,000,007? 题解:矩阵快速幂 数据范围很恶心,先要对原数据取…
暂无图片
编程学习 ·

硅上量子点激光器报告最新进展总结(二)

————来自蔻享学术UCSB万雅婷博士报告一、量子点在传统的F-P腔上的应用:87%的电注入效率,175mW的输出功率,6.5mA的阈值电流 APL photonics 3(3), 030901(2018)这些指标到现在仍然代表硅上量子点激光器最好的性能。图一 F-P量子点激光器寿命测试 硅上量子点激光器具…
暂无图片
编程学习 ·

Java8的集合:HashSet的实现原理

HashSet 概述 HashSet 实现 Set 接口,由哈希表(实际上是一个 HashMap 实例)支持。它不保证 set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用 null 元素。 HashSet 的实现 对于 HashSet 而言,它是基于 HashMap 实现的,HashSet 底层使用 HashMap 来保存所有元素…
暂无图片
编程学习 ·

网络安全技术及应用第3版 主编贾铁军等——教材习题 期末重点 复习题 知识提炼 (第5章 密码与加密技术)

参考教材:网络安全技术及应用 第3版 主编贾铁军等 第5章 密码与加密技术选择题填空题简答题计算题1)凯撒密码:(将字母表示一个循环的表,再进行移位)2)单字母替换密码3)矩阵转置技术4)RSA算法论述题 选择题 张三给李四发信息,为了实现数据保密,加密秘钥是()————李…
暂无图片
编程学习 ·

@RequestBody和@RequestParam区别

@RequestParam 注解@RequestParam接收的参数是来自requestHeader中,即请求头。RequestParam可以接受简单类型的属性,也可以接受对象类型。@RequestParam有三个配置参数:required 表示是否必须,默认为 true,必须。 defaultValue 可设置请求参数的默认值。 value 为接收url的…
暂无图片
编程学习 ·

分布式计算(课堂测验+MOOC答案)

分布式计算(课堂测验+MOOC答案)分布式计算(课堂测验+MOOC答案)第一章节第二章节第三章节第四章节第五章节 分布式计算(课堂测验+MOOC答案) 第一章节第二章节第三章节 1、【单选题】在EC2服务中,每个实例自身携带 ()个存储模块。(A) A. 1 B. 2 C. 3 D. 4 2、【单选题】…
暂无图片
编程学习 ·

CTO也糊涂的常用术语:功能模块、业务架构、用户需求、文档……

功能模块、业务架构、需求分析、用户需求、系统分析、功能设计、详细设计、文档、业务、技术……很多被随口使用的名词,其实是含糊甚至错误的。到底含糊在哪里,错误在哪里,不仅仅是新手软件开发人员糊涂,许多入行多年的老手也一样。虽然很多老手功成名就,挂着CTO、总架构师…