C++数据结构重要知识点(5)(哈希表、unordered_map和unordered_set封装)

2024-09-07 21:52

本文主要是介绍C++数据结构重要知识点(5)(哈希表、unordered_map和unordered_set封装),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.哈希思想和哈希表

(1)哈希思想和哈希表的区别

哈希(散列、hash)是一种映射思想,本质上是值和值建立映射关系,key-value就使用了这种思想。
哈希表(散列表,数据结构),主要功能是值和存储位置建立映射关系它通过key-value模型中的key来定位数组的下标,将value存进该位置。

哈希思想和哈希表数据结构这两个概念要分清,哈希是哈希表的核心思想。

(2)unordered_map、unordered_set是什么?

C++11提供了新容器unordered_map、unordered_set,它们的底层都是hash,你可能会注意到这两个容器和set、map名字很像,其实这两个容器和map、set功能基本一样,都提供非常高效的搜索,但unordered_map、unordered_set中序遍历不是有序的,map、set中序有序不同

(3)哈希表的实现

由于unordered_map、unordered_set源于hash表,它们封装的方式和前面AVL树和红黑树的思路一致,所以本篇文章在封装这件事情上仅会简单讲解。

①初步流程

整个过程其实很好理解,就是一个一对一的函数关系,如果我们要存key,直接找到映射位置存进去即可,如果存的是key-value,单独提取key再做映射也是很轻松的。如果key是string等非整型类型,需要先转换一次,也就是需要两层映射。

②第一层映射

我们先前就说过,key有可能不是数字,所以这里要进行一次转换,为保证统一性,我们都写上转换函数,其中针对要处理的key写特化

这里的K就是key的类型,专门为string写了一个特化,其实库里面也是这么做的,string毕竟还是太常见了。

string直接将它的每一个字符对应的ASCII码值 * 31,最后加起来,对应转换后的key,经过它人的实验和证明,在这个时候重复的概率很低,比如"abcd"和"dcba"如果直接将ASCII值相加得到的转换的key就会重复。我们也可以自己去找转换的方式,这不是唯一的。

③第二层映射(哈希函数)

哈希函数是哈希里面最关键的函数,为什么?我们试想,如果我们按照取模的的思想,一个size为10的vector,10 % 10 == 0,所以10放在数组下标0这个位置。而当20要放进数组里,20 % 10 == 0,也要放在0,这个时候就冲突了,20就要放在10下一个位置,数组下标为1,这就是典型的哈希冲突。

哈希冲突其实是零和博弈的体现,即资源有限,不同的人之间互相竞争。

哈希冲突几乎无法避免,但可以通过不同的哈希函数缓解。

第一种哈希函数就是直接定址法,在计数排序中我们就见识过它了,它必须针对已知的数据来开辟数组。比如我明确知道要存放的数据范围是-200 ~ 600,我就直接开辟800个空间,保证所有数据都能不冲突地存放进来。这其实是用key的值映射一个绝对位置或相对位置。优点就是这种方法解决了哈希冲突并且效率高。但缺点最致命,就是不仅数据要集中,而且要事先知道数据的范围。这只能说过于严苛了,所以看似诱惑力大,但实际情况基本不用。

第二种哈希函数就是除留余数法,这也是最轻松、最好理解的办法。就是我前面举的例子,按照数组大小来取模确定位置。hashi = key % N, N是表的大小。这使得就算数据未知,范围波动大,但我们依然可以用取模的操作让它们强制约束在一个数组的范围内做选择。但接下来就必须面对另一个问题,哈希冲突。

④闭散列(开放定址法)

为什么叫闭散列?就是像我最开始举的那个例子,第一个位置不够了就去下一个位置,这个哈希冲突是在数组内部解决的,并没有向外部申请空间。

开放定址法又分为线性探测、二次探测、三次探测等。线性探测是把这个坑占了去找挨着的下一个,二次探测是是按照第一次走1^2,如果这个位置也被占了就走2^2,以此类推,三次探测也一样。这些都是缓解哈希冲突,不想让数据挨得太近,但也只是缓解了。

如果我们想要找到这个数据,我们只需要再次映射,先找到本来该待的位置,比较数据是否一样,一样就找到了,不一样就证明发生了哈希冲突,按照规则向后找。如果走到空还没找到就说明没有这个数据。

我们可以使用枚举来标明每个位置的状态。

哈希冲突算是解决了一部分,还个问题就是扩容怎么办,数组总是有限的,我们必须考虑扩容的情况。扩容后映射关系也变了,前面的所有数据要重新映射一次。

考虑到效率,当数组中的空位越来越少的时候,哈希冲突更容易发生,就像还剩一个位置的停车场走到哪基本都找不到停车位的。所以引入了负载因子,每添加一个数据就+1,删除-1,它和数组总大小之比大于0.6或0.7就说明很拥堵了,需要扩容。

这里也复用了insert,使得我们不用手写insert两次,后续代码如下

删除就极为简单,我前面说过可以给每个位置配一个枚举的状态。这里我们就可以直接修改标记。同时我们也要注意,删除的位置后面还有有效数据,当我们查找时要注意判空的条件要忽略掉删除部分。

⑤开散列(拉链法、哈希桶)

这种处理方式就是将vector设为指针数组,每个指针像单链表那样管理数据。我们一般将这种数组的每个位置叫做一个桶,很形象。当有数据映射到该位置时,我们就不需要向后走,直接像链子一样挂在桶里。这样不管增数据、找数据还是删数据都转换成了链表的操作,库里面就使用这种办法。

插入采用头插,这在链表中是效率最高的。

我前面说过,优秀的处理方法只会缓解哈希冲突而不会解决它,当每个桶足够深了,效率就变低了,我们仍然要引入负载因子来判断扩容。闭散列的负载因子永远不会超过1,因为它会被限制在数组大小内,而开散列可以很轻松地超过1。不过依然推荐负载因子控制在0.6 ~ 0.7之间。扩容过程和闭散列比起来就有点麻烦了。

由于是开散列,我们引入了额外的空间来处理哈希冲突,当我们扩容对原来的数据进行重映射时,我们自然希望继续利用好我们的空间,也就是直接将指针交给新的位置保管而不是先析构、再构造,这样每次扩容的消耗会很大,而且这是无用消耗,很值得我们去优化,所以复用insert的思路就不可行了。

思路捋清楚,其实也很简单。遍历,找到不为空的指针就遍历这个桶,为每个指针找到新的位置,将这个指针头插进新位置即可。

删除、查找纯粹是单链表的知识,就不多阐述了。

有的极端情况会出现不管怎么扩容,一个桶下面挂的数据也很多,这个时候有的会将单链表处理为红黑树,当然这个仅作了解。

2.unordered_map、unordered_set封装

查找上unordered_set的findO(1),set是O(logN),插入有序的时候红黑树性能更好,旋转次数少,在很多场景下unordered_map、unordered_set有自己的优势。

下面仅以unordered_map做简单讲解

(1)hash实现

和AVL树和红黑树一样,我们要传key,实际数据类型,以及实际数据类型中的key

Hash是第一次转换函数,不要搞混了

创建结点的方式也要改变,使其更兼容两种类型

(2)unordered_map实现

这里展示的是整体框架,注意传参,以及仿函数的调用,这些熟悉后其实也挺简单的

(3)迭代器实现

这又是老生常谈的问题,怎么找下一个结点。我们知道了当前结点的位置,如何找到下一个?所以直接传哈希表的指针是最优解。

在直接定址法里,找下一个很轻松,直接pos++即可

在哈希桶里,我们要先向前探一探,看看链表还有没有下一个结点,没有的话就走到下一个桶。

注意要先判断桶走完没

这篇关于C++数据结构重要知识点(5)(哈希表、unordered_map和unordered_set封装)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146261

相关文章

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》:本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理?proxy

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

SpringBoot整合jasypt实现重要数据加密

《SpringBoot整合jasypt实现重要数据加密》Jasypt是一个专注于简化Java加密操作的开源工具,:本文主要介绍详细介绍了如何使用jasypt实现重要数据加密,感兴趣的小伙伴可... 目录jasypt简介 jasypt的优点SpringBoot使用jasypt创建mapper接口配置文件加密

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑