做qq游戏的视频秀网站/友情链接网

unordered_set/map和set/map的差异

unordered_set/map和set/map的第⼀个差异是对key的要求不同，set/map要求Key⽀持⼩于⽐较，而unordered_set/map要求Key⽀持转成整形且⽀持等于⽐较

unordered_set/map和set/map的第⼆个差异是迭代器的差异，set/map的iterator是双向迭代器，unordered_set/map是单向迭代器，其次set/map底层是红⿊树，红⿊树是⼆叉搜索树，中序遍历是有序的，所以set迭代器遍历是有序+去重。⽽unordered_set/map底层是哈希表，迭代器遍历是⽆序+去重。

unordered_set/map和set/map的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_set的增删 查改更快⼀些，因为红⿊树增删查改效率是 O(logN),⽽哈希表增删查平均效率是O(1)

由于unordered_map/set是用哈希表实现的，所以在实现unordered_map/set之前，我们需要先了解一下哈希表

哈希表

哈希(hash)⼜称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。

哈希函数

直接定址法

当关键字的范围⽐较集中时，直接定址法就是⾮常简单⾼效的⽅法，⽐如⼀组关键字值都在 [a,z]的⼩写字⺟，那么我们开⼀个26个数的数组，每个关键字acsii码-aascii码就是存储位置的下标。 也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。

直接定址法的缺点也⾮常明显，当关键字的范围⽐较分散时，就很浪费内存甚⾄内存不够⽤。假设有数据范围是[0,9999]的N个值，要映射到⼀个M个空间的数组中(⼀般情况下M>=N)，那么就要借助哈希函数(hashfunction)h，将关键字key映射到数组的h(key)位置（将关键字映射到数组时，要先将关键字转化为整数），这⾥要注意的是h(key)计算出的值必须在[0,M)之间。

除法散列法/除留余数法

假设哈希表的⼤⼩为M，那么通过key除以M的余数作为映射位置的下标，即：h(key)=key%M。

当使⽤除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是2的X次方，那么key%M本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就很容易冲突。

因此，当使⽤除法散列法时，建议M取不太接近2的整数次幂的⼀个质数(素数)。

不过也有例外：Java的HashMap采⽤除法散列法时M就是2的整数次幂（这样就可以直接位运算，⽽不⽤取模，更⾼效⼀些），但是他是取key的前16位和后16位并将二者异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围 内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀⼀些即可。

乘法散列法 

乘法散列法分两步：用关键字与一个常数A(0<A<1)相乘，将结果的小数部分再与M相乘并取整

即：h(key) = floor(M ×((A ×key)%1.0))

其中floor表⽰对表达式进⾏下取整，A∈(0,1)，这⾥最重要的是A的值应该如何设定，Knuth认为 A = 0.6180339887.... (⻩⾦分割点) ⽐较好。

乘法散列法对哈希表⼤⼩M是没有要求的，假设M为1024，key为1234，A=0.6180339887,A*key = 762.6539420558，取⼩数部分为0.6539420558, M×((A×key)%1.0)=0.6539420558*1024= 669.6366651392，那么h(1234)=669。

哈希冲突

通过哈希函数将key映射到一个数组时存在的⼀个问题：两个不同的key可能会映射到同⼀个位置去，这种问题我们叫做哈希冲突， 或者哈希碰撞。

理想情况是找出⼀个好的哈希函数来避免冲突，但是实际场景中，冲突是不可避免的,所以既要尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的⽅案。

负载因⼦

假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么N负载因⼦ =M 。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低

处理哈希冲突

实践中哈希表⼀般还是选择除法散列法作为哈希函数，当然哈希表⽆论选择什么哈希函数也避免不了冲突。那么插⼊数据时，如何解决冲突呢？主要有两种两种⽅法：开放定址法和链地址法。

开放定址法

在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按 照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测、⼆次探测

线性探测 ：

从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛ 到哈希表尾，则回绕到哈希表头的位置。

h(key) = hash0 = key % M ，hash0位置冲突了，则线性探测公式为：hc(key,i) = hashi =(hash0+i) % M ，i = {1,2,3,...,M −1} ，因为负载因⼦⼩于1， 则最多探测M-1次，⼀定能找到⼀个存储key的位置。

线性探测的⽐较简单且容易实现，但存在一个的问题：假设hash0位置连续冲突，且hash0，hash1， hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题

⼆次探测 ：

从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为 ⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表 尾的位置

h(key) = hash0 = key % M , hash0位置冲突了，则⼆次探测公式为：hc(key,i) = hashi = (hash0±i^2 ) % M ，  i = M {1,2,3,...,M/2 }

扩容

这⾥我们哈希表负载因⼦控制在0.7，当负载因⼦到0.7以后我们就需要扩容了，如果我们还是按照2倍扩容，那么扩容后哈希表的⼤⼩就不是⼀个质数了。⼀种解决⽅案是像JavaHashMap一样使⽤2的整数幂。另外⼀种⽅案是sgi版本的哈希表使⽤的⽅法，给了⼀个近似2倍的质数表，每次去质数表获取扩容后的⼤⼩。

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
};

链地址法

解决冲突的思路 

开放定址法中所有的元素都放到哈希表⾥，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储⼀个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下⾯，链地址法也叫做拉链法或者哈希桶。

扩容

开放定址法负载因⼦必须⼩于1，链地址法的负载因⼦就没有限制了，可以⼤于1。负载因⼦越⼤，哈 希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；stl中 unordered_xxx的最⼤负载因⼦基本控制在1，⼤于1就扩容，我们下⾯实现也使⽤这个⽅式。

key不能取模的问题

当key是string等类型时，key不能取模，那么我们需要给HashTable增加⼀个仿函数，这个仿函数把key转换成⼀个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数就⽤默认参数即可，如果这个Key不能转换为整形，我们就需要⾃⼰实现⼀个仿函数传给这个参数，实 现这个仿函数的要求就是尽量key的每值都参与到计算中，让不同的key转换出的整形值不同。由于string做哈希表的key⾮常常⻅，所以我们可以考虑把string特化⼀下。

​template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hashi = 0;for (auto ch : key){hashi *= 131;hashi += ch;}return hashi;}
};
​// 字符串转换成整形，可以把字符ascii码相加即可
// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
// 这⾥我们⽤上次的计算结果去乘⼀个质数(像31, 131这样的数效果比较好)

哈希表的实现

#include<vector>
#include<string>
using namespace std;namespace nexus
{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};inline unsigned long __stl_next_prime(unsigned long n){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);return pos == last ? *(last - 1) : *pos;}template<class K>struct HashFunc{size_t operator()(const K& key){return key;}};template<>struct HashFunc<string>{size_t operator()(const string& key){size_t hashi = 0;for (auto ch : key){hashi *= 131;hashi += ch;}return hashi;}};template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T, class KeyOfT, class Hash>class HashTable;template <class K, class T, class KeyOfT, class Hash,class PTR,class REF>struct HTIterator{typedef HashTable<K, T, KeyOfT, Hash> HashTable;typedef HashNode<T> Node;typedef HTIterator<K, T, KeyOfT, Hash,PTR,REF> Self;HTIterator(Node* node = nullptr, HashTable* ht = nullptr):_node(node), _ht(ht){}Self& operator++(){// 当前迭代器所指节点后还有节点时直接取其下一个节点if (_node->_next!=nullptr)_node = _node->_next;// 找下一个不空的桶，返回该桶中第一个节点else{Hash hs;KeyOfT kot;size_t next = hs(kot(_node->_data))%_ht->_tables.size() + 1;while (next < _ht->_tables.size()){if (_ht->_tables[next] != nullptr)break;next++;}if (next == _ht->_tables.size())_node = nullptr;else _node = _ht->_tables[next];}return *this;}Self operator++(int){Self tmp = *this;++*this;return tmp;}REF operator*() { return _node->_data; }PTR operator->() { return &(_node->_data); }bool operator==(const Self& it) const { return _node == it._node; }bool operator!=(const Self& it) const { return _node != it._node; }Node* _node;             // 当前迭代器关联的节点HashTable* _ht;         // 哈希桶--主要是为了找下一个空桶时候方便};// K 为 T 中key的类型// T 可能是键值对，也可能是K// KeyOfT: 从T中提取key// Hash将key转化为整形，因为哈希函数使用除留余数法template<class K, class T, class KeyOfT, class Hash=HashFunc<K>>class HashTable{template <class K, class T, class KeyOfT, class Hash,class PTR,class REF>friend struct HTIterator;public:typedef HashNode<T> Node;typedef HTIterator<const K, T, KeyOfT, Hash,T*,T&> Iterator; typedef HTIterator<const K, T, KeyOfT, Hash,const T*,const T&> Const_Iterator;public:HashTable(size_t size = __stl_next_prime(0)){_tables.resize(size, nullptr);}// 哈希桶的销毁~HashTable(){for (auto& e : _tables){Node* cur = e;while (cur){Node* tmp = cur->_next;delete cur;cur = tmp;}e = nullptr;}}Iterator Begin(){Node* tmp=nullptr;for (Node* e:_tables){tmp = e;if (tmp!=nullptr)break;}return { tmp,this };}Iterator End(){return { nullptr, this };}Const_Iterator Begin() const{Node* tmp = nullptr;for (Node* e : _tables){tmp = e;if (tmp != nullptr)break;}return { tmp,this };}Const_Iterator End()const{return { nullptr, this };}// 插入值为data的元素，如果data存在则不插入pair<Iterator,bool> Insert(const T& data){Iterator tmp_iterator = Find(kot(data));if (tmp_iterator!=End())return { tmp_iterator,false };if (_n == _tables.size()){HashTable newhashtable(__stl_next_prime(_tables.size() + 1));for (auto e : _tables){Node* tmp = e;while (tmp){newhashtable.Insert(tmp->_data);tmp = tmp->_next;}}swap(_tables, newhashtable._tables);}size_t pos = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);newnode->_next = _tables[pos];_tables[pos] = newnode;_n++;return {Iterator (newnode,this),true};}// 在哈希桶中查找值为key的元素，存在返回true否则返回falseIterator Find(const K& key){size_t pos = hs(key) % _tables.size();Node* tmp = _tables[pos];while (tmp){if (kot(tmp->_data) == key)return { tmp,this };tmp = tmp->_next;}return { nullptr,this };}// 哈希桶中删除key的元素Iterator Erase(Iterator& it){if (it == End())return it;Iterator next_it = it;next_it++;K key = kot(*it);size_t pos = hs(key) % _tables.size();if (kot(_tables[pos]->_data) == key){delete _tables[pos]; _tables[pos] = nullptr;}Node* tmp = _tables[pos];Node* parent = tmp;while (tmp){if (kot(tmp->_data) == key){parent->_next = tmp->_next;delete tmp;break;}parent = tmp;tmp = tmp->_next;}_n--;return next_it;}size_t size() { return _n; }bool Empty() { return _n == 0; }size_t Count(const K& key){if (Find(key) != End())return 1;return 0;}size_t TableCount(){return _tables.size();}size_t TableSize(size_t n){size_t count = 0;Node* tmp = _tables[n];while (tmp){count++;tmp = tmp->_next;}return count;}private:Hash hs;KeyOfT kot;vector<Node*> _tables;  // 指针数组size_t _n = 0;			// 表中存储数据个数};
}

unordered_set的实现

#include"hash.h"
namespace nexus
{// unordered_set中存储的是K类型，HF哈希函数类型template<class K, class Hash = HashFunc<K>>class unordered_set{// 通过key获取value的操作struct SetKeyOfT{const K& operator()(const K& data){return data;}};typedef HashTable<const K,const K, SetKeyOfT, Hash> HT;public:typename typedef HT::Iterator iterator;typename typedef HT::Const_Iterator const_iterator;public:unordered_set() : _ht(){}iterator begin() { return _ht.Begin(); }iterator end() { return _ht.End(); }const_iterator begin()const { return _ht.Begin(); }const_iterator end()const { return _ht.End(); }// capacitysize_t size()const { return _ht.size(); }bool empty()const { return _ht.Empty(); }/// lookupiterator find(const K& key) { return _ht.Find(key); }size_t count(const K& key) { return _ht.Count(key); }// modifypair<iterator, bool> insert(const K& key){return _ht.Insert(key);}iterator erase(iterator pos){return _ht.Erase(pos);}// bucketsize_t table_count() { return _ht.TableCount(); }size_t table_size(size_t n) { return _ht.TableSize(n); }private:HT _ht;};
}

unordered_map的实现

#include"hash.h"
namespace nexus
{// unordered_map中存储的是pair<K, V>的键值对，K为key的类型，V为value的类型，Hash哈希函数类型template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& data){return data.first;}};typedef HashTable<const K, pair<const K, V>, MapKeyOfT, Hash> HT;public:typename typedef HT::Iterator iterator;typename typedef HT::Const_Iterator const_iterator;public:unordered_map() : _ht(){}//iterator begin() { return _ht.Begin(); }iterator end() { return _ht.End(); }const_iterator begin()const { return _ht.Begin(); }const_iterator end()const { return _ht.End(); }//// capacitysize_t size()const { return _ht.size(); }bool empty()const { return _ht.Empty(); }//// AcessV& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert({ key, V() });return ret.first->second;}const V& operator[](const K& key)const{pair<iterator, bool> ret = _ht.Insert({ key, V() });return ret.first->second;}/// lookupiterator find(const K& key) { return _ht.Find(key); }size_t count(const K& key) { return _ht.Count(key); }// modifypair<iterator, bool> insert(const pair<K, V>& data){return _ht.Insert(data);}iterator erase(iterator pos){return _ht.Erase(pos);}// bucketsize_t table_count() { return _ht.TableCount(); }size_t table_size(size_t n) { return _ht.TableSize(n); }private:HT _ht;};
}