一.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%M
2-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 }; template<class K, class V> class HashData { pair<K, V> _kv; State _state = EMPTY;//用枚举造一个状态标，便于后续查找 }; template<class K,class V> class HashTable { private: vector<HashData<K, 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 pair<K, V>& kv) { if (Find(kv.first)) return false;//禁止冗余。 //负载因子>=0.7,扩容。 if (_n * 10 / _tables.size() >= 7)//由于除只保留整数，会影响精度，所以整体扩大10倍。 { HashTable<K, 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)无法使用“==”等操作符的问题
情景：
解决方案：
①.类型允许强制类型转化或者强转不影响相关操作的
用一个仿函数将无法执行相关操作的类型强制转化为无符号整型。
template<class 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,能将冲突的概率降到极低。
⑤.最终代码：
template<class K>//仿函数 struct HashFunc { size_t operator()(const K& key) { return (size_t)key;//强制类型转化 } }; template<>//string特化 struct HashFunc<string> { size_t operator()(const string& s) { size_t hash = 0; for (auto ch : s) { hash += ch; hash *= 131;//减小冲突，BKDR } return hash; } };四.哈希表的实现(哈希桶)
大致结构跟开放地址法相似，变的地方在于处理冲突的方式。因此重叠部分不一一赘述，请参见上方开放地址。所以本节着重讲述处理冲突。
1.变动
为了实现挂载节点的效用，哈希表(vector)被设计为指针数组:
所以存储数据的责任就从HashData<K, V>>，落到Node*指向的节点身上。
2.挂载节点的细节
首先利用除法散列法取模找映射，找到映射位置后，如果发生冲突，就在该位置上，对新节点执行插入，头插尾插都可以，这里以头插举例：
让newnode的下个节点指向当前头结点，当前头结点的地址又位于哈希表(vector)里，所以就有：
然后newnode接替称为新头结点，因此让它的地址在哈希表里：
还要注意，每插完一个节点，负载因子会上升，因此在负载因子为1时，要进行扩容：
扩容方案①.复用Insert(拷贝)
将旧表节点的_kv拿给新表,然后复用Insert的代码，在新表中用_kv建一个新的节点，并插在已计算好的新位置上。
但有个问题，交换完的新表(存着一开始旧表的数据)，要执行析构，_tables是vector类型，因此有自己的析构函数，系统会自动调用，但vector里存的Node*是自定义类型，需要去手动实现析构，即便手动实现了，也不能像系统类型的delete[]那样，出现一次，就可以释放所有链式结构，这就意味这要一个个节点的调用析构，这样的开销是极大的。
扩容方案②.将旧表节点整个直接拿下来
算一下节点在新表的位置，然后将旧节点头插进新表该位置。
头插：先将位置里原有的东西拿出来，放到待插入新节点后面，然后新节点进入该位置。
注意，此处是用vector<Node*>开新表，没必要再去用Hashtable。
我们下期见
end
请各位大佬不吝手中的三联哦。
