在里面不会根据key值进行排序遍历出来是无序的。在这里插入图片描述以上是unordered_set的声明Key是unordered_set底层关键字的类型。unordered_set有两个仿函数类型要求Hash和Pred第一个是默认要求Key支持转换成整型这与它的底层是哈希桶有关。如果不支持或想按照自己的需求走可以自行实现将Key转成整型的仿函数传给第二个模板参数。第二个是默认要求支持比较相等这个也与底层哈希桶有关如果不支持或者想按照自己的需求走可以自行实现比较相等的仿函数传给第三个模板参数。unordered_set底层存储数据是从空间配置器申请的如果有需要可以自己实现内存池然后传给第四个模板参数。一般来说后面三个模板参数在实际使用中是不需要进行传递的。差异性能差异unordered_set相对于set 增删查 O(logN)的时间复杂度它的时间复杂度是O(1)但实际差距没有这么大。key的要求的差异set要求默认支持小于比较而unordered_set默认是要求支持等于比较而且还要支持有Key转换整型的仿函数。它也会除重。迭代器以及遍历顺序差异set是双向迭代器而unordered_set是支持单向迭代器。前者中序遍历-有序后者无序。unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似支持Key冗余。unordered_multimap/unordered_multiset跟multimap/multiset之间的差异也是性能、key的要求、迭代器与遍历顺序三个方面的差异。二、认识哈希表1. 哈希概念哈希(hash)又称散列是一种组织数据的方式。它的本质就是通过哈希函数把关键字Key跟存储位置数组下标建立一个映射关系然后查找时通过这个哈希函数来计算出Key存储的位置进而做到快速查找。哈希表通常通过数组来实现。我们通过下面的直接定址法来更好的理解让关键字跟存储位置建立一个映射关系2. 直接定址法直接定址法直接定址法适用于关键字的范围比较集中时比如一组关系都在[0, 99]之间那么我们开一个大小为100个数的数组每个关键字的值直接就是存储位置的下标。又比如一组关键字的值都在[a, z]的小写字母那么我们开一个大小为26的数组每个关键字ascii码 - ‘a’a的ascii码就是存储位置的下标。直接定址法的本质就是用关键字计算出一个绝对或者相对位置。现在有一个题目给定一个字符串 s 只有小写英文字母找到 它的第一个不重复的字符并返回它的索引 。如果不存在则返回 -1 。代码实现代码语言javascriptAI代码解释int firstUniqChar(string s) { int count[26] {0}; for (auto e : s) { count[e - a]; } //i是用来遍历s的,不是用来遍历count的 for (int i 0; i s.size(); i) { if (count[s[i] - a] 1) { return i; } } return -1; }这里我们建立了一个用来计数的数组count然后每一个值全初始化为0每一个英文字母减去字母a得到的ascii值都能映射到对应的一个下标上面。之后遍历s里面的每一个英文字符就能轻松得到每一个字母出现的次数。如果我们想要确认s里面有没有字母a只需要访问count[0]就能知道这里的映射关系就是数组下标 字母 - ‘a’。这里的关键字就是s里面出现的英文字母它们和count数组的下标建立了映射关系。直接定址法的缺点也非常明显那就是如果关键字的范围比较分散的话比如只存2个数一个1一个10000难不成要开上10000个数大小的数组吗甚至在有的情况下内存是不够用的这样就太浪费空间了所以又有其他的方法让关键字跟存储位置之间建立一个映射关系比如除留余数法/除法散列法。3. 除法散列法/除留余数法除法散列法也叫做除留余数法假设哈希表的大小为M那么让关键字Key除以M得到的余数作为映射位置的下标就能够确保所有的数都能映射到这个哈希表对应的位置上。它的哈希函数为hkey key%M。当使用除法散列法时要尽量避免M为某些值如2的幂10的幂等。如果是2^x,那么key%2^x的本质就相当于是保留key二进制的后x位后x位相同的值计算出来的哈希值hkey都是一样的会造成哈希冲突接下来会讲到。比如{63, 31}这两个数看起来完全没有关联但63二进制后八位是0011111131的二进制后八位是00011111如果M是16那么计算出来的哈希值就都是15将二进制倒数第四位之前的1都抹去了。如果是10^x保留10进制后面的x位也是同理它就更明显了如果M是102与12与22都是一样的哈希值2。当使用除法散列法时建议M取不太接近2的整数次幂的一个质数。实践中如果可以有效解决冲突的话M取2的整数次幂也可以比如java里面HashMap的实现里M就是取的2的整数次幂。还有其他的方法比如乘法散列法全域散列法等有兴趣的读者大大们可以去了解了解。4. 哈希冲突当两个不同的key值经过哈希函数和模运算之后得到的数组下标可能一样会映射到同一个位置去这种问题我们叫做哈希冲突也叫做哈希碰撞。理想的情况是设计出一个能够避免冲突的哈希函数但在实际情况中冲突不可避免能够做到的就是尽可能设计出优秀的哈希函数减少冲突的次数也要设计出解决冲突的办法。5. 哈希函数哈希函数是将任意大小的数据映射到固定范围的整数值的函数这个整数值再通过某种方式通常是取模转换为数组下标。比如除法散列法的的哈希函数是hkey key%M模出来的哈希值被固定在0到M - 1范围内这里的哈希值就是数组下标。key → 哈希函数 → 哈希值 → 取模运算 → 数组下标一个好的哈希函数应该让N个关键字被等概率的均匀的分布到哈希表的M个空间中但是实际中很难做到但也应该朝着这个方向去设计。6. 负载因子假设哈希表中已经映射了存储了N个值而哈希表的大小为M那么负载因子 N/M。负载因子越大代表它的空间利用率越高越小代表它的存储效率越高。负载因子越大代表这个哈希表越满接下来的存储就越容易发生哈希冲突发生哈希冲突然后根据处理哈希冲突的方法进行存储效率一定会降低。负载因子越小接下来的存储虽然不容易发生哈希冲突但是会造成空间的浪费。负载因子的取值很重要一般是取0.7左右。三、处理哈希冲突-开放定址法的具体实现解决哈希冲突主要有两种方法开放定址法和链地址法接下来我们来了解解决哈希冲突其中的一种办法—开放定址法。1. 开放定址法在开放定址法中所有的元素都放到哈希表里当一个关键字key用哈希函数计算出的位置冲突了则按照某种规则找到一个没有存储数据的位置进行存储开放定址法中负载因子一定是小于1的。这里的规则有三种线性探测二次探测双重探测。1.1 线性探测从发生冲突的位置开始依此线性向后探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾则要回绕到哈希表头的位置。即 hkey key % M hash0如果hash0的位置冲突了则线性探测公式为hkey hashi hash0 i% M, i {123…M - 1}由于负载因子是小于1的那么探测最多M - 1次一定能够找到存储位置。因为哈希表一定还是有没有存储数据的存储位置的。群集/堆积若hash0位置连续冲突且hash0hash1hash2都已经存储了数据那么后续映射到hash0hash1hash2的值都会抢夺hash3的位置这种现象叫做群集/堆积。而二次探测可以在一定程度上解决这个问题。接下来通过一组数组来演示一下如何利用线性探测规则来存储数据。 {31425816}M为11利用除法散列法哈希函数为hkey key % M。在这里插入图片描述按照顺序一个一个往里面存储数据3会映射到下标为3的位置14也会映射到下标为3的位置但是这个位置已经存储了数据那么14就要从下标为3的这个位置往后找一个没有存储数据的位置–下标为4的这个位置之后再存储25816也是同理。如果直接映射到的那个位置没有存储值那么直接存储就好但若已经存储了值就需要线性往后面找一个没有存储值的位置进行存储。至于查找也是根据key通过哈希函数得到的映射位置hash0然后让key与这个位置存储的值进行比较如果不相等则继续线性向后寻找然后依次进行比较直到找到这个与key相等的值或者遇到没有存储数据的位置。1.2 二次探测从发生冲突的位置开始依次左右按二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止如果往右走到哈希表尾则回绕到哈希表头的位置如果往左走到哈希表头则回绕到哈希表尾的位置。hkey hash0 key % M hash0的位置冲突了则二次探测公式为hckeyi hashi hash0 ± i^2% Mi {123…M/2}就是i变成了i^2。二次探测当hashi hash0 - i ^ 2% M时当hashi 0时需要hashi M。二次探测能在一定程度上解决群集/堆积的问题但是无法完全避免。双重散列能够进一步解决这个问题。其实二次探测包括下面的双重散列都是为了让数据的存储能够更加分散更加均匀能够尽可能的减少哈希冲突。1.3 双重散列了解第一个哈希函数计算出的值发生冲突使用第二个哈希函数计算出一个跟key相关的偏移量值不断往后探测直到寻找到下一个没有存储数据的位置为止。h1key hash0 key%Mhash0位置冲突了则双重探测公式为hckey,i hashi hash0 i * h2(key)% Mi {123…M}。要求h2key M 且 h2key和 M 互为质数有两种简单的取值方法1、当M为2整数幂时h2key从[0, M - 1] 任选一个奇数2、当M为质数时h2key key % M - 1 1。保证h2key与 M 互质是因为根据固定的偏移量所寻址的所有位置将形成一个群若最大公约数p gcdMh1key 1那么所能寻址的位置的个数为M/P M使得对于一个关键字来说无法充分利用整个散列表。举例来说若初始探查位置为1偏移量为3整个散列表大小为12那么所能寻址的位置为{1,4,7,10}寻址个数为12 / gcd123 4。2. 开放定址法代码实现2.1 框架搭建我们首先要思考一个问题如何删除一个数倘若直接删掉它而又有多个key都是映射到这个位置上的删去它存储在它后面的key值应该如何去找毕竟我们的查找的逻辑是将存储的值与key值进行比较直到找到它或遇到没有存储key值的位置就停止直接删掉的话首次查找就会停止。如上表我们若是直接将3删掉那么这个位置将为空14应该如何去找到我们转变思路可以不将它直接删掉而是设立一个状态变量用来储存每个哈希表里存储数据的状态表示它是空EMPTY)是删掉了(DELETE)还是存在着(EXIST)枚举类型可以很好的表示。哈希表通常由数组实现我们通过vector来实现里面存储着的是哈希表里的数据。这个数据应该要由表示它的状态量和真正存储的数据组合而成–类HashData。