1、unordered系列关联式容器在C98中STL提供了底层为红黑树结构的一系列关联式容器。在查询时效率可以达到O(log2ⁿ)即最差情况下需要比较红黑树高度次当树中的节点非常多时查询效率也不理想因此STL提供了4个unordered系列的关联式容器这四个容器与红黑树的关联式容器使用方法基本类似只是其底层结构不同1.1 unordered_map1.1.1 unordered_map的介绍unordered_map是储存key, value键值对的关联式容器其允许通过key快速的索引到与其对应的value在unordered_map中键值通常用于唯一的标识元素而映射值是一个对象其内容与此键关联键的映射值的类型可能不同在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内 找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低unordered_maps实现了直接访问操作符(operator[])它允许使用key作为参数直接访问 value它的迭代器至少是前向迭代器单向迭代器1.2 unordered_set1.2.1 unordered_set和set的使用差异第一个差异是对key的要求不同set要求Key支持小于比较而unordered_set要求Key支持转成整形且支持等于比较第二个差异是迭代器的差异set的iterator是双向迭代器unordered_set是单向迭代器其次set底层是红黑树红黑树是二叉搜索树走中序遍历是有序的所以set迭代器遍历是有序去重。而unordered_set底层是哈希表迭代器遍历是无序去重第三个差异是性能的差异整体而言大多数场景下unordered_set的增删查改更快一些因为红黑树增删查改效率是 而哈希表增删查平均效率是 O(1)2、底层结构unordered系列的关联容器之所以效率比较高是因为其底层使用了哈希结构2.1 哈希概念哈希hash又称散列是⼀种组织数据的方式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立⼀个映射关系查找时通过这个哈希函数计算出Key存储的位置进行快速查找所以在结构中插入元素根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放。搜索元素对元素的关键码进行相同的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜素成功。eg:数据集合{6, 7, 8, 9, 10, 11}哈希函数设置为hash(key) key % sizekey 6 → h6%60 → 下标 0 存 6key 7 → h7%61 → 下标 1 存 7key 8 → h8%62 → 下标 2 存 8key 9 → h9%63 → 下标 3 存 9key 10 → h10%64 → 下标 4 存 10key 11 → h11%65 → 下标 5 存 11数组下标存储元素哈希值06017128239341045115用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快。但是也会出现问题在上述的操作中如果两个key同时指向同一个存储位置那么就产生了哈希冲突2.2 哈希冲突两个不同的key可能会映射到同一个位置去即不同的关键字通过相同的哈希函数计算出相同的哈希地址这种现象称为哈希冲突或哈希碰撞比如7和13通过哈希函数hash(key) key % sizesize6计算之后下标都是1两个数据属于同一位置2.3 哈希函数引起哈希冲突的一个原因可能是哈希函数设计不够合理哈希函数应遵循以下原则哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀的分布在整个空间中哈希函数应该比较简单一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中却很难做到但是我们要尽量往这个方向去考量设计下面列举一些常见的哈希函数2.3.1 直接定址法常用当关键字的范围比较集中时直接定址法就是非常简单高效的方法直接定址法本质就是用关键字计算出⼀个绝对位置或者相对位置比如一组关键字都在[0,99]之间那么我们开一个100个数的数组每个关键字的值直接就是存储位置的下标取关键字的某个线性函数为散列地址Hash(Key) A * Key B优点是简单、均匀缺点是需要事先知道关键字的分布情况。所以直接定址法适合查找比较小且连续的情况2.3.2 除留余数法除法散列法也叫做除留余数法顾名思义假设哈希表的大小为M那么通过key除以M的余数作为映射位置的下标也就是哈希函数为h(key) key % M注意当使用除法散列法时要尽量避免M为某些值如2的幂10的幂等。如果是2^X那么key % 2^X本质相当于保留key的后X位那么后x位相同的值计算出的哈希值都是⼀样的就冲突了如{63 , 31}看起来没有关联的值如果M是16也就是2^4 那么计算出的哈希值都是15因为63的二进制后8位是0011111131的⼆进制后8位是00011111当使用除法散列法时建议M取不太接近2的整数次幂的⼀个质数(素数)2.3.3 乘法散列法了解乘法散列法对哈希表大小M没有要求他的大思路第一步用关键字K乘上常数 A (0A1)并抽取出 kA 的小数部分。第二步后再用M乘以kA的小数部分再向下取整h(key) floor(M × ((A × key)%1.0))其中floor表示对表达式进行下取整A∈(0,1)这里最重要的是A的值应该如何设定Knuth认为 A ( 5 − 1)/2 0.6180339887…黄金分割点比较好。2.3.4 全域散列法了解如果存在一个恶意的对手他针对我们提供的散列函数特意构造出⼀个发生严重冲突的数据集比如让所有关键字全部落入同一个位置中。这种情况是可以存在的只要散列函数是公开且确定的就可以实现此攻击。解决方法自然是见招拆招给散列函数增加随机性攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。2.4 处理哈希冲突主要有两种两种方法 开放定址法和链地址法2.5 开放定址法闭散列在开放定址法中所有的元素都放到哈希表里当⼀个关键字key用哈希函数计算出的位置冲突了则按照某种规则找到一个没有存储数据的位置进行存储开放定址法中负载因子一定是小于的。这里的规则有三种线性探测、二次探测、双重探测2.5.1 线性探测从发生冲突的位置开始依次线性向后探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾则回绕到哈希表头的位置插入通过哈希函数获取待插入元素在哈希表中的位置如果该位置没有元素则直接插入新元素如果该位置有元素依次向后1探测直到寻找到下一个空位置为止boolInsert(constpairK,Vkv){// 查重先查找要插入的key如果已存在直接返回false禁止重复插入if(Find(kv.first))returnfalse;// 判断负载因子是否触发扩容// 负载因子 有效数据数量 / 数组总长度0.7触发扩容减少哈希冲突if((double)_n/_tables.size()0.7){// 注释掉的是废弃扩容写法//std::vectorHashDataK, V newtables(_tables.size()*2);//for (auto data : _tables)//{// if (data._status EXIST)// {// //...// }//}//_tables.swap(newtables);// 创建临时哈希表用来存放扩容后的数据HashTableK,V,HashnewHT;// 给临时哈希表分配质数长度的底层数组newHT._tables.resize(__stl_next_prime(_tables.size()1));// 遍历旧哈希表全部格子for(autodata:_tables){// 只搬运状态为有效存在的数据跳过空、已删除格子if(data._statusEXIST){// 把旧数据插入到新哈希表自动重新哈希线性探测newHT.Insert(data._kv);}}// 交换新旧哈希表底层vector数组交换效率极高无需拷贝大量数据_tables.swap(newHT._tables);}Hash hs;// 1.用哈希函数把key转为大整数哈希值// 2.对数组长度取模压缩到合法下标范围得到原始哈希位置size_t hash0hs(kv.first)%_tables.size();size_t hashihash0;// 记录当前正在探测的数组下标初始等于原始哈希位置size_t i1;// 线性探测偏移量每次冲突向后偏移i位// 线性探测循环如果当前下标格子存有有效数据代表哈希冲突继续向后找空位while(_tables[hashi]._statusEXIST){// 计算下一个探测下标模数组长度防止下标越界hashi(hash0i)%_tables.size();i;// 偏移量自增下一轮向后多看一格}// 循环结束当前hashi下标格子是空/已删除可以存入新数据_tables[hashi]._kvkv;// 把键值对存入找到的格子_tables[hashi]._statusEXIST;// 修改格子状态为有效存在_n;// 哈希表有效数据个数1returntrue;// 插入完成}查找用哈希函数把key转为哈希值找到待查找元素在哈希表中的位置只要当前格子不是空白位 EMPTY就持续循环HashDataK,V*Find(constKkey){Hash hs;// 通过哈希函数算出key的哈希值对数组长度取模得到key理论存放的起始下标hash0size_t hash0hs(key)%_tables.size();// hashi当前正在检查的数组下标初始先从理论起始位置开始查找size_t hashihash0;size_t i1;// 线性探测// 循环条件当前位置不是空白空位EMPTY就继续查找//while(_tables[hashi]._status!EMPTY){if(_tables[hashi]._statusEXIST_tables[hashi]._kv.firstkey)return_tables[hashi];// 线性探测公式起始下标偏移量模数组长度实现环形遍历防止下标越界hashi(hash0i)%_tables.size();i;}returnnullptr;}删除boolErase(constKkey){auto*ptrFind(key);if(ptr){// 不直接清空数据仅把状态修改为DELETEptr-_statusDELETE;--_n;returntrue;}else{returnfalse;}}采用闭散列处理哈希冲突时不能随便删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索因此线性探测采用标记的伪删除法将删除位置标记成DELETE删除一个元素线性探测的优点是实现非常简单缺点是一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同 关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。可以利用下面的二次探测解决该问题2.5.2 二次探测从发生冲突的位置开始依次左右按二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止如果往右走到哈希表尾则回绕到哈希表头的位置如果往左走到哈希表头则回绕到哈希表尾的位置二次探测公式为hc(key, i) (hash0 ± i²) % Mi {1, 2, 3,… ,M/2}补充负载因子负载因子的定义为填入表中的元素个数/散列表的长度扩容时当负载因子大于等于0.7时哈希冲突会增加因此选择扩容key不能取模的问题当key是string/Date等类型时key不能取模那么我们需要给HashTable增加一个仿函数这个仿函数支持把key转换成⼀个可以取模的整形templateclassKstructHashFunc{// 重载()size_t返回无符号整数size_toperator()(constKkey){return(size_t)key;}};// 特化templatestructHashFuncstring{// BKDRsize_toperator()(conststringstr){size_t hash0;for(autoch:str){hashch;hash*131;}returnhash;}};2.6 链地址法开散列首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中开散列中每个桶中放的都是发生哈希冲突的元素2.6.1 开散列模拟实现namespacehash_bucket{templateclassK,classVstructHashNode{//pairK,V_kv;HashNodeK,V*_next;// 节点构造函数创建节点时传入键值对HashNode(constpairK,Vkv):_kv(kv),_next(nullptr){}};// 哈希表主类模板// K键类型V值类型Hash哈希函数工具默认使用之前写的HashFuncKtemplateclassK,classV,classHashHashFuncKclassHashTable{typedefHashNodeK,VNode;public:HashTable()// 初始化哈希桶数组初始容量取大于等于1的最小质数每个桶头指针初始化为空:_tables(__stl_next_prime(1),nullptr),_n(0){}~HashTable(){for(size_t i0;i_tables.size();i){Node*cur_tables[i];// 当前桶的节点重新映射挂到新表while(cur){Node*nextcur-_next;deletecur;curnext;}_tables[i]nullptr;}}boolInsert(constpairK,Vkv){// 先查找当前key是否已经存在哈希表中若key重复不允许重复插入直接返回falseif(Find(kv.first))returnfalse;Hash hs;// 负载因子1扩容if(_n_tables.size()){//HashTableK, V newHT;//newHT._tables.resize(_tables.size()*2);//// 遍历旧表将所有值映射到新表//for (auto cur : _tables)//{// while (cur)// {// newHT.Insert(cur-_kv);// cur cur-_next;// }//}//_tables.swap(newHT._tables);// 创建新的扩容桶数组容量取比原容量更大的最小质数质数减少哈希冲突vectorNode*newtables(__stl_next_prime(_tables.size()1));for(size_t i0;i_tables.size();i){// 取出旧桶链表头节点Node*cur_tables[i];// 当前桶的节点重新映射挂到新表while(cur){// 提前保存下一个节点防止迁移时链表断裂丢失数据Node*nextcur-_next;// 插入到新表// 扩容后数组长度改变必须重新计算当前key对应的新下标size_t hashihs(cur-_kv.first)%newtables.size();// 头插法当前节点指向新桶原本的头节点cur-_nextnewtables[hashi];// 更新新桶头指针为当前迁移节点newtables[hashi]cur;curnext;}_tables[i]nullptr;}_tables.swap(newtables);}// 扩容完成后计算待插入key对应的桶下标size_t hashihs(kv.first)%_tables.size();// 在堆内存新建存储当前键值的链表节点Node*newNodenewNode(kv);// 头插逻辑新节点后继指向当前桶原有链表头newNode-_next_tables[hashi];// 更新桶头指针新节点成为链表第一个节点_tables[hashi]newNode;_n;returntrue;}Node*Find(constKkey){Hash hs;// 算出key对应的哈希桶下标size_t hashihs(key)%_tables.size();Node*cur_tables[hashi];while(cur){if(cur-_kv.firstkey)returncur;curcur-_next;}returnnullptr;}boolErase(constKkey){Hash hs;// 定位目标key所在的哈希桶size_t hashihs(key)%_tables.size();// prev记录cur的前一个节点用来断开链表Node*prevnullptr;Node*cur_tables[hashi];while(cur){if(cur-_kv.firstkey){// 情况1要删除的是链表头节点prev为空if(prevnullptr){_tables[hashi]cur-_next;}// 情况2要删除的是中间/尾部节点else{// 前驱节点跳过待删节点直接链接后继节点prev-_nextcur-_next;}deletecur;returntrue;}prevcur;curcur-_next;}returnfalse;}private://vectorlistpairK, V _tables;vectorNode*_tables;size_t _n0;// 实际存储的数据个数};