一.unorder_map和unorder_set的使用注unorder_map和unorder_set的底层均是哈希。1.带unorder和不带的区别①.遍历有无序set的输出unorder_set的输出可看出unorder_set是无序的set是有序的。②.对key的要求③.迭代器④.性能二.哈希表相关知识点1.概念注1.该位置里存储的是跟Key有关的东西并不一定是Key本身。就像某道oj题里存储位置也可以存储Key出现的次数。2.哈希函数就是关键字和它存储位置间的桥梁。3.由于能够通过哈希函数直接计算出key对应的存贮位置属于指哪打哪因此哈希的时间复杂度跟vector,string一样是O(1)。2.哈希函数h(key)代表哈希函数值。经实例化的h(key)就是key存储位置的下标。2-1.直接定址法用key的值直接当存储位置的下标也就是h(key) key。很高效但仅适用于数据(Key)集中且为整型的条件下。2-2.除法散列法/除留余数法(最常用)假设哈希表大小为M,通过key除以M的余数作为映射位置的下标也就是哈希函数为h(key)key%M2-2-1如何避免冲突2-3.乘法散列法2-4.全域散列法(防止被攻击)2-5.哈希冲突指两个不同的Key映射到同一个位置上。相当于同一个位置上要存两个Key的东西,这必然会引发冲突。eg:2-5-1.开放地址法处理冲突①.开放地址法介绍位置被人占了就近找一个没有人的位置。②.规则介绍Ⅰ.线性探测群集会让多个哈希值堵在同个位置使得这几个值都要去接着线性探测因而在线性探测上白白浪费掉大量时间。Ⅱ.二次探测(改善群集即线性探测后互相将映射位置占据的问题)本质是让哈希值更为分散。2-5-2.链地址法(哈希桶)处理冲突开放地址法无论是上面哪三种都不是一个最优解这是开放地址法本身的局限性造成的这是一种内耗式抢别人空间的方法。那我们干脆就让它冲突只是把冲突的几个值用链表挂起来。2-6.负载因子哈希表中已经存储了N个值(Key的数量为N)哈希表大小为M那么负载因子 N / M。代表哈希表满员率。负载因子越大则哈希冲突的可能性就越大但空间利用率越高。2-7.将关键字转为整数当关键字做映射时整型的关键字好做映射计算(整型可支持“”“%”操作从而支持哈希函数和散列法)所以不是整型的关键字需想办法转换为整型。因此后面的Key是关键字转化为整型后的值相当于做了双重映射。三.哈希表的实现(开放地址法)1.不用pair的缘故既要有删除操作又要确保不会影响查找就需要待删除位置数据不为空就干脆单独封装一个HashData类,里面既有存数据的pair,也有显示状态的标签_State。用三种状态代表存储位置下数据的去留。删除的数据状态为delete;还存在的数据状态为exist;空位置的状态为empty。由此删除了数据的位置就不是空就可规避上面由空带来的查找失败。enum State { EXIST, EMPTY, DELETE }; templateclass K, class V class HashData { pairK, V _kv; State _state EMPTY;//用枚举造一个状态标便于后续查找 }; templateclass K,class V class HashTable { private: vectorHashDataK, V _tables; size_t _n 0; };2.Insert接口①.是模size()还是capacity()?Insert接口中需要用到除法散列法取模,去确认映射位置那么来探讨一下该去模谁。既然是插入那肯定是在vector存数据的区域进行插入而该区域的大小为size(),所以该模size()。②.解决线性探测死循环(探讨扩容)假如哈希表满了这时候不去扩容依旧执行插入那么会一直去线性探测造成死循环。为了解决这个问题就拿负载因子开刀当负载因子大于0.7时就自动扩容。扩容这里将旧表元素插入新表用了点小巧思。创建新表后负载因子小于0.7就不进入扩容的这个if分支就去到下面的插入操作里。体现了一种类似于递归的代码的复用但递归是自己调用自己而这里是旧表调用新表的Insert。扩容改进之质数表(既要也要)inline unsigned long __stl_next_prime(unsigned long n) {//扩容小帮手 // Note: assumes long is at least 32 bits. static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53 , 97 , 193 , 389 , 769, 1543, 3079, 6151 , 12289 , 24593, 49157 , 98317, 196613, 393241 , 786433, 1572869, 3145739, 6291469 , 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos lower_bound(first, last, n);//lower_bound作用于升序区间返回第一个大于等于n的数。 return pos last ? *(last - 1) : *pos; }线性探测的代码③.用二次探测代替线性探测完整代码bool Insert(const pairK, V kv) { if (Find(kv.first)) return false;//禁止冗余。 //负载因子0.7,扩容。 if (_n * 10 / _tables.size() 7)//由于除只保留整数会影响精度所以整体扩大10倍。 { HashTableK, V, Hash newht;//创建新表 newht._tables.resize(_tables.size() * 2); for (auto data : _tables) { newht.Insert(data._kv); } _tables.swap(newht._tables);//夺舍 } Hash hash; size_t hash0 hash(kv.first) % _tables.size();//用仿函数转化kv类型已解决某些类型kv无法取模的问题。 //判断映射位置是否放值如果放了哈希冲突就线性探测。 size_t hashi hash0; size_t i 1; int flag 1; while (_tables[hashi]._state EXIST) { //线性探测 hashi (hash0 i) % _tables.size();//模一下可以让到末尾的回环未到末尾的值依旧不变。 i; ////二次探测 //if(hashi 0) hashi _tables.size();//解决模出来为负数的问题 //hashi (hash0 (flag * i * i)) % _tables.size(); //if (flag 1) //{ // flag -1; //} //else //{ // flag 1; // i; //} }3.解决模板参数某些类型(如string)无法使用“”等操作符的问题情景解决方案①.类型允许强制类型转化或者强转不影响相关操作的用一个仿函数将无法执行相关操作的类型强制转化为无符号整型。templateclass K//仿函数 struct HashFunc { size_t operator()(const K key) { return (size_t)key;//强制类型转化 } };②.不允许强转或者强转有影响的将所有该类型的数据先映射成unsigned int,然后再进行取模相当于进行两次映射struct StringHashFunc { size_t operator()(string s) {//做第一次映射 size_t hash 0; for (auto ch : s) { hash ch; } return hash; } };要是执行Insert操作第二次映射在Insert里。③.改进string类型的数据实在太常用了频繁的写仿函数实在很麻烦有没有不写仿函数的打法有的兄弟有的用特化。写一个HashFunc这个仿函数的string特化。如下图HashFunc作为缺省模板参数出现就不用特意写系统也会自动调用而系统有惰性会去调用符合条件且现成的string特化是类模板已经实例化好的类所以就会去自动调用它。④.BKDR为应对这种冲突的情形给hash * 131,能将冲突的概率降到极低。⑤.最终代码templateclass K//仿函数 struct HashFunc { size_t operator()(const K key) { return (size_t)key;//强制类型转化 } }; template//string特化 struct HashFuncstring { size_t operator()(const string s) { size_t hash 0; for (auto ch : s) { hash ch; hash * 131;//减小冲突BKDR } return hash; } };四.哈希表的实现(哈希桶)大致结构跟开放地址法相似变的地方在于处理冲突的方式。因此重叠部分不一一赘述请参见上方开放地址。所以本节着重讲述处理冲突。1.变动为了实现挂载节点的效用哈希表(vector)被设计为指针数组:所以存储数据的责任就从HashDataK, V落到Node*指向的节点身上。2.挂载节点的细节首先利用除法散列法取模找映射找到映射位置后如果发生冲突就在该位置上对新节点执行插入头插尾插都可以这里以头插举例让newnode的下个节点指向当前头结点当前头结点的地址又位于哈希表(vector)里所以就有然后newnode接替称为新头结点因此让它的地址在哈希表里还要注意每插完一个节点负载因子会上升因此在负载因子为1时要进行扩容扩容方案①.复用Insert(拷贝)将旧表节点的_kv拿给新表,然后复用Insert的代码在新表中用_kv建一个新的节点并插在已计算好的新位置上。但有个问题交换完的新表(存着一开始旧表的数据)要执行析构_tables是vector类型因此有自己的析构函数系统会自动调用但vector里存的Node*是自定义类型需要去手动实现析构即便手动实现了也不能像系统类型的delete[]那样出现一次就可以释放所有链式结构这就意味这要一个个节点的调用析构这样的开销是极大的。扩容方案②.将旧表节点整个直接拿下来算一下节点在新表的位置然后将旧节点头插进新表该位置。头插先将位置里原有的东西拿出来放到待插入新节点后面然后新节点进入该位置。注意此处是用vectorNode*开新表没必要再去用Hashtable。我们下期见end请各位大佬不吝手中的三联哦。