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

热门文章

暂无图片
编程学习 ·

STM32开放式开发环境:释放创造力

市场上涌现各种价格亲民的经济型微控制器,助力新一代开发者创造令人兴奋的新型嵌入式应用。如今的开发工具非常好用,软硬件均呈现模块化趋势,插接安装简单容易,使得产品设计评估和原型开发周期大幅缩短。STM32开放式开发环境是业内独一无二的软硬件开发平台,堆叠式插接电路…
暂无图片
编程学习 ·

3D打印与互联网发展的探索

“互联网+3D打印+创意文化”模式崭露头角 互联网具备大众属性,3D打印技术及服务或许能结合互联网带来更多创新,通过互联网渠道带来全流程的在线、交互体验、互联网化来实时响应消费用户需求形成新的商业模式。 近日,国内一家3D打印综合性服务平台已悄然上线,为消费用户提供…
暂无图片
编程学习 ·

在海外如何寻找蓝海市场

2010年左右,我国跨境进口零售电商企业开始逐渐出现,到2015年电商数量实现了爆发式的增长。当然,随后就开始进入红海时代,网易考拉海购、天猫国际、京东全球购、唯品国际、小红书、洋码头占领了大部分市场。 国内红海,那就出海。 红海、蓝海概念的提出,让更多的创业者积极…
暂无图片
编程学习 ·

单调栈解决Next Greater Number一类题

单调栈是什么? 单调栈使得每次新元素入栈后,栈内元素都保持有序(单调递增或者单调递减)。 单调递增栈:栈中数据出栈的序列为单调递增序列。 单调递减栈:栈中数据出栈的序列为单调递减序列。 注意:这里所说的递增递减是出栈的顺序,不是栈中数据的顺序。 单调栈的应用 通…
暂无图片
编程学习 ·

PAT 甲级 1013 Battle Over Cities (25分)

题目 1013 Battle Over Cities (25分) It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any othe…
暂无图片
编程学习 ·

linux 修改时间并永久生效

Centos系统,必须同时修改系统时间和硬件时间,才可以保证修改有效,单纯的使用date命令修改系统时间,是立即生效,重启后系统还原。具体操作如下:1.date {查看目前本地的时间}2.hwclock --show {查看硬件的时间}3.如果硬件时间和系统时间不同,那就对硬件的时间进行修改4.hw…
暂无图片
编程学习 ·

GUI学生管理系统--创建项目

这里写自定义目录标题实现步骤步骤一:创建Java项目步骤二:在项目文件中创建文件夹步骤三: 在lib文件夹中加入数据库启动包步骤四:在images中添加图片步骤五:在help文件夹中添加所需使用到的帮助文件 实现步骤 在上次实训结束以后,我们完成了数据库表数据的插入,完成了建…
暂无图片
编程学习 ·

查询语句执行顺序

select 查询列表 7 from 表1 别名 1 连接类型 join 表2 2 on 连接条件 3 where 筛选 4 group by 分组列表 5 having 筛选 6 order by排序列表 8 limit 起始条目索引,条目数; 9
暂无图片
编程学习 ·

Eclipse中Java文件图标由实心J变成空心J的问题

这里写自定义目Eclipse中Java文件图标由实心J变成空心J的问题录标题 在eclipse中空心J的java文件,表示不被包含在项目中进行编译,而是当做资源存在项目中。例如 当是单个文件为空心J的时候 1.右击该文件 – >BuildPath -->Include (如果没有includ这个选项可以采用别…
暂无图片
编程学习 ·

(精品)cesium-绘制动态线(解决闪烁)的进击研究教程

文章目录前因后果效果图先行动态线绘制思路代码及效果图动态线连续绘制思路代码及效果图结论 前因后果 最近项目中,需要绘制墙体,测试了cesium提供的诸多entity,发现都死在了贴纹理阶段;最后妥协于使用wall实体进行墙体的绘制.期间解决了纹理贴图效果,高程遮挡,动态绘制线路闪烁…
暂无图片
编程学习 ·

Codeforces Round #654 (Div. 2) D. Grid-00100(构造)

题目链接 思路:题目要求价值最小,怎么放价值最小?每次放的地方行和列最大值最小值之差为1,那么当行或者列%n==0时就从头开始此时的行列最大值最小值之差依旧是1 #include <cstdio> #include <cstring> #include <algorithm> #include <set> #inclu…
暂无图片
编程学习 ·

SpringBoot框架使用

—— 本文转自onestar : SpringBoot框架原理分析 一、起步依赖原理分析 在搭建SpringBoot环境的时候,在pom.xml中添加了两个依赖,对这两个依赖进行分析,分别是: SpringBoot的起步依赖:spring-boot-starter-parent web的起步依赖:spring-boot-starter-web 1、spring-bo…