C++ unordered_map和unordered_set的使用，哈希表的实现

unordered_map，unorder_set和map ，set的差异

unordered_map，unordered_set在功能方面和map，set基本一致
unordered_map和unordered_set底层是哈希表，遍历无序，查找删除修改的效率为O(1)
map和set底层是红黑树，遍历有序，查找删除修改的效率为O(logN)

1. 功能：迭代器之间也有差异，set是双向迭代器，unordered_set是单向迭代器，set底层是红黑树，走中序是有序的，所以迭代器的遍历是有序+去重，unordered_set底层是哈希表，迭代器遍历是无序+去重
2. 效率：unordered_set和set性能方面也有差异，set是O(logN),unordered_set是O(1)
3. 使用要求：对key的要求不同，set要求key支持小于的比较，unordered_set要求key转为整形且要支持等于的比较
4. unordered_set,unordered_map和map,set要求基本一致
5. unordered_multimap和unordered_multiset支持键值冗余（key冗余）
6. 效率上无序的比有序的总体上要好很多，但是在排有序的数的时候，有序的删除，插入比无序的效率高，但是查找效率还是无序的效率高
   

void set_test1()
{// 迭代器遍历set<int> s = { 3,1,6,7,8,2};set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}// 3 1 6 7 8 2cout << endl;
}int main()
{set_test1();return 0;
}

哈希表的实现

概念

• 哈希表也叫散列表，散列有散乱排列的意思。通过关键字Key跟存储位置建立一个映射关系

直接定址法

• 适合关键字的范围比较集中的，直接定址法是非常高效的方法。比如给’a’ - 'z’的小写字母为范围，通过直接映射或相对映射，关键字的值就是存储位置的下标，下面也有一道题是这样的。只适合整形，字符串，浮点数都不行

字符串中的第一个唯一字符

class Solution 
{
public:int firstUniqChar(string s) {int hash[26] = {0};for(auto ch : s){hash[ch - 'a']++;}    for(int i = 0;i < s.size();i++){if(hash[s[i] - 'a'] == 1)return i;}return -1;}
};

哈希冲突

• 直接定址法的缺点非常明显，当关键字比较分散时，会浪费空间甚至空间会不够用。当有N个值要映射到M个空间中（M >= N），就要借助哈希函数，关键字key要放到数组的h(key）的位置，h(key)计算的值要在[0,M)中。
• 哈希冲突也叫哈希碰撞，就是两个不同的key映射到同一个位置了，我们要设计一个哈希函数来减少哈希冲突，在实际问题中哈希冲突是不可避免的

哈希冲突举个例子

N == 100 M == 200,N个数要存到M个空间中
除法散列法：h(key) = key % M
哈希冲突：3 % 200 = 3，203 % 200 = 3

负载因子

哈希表中已经存了N个值，哈希表的大小为M,负载因子 = N/M,负载因子也叫装载因子/载荷因子，负载因子越大，哈希冲突越高，空间利用率越高，相反就越低。

将关键字转为整数

比如是浮点数转为整数或者有符号的整数（负数）要转为正数，字符串转为整数。

哈希函数

一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计。

除法散列法/除留余数法

• 除法散列表是最常用的，哈希表的大小为M,通过key除以M的余数作为映射的下标，h(key) = key % M
• 使用这个方法时要注意M不要为2的幂，10的幂等。如果是2^X，那么key%2 ^ X,相当于保留key的后X位，那么key的后X位相同的值就哈希冲突了。
• 比如63,31，如果M是16，2 ^ 4,计算出的哈希值都是15，00111111为63，00011111为31，后4位都是1111，所以会哈希冲突。10进制的，比如123和345123，如果M = 10 ^ 3,保留后三位，都是123,也哈希冲突。
• 当使用除留余数法时，建议M取不太接近2的整数次幂的一个质数
• %其实用到了除，除的效率比位运算的效率更低，所以Java中用了位运算

Java中用了2的整数次幂作为哈希表的大小M

哈希冲突的解决方法

开放定址法

• 开放定址法，哈希表是空的，把所有元素放到哈希表中，当关键字key用哈希函数找到了冲突位置，就按照某种规则去找一个没有存储数据的位置进行储存。这里有三种规则：线性探测，二次探测，双重探测

线性探测

现在给一组数据：
{19,30,5,36,13,20,21,12} 等这一组值映射到M=11的表中

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，
h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1

上面这组数据在8位置就冲突了

• 线性探测：从发生冲突的位置依次往后探测，直到找到一个没有存储数据的位置为止，如果走到哈希尾都没有找到，则回绕到哈希头继续往后找
• h(key) = hash0 = key % M , hash0位置冲突了，则线性探测公式为：hc(key, i) = hashi = (hash0 + i) % M， i = {1, 2, 3, …, M − 1}，因为负载因子必须小于1（因为要留一个位置不放数据，不然会出问题），则最多探测M-1次，一定能找到一个存储key的位置。
• 连续冲突：hash0位置连续冲突，（你占我的位置，我占你的位置）这种现象叫做 群集/堆积，二次探测可以改善这样的问题

二次探测

二次探测和线性探测非常类似
如果往左走回绕到哈希表尾，用减，比如3-9，到5的位置停下，-6 + M,M == 11, -6 + M = 5

// 二次探测
int flag = 1;
while (_tables[hashi]._state == EXIST)
{// 存在进行二次探测,删除和空就退出hashi = (hash0 + i*i*flag) % _tables.size();if (hashi < 0)hashi += _tables.size();if (flag == 1){flag = -1;}else{flag = 1;++i;}
}

开放定址法代码实现

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，
h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1
蓝色的四个位置连续冲突
查找的原则：遇到删除，存在才继续找，遇到空就结束查找
状态标识：存在，空和删除，空和删除可以放值，空就线性探测
要注意给每个存储值的位置加一个状态标识，否则删除一些值以后，会影响后面冲突的值的查找。
如下图，我们删除30，会导致查找20失败，当我们给每个位置加⼀个状态标识{EXIST,EMPTY,DELETE} ，删除30就可以不用删除值，而是把状态改为 DELETE ，那么查找20时是遇到 EMPTY 才能停止，就可以找到20。

哈希表的代码

#pragma once#include<vector>// 枚举状态
enum State
{EXIST,EMPTY,DELETE
};template<class K,class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K,class V>
class HashTable
{
public:// 构造HashTable()// 会取到53:_tables(__stl_next_prime(0)),// 11是数据个数()_n(0){}// 为了解决M是质数的问题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取表中大于等于first的数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){// 扩容//vector<HashTable<K, V>> newtables(_tables.size()*2);//for (auto& data : _tables)//{//	// 把旧表的数据映射到新表//	// 不能直接拷贝,因为映射关系还是原来的(会乱)//	if (data._state == EMPTY)//	{//		size_t hash0 = data._kv.first % newtables.size();//		// ...//	}//}//_tables.swap(newtables);// 上面的方法代码过于冗余// 把新表和旧表交换HashTable<K, V> newht;// newht._tables.resize(_table.size() * 2);newht._tables.resize(__stl_next_prime(_table.size()));for (auto& data : _tables){// 把旧表的数据映射到新表if (data._state == EMPTY){// 相当于递归newht.Insert(data._kv);}}// 函数结束,newht销毁,数据交换给旧表_tables.swap(newht._tables);}// key / M , M哈希表的空间大小size_t hash0 = kv.first % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._state == EXIST){// 存在进行线性探测,删除和空就退出hashi = (hash0 + i) % _tables.size();++i;}// 二次探测//int flag = 1;//while (_tables[hashi]._state == EXIST)//{//	// 存在进行二次探测,删除和空就退出//	hashi = (hash0 + i*i*flag) % _tables.size();//	if (hashi < 0)//		hashi += _tables.size();//	if (flag == 1)//	{//		flag = -1;//	}//	else//	{//		flag = 1;//		++i;//	}//}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}// 查找HashData<K, V>* Find(const K& key){size_t hash0 = key % _tables.size();size_t hashi = hash0;size_t i = 1;// Find等于空就找不到了while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}// 存在进行线性探测,删除和空就退出hashi = (hash0 + i) % _tables.size();++i;}return nullptr;}// 删除bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (key){ret->_state = DELETE;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n;// 记录哈希表中的数据个数
};#include"HashTable.h"int main()
{int a[] = { 19,30,5,36,13,20,21,12 };HashTable<int, int> ha;for (auto& e : a){ha.Insert({ e,e });}ha.Erase(20);if (ha.Find(30)){cout << "找到了" << endl;}if (ha.Find(20)){cout << "找到了" << endl;}else{cout << "没有找到" << endl;}return 0;
}