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

文章目录 unordered_map，unorder_set和map ，set的差异哈希表的实现概念直接定址法哈希冲突哈希冲突举个例子 负载因子将关键字转为整数哈希函数除法散列法/除留余数法 哈希冲突的解决方法开放定址法线性探测二次探测 开放定址法代码实现 哈希表的代码

unordered_map，unorder_set和map ，set的差异

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

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