个人主页 ： zxctscl
如有转载请先通知

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$lo{g}_{2}N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，这次对unordered_map和unordered_set进行介绍。

哈希是无序的，但是map和set是有序的，unordered_map和unordered_set无序。

1.1 unordered_map

1.1.1 unordered_map的文档介绍

有需要了解的可以点这个链接： unordered_map的文档说明

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
6. 它的迭代器至少是前向迭代器。

1.1.2 unordered_map的接口说明

1. unordered_map的构造
   
   

2. unordered_map的容量
   

3. unordered_map的迭代器
   unordered_map的迭代器是单项的
   

4. unordered_map的元素访问

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。

5. unordered_map的查询
   
   注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

6. unordered_map的修改操作
   

7. unordered_map的桶操作
   

来利用 unordered_map统计一下次数：

void test_map1()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;
}

那么 unordered_map统计次数，和map统计次数有什么区别呢？
map底层是红黑树，是有序的，按这水果中文的字典序去排序的。
unordered_map是无序的。

1.2 unordered_set

有需要了解的可以点这个链接： unordered_set的文档说明

1. unordered_set的构造
   

2. unordered_set的容量
   

3. unordered_set的迭代器
   这里迭代器是单项的
   

4. unordered_set的元素访问
   

5. unordered_set的修改操作
   

unordered_set是无序的，来个代码看看：

void test_set1()
{unordered_set<int> s = { 3,1,7,8,2 };unordered_set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;	}cout << endl;
}

比较unordered_set和set的插入查找删除的效率：

int test_set2()
{const size_t N = 10000000;unordered_set<int> us;set<int> s;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; ++i){//v.push_back(rand()); // N比较大时，重复值比较多//v.push_back(rand()+i); // 重复值相对少v.push_back(i); // 没有重复，有序}size_t begin1 = clock();for (auto e : v){s.insert(e);}size_t end1 = clock();cout << "set insert:" << end1 - begin1 << endl;size_t begin2 = clock();for (auto e : v){us.insert(e);}size_t end2 = clock();cout << "unordered_set insert:" << end2 - begin2 << endl;int m1 = 0;size_t begin3 = clock();for (auto e : v){auto ret = s.find(e);if (ret != s.end()){++m1;}}size_t end3 = clock();cout << "set find:" << end3 - begin3 << "->" << m1 << endl;int m2 = 0;size_t begin4 = clock();for (auto e : v){auto ret = us.find(e);if (ret != us.end()){++m2;}}size_t end4 = clock();cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;cout << "插入数据个数：" << s.size() << endl;cout << "插入数据个数：" << us.size() << endl << endl;size_t begin5 = clock();for (auto e : v){s.erase(e);}size_t end5 = clock();cout << "set erase:" << end5 - begin5 << endl;size_t begin6 = clock();for (auto e : v){us.erase(e);}size_t end6 = clock();cout << "unordered_set erase:" << end6 - begin6 << endl << endl;return 0;
}

重复值比较多的时候：

重复值相对少：

没有重复，有序

2. 底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

2.1 哈希概念

什么是哈希呢？
哈希是一种映射。
映射就是值和值之间的关联。
哈希表：哈希思想实现的数据结构

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($lo{g}_{2}N$)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

值和位置直接或间接映射，会导致两个问题，一个是值很分散，另一个是值不好映射，比如string或者结构体对象。

举个例子：一组数据集合10001，11,55,24,19，放在10个空间中。
除留余数法：hash(key) = key % capacity; capacity为存储元素底层空间总的大小，这样值很分散的问题就解决了，空间根值的范围有关系。

利用除留余数法进行之后是这样的：

此时就产生了哈希冲突/碰撞：不同的值放可能会映射到相同的位置。

2.2 哈希冲突

对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) ==Hash($k_j$)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

2.3 哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

2.3.1 闭散列

思路：就是我的位置被人占了，我就去抢别人的位置。

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

2.3.1.1 线性探测

1. 线性探测
   线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

比如上面中的场景，现在需要插入元素12，先通过哈希函数计算哈希地址，hashAddr为2，因此12理论上应该插在现在11位置，但是该位置已经放了值为11的元素，即发生哈希冲突。

插入：
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

现在需要插入元素31，先通过哈希函数计算哈希地址，hashAddr为1，因此31理论上应该插在现在10001位置，但是该位置已经放了值为10001的元素，31只能向后探测，直到找到空位置插入进去。

删除：采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。

如果要删除值，就得先查找，找不到的遇到空才能停止。

这里先删除55

在删除55后，再查找31，会出现什么？
31映射的位置是1，此时从10001位置开始找，一直找到24后面的空。就会出现31是存在，但就是找不到。

那么怎么解决这个问题呢？
可以加一个状态标记来解决，没有值就为空，放了值就存在，删了值就是删除。

enum State
{EMPTY,EXIST,DELETE
};

哈希表什么情况下进行扩容？如何扩容？

扩容时，不能直接将原有的数据直接拷贝下来，而是在新扩容的空间内重新映射。

当10扩容到20时，数据的映射：

扩容到原来的两倍，旧表的数据重新计算到新表，如果是vector就得重新一个一个计算，但如果用哈希表对象HashTable<K, V> newHT;，就直接赋用。

//扩容if (_n*10 / _tables.size() >= 7){//size_t newsize = _tables.size() * 2;//vector<HashData<K, V>> newtables(newsize);旧表重新计算到新表//for (size_t i = 0; i < tables.size(); i++){}size_t newsize = _tables.size() * 2;HashTable<K, V> newHT;newHT._tables.resize(newsize);//旧表重新计算到新表for (size_t i = 0; i < tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables)；}

那么怎么解决其他类型不能取模的问题？
此时可以再建立一层哈希。哈希是值和存储位置建立映射关系，如果是int就直接能用取模；如果是string，不能直接取模，可以考虑把srring转化为int，再用int去建立映射关系。

那么怎么用代码来实现呢？
这里是泛型，就可以用到仿函数，只要能使用隐式类型转换，就能用：

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};

但是string不能转成整形，此时单独写一个string转成整形：
就是key不支持强转整形取模，那么就要自己提供转化为整形的仿函数。

template<>
struct HashFunc<string>
{size_t operator()(const string& key){return key[0];}
};

库里面也是有这样的仿函数：

但是这样写的转换不好，如果两个字符串首字母一样就冲突了。
可以考虑遍历这个string再把它的ASCII码值加起来：

template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash += ch;}return hash;}
};

但是这样的代码还是有缺陷，像 abcd，bcad，aadd，BKDR他们的ASCII码值相加起来都一样。所以每次结果都乘以131，再加，结果就不会一样。
为什么是131，可以看看下面这个链接： 字符串Hash函数对比

这里用一个特化，不是特化类型就走上面那个，是特化类型就走这个。

template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};

那么是否还会存在冲突呢？
还是有的。

线性探测优点：实现非常简单。
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

2. 二次探测
   线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：$H_i$ = ($H_0$ + $i^2$ )% m, 或者：$H_i$ = ($H_0$ - $i^2$ )% m。其中：i =1,2,3…， $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷

2.3.1.2 线性探测实现代码

#pragma once
#include<vector>template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 特化
template<>
struct HashFunc<string>
{// abcd// bcad// aadd// BKDRsize_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};namespace open_address
{enum State{EMPTY,EXIST,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};struct StringHashFunc{// abcd// bcad// aadd// BKDRsize_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable(){_tables.resize(10);}bool Insert(const pair<K,V>& kv){if (Find(kv.first))return false;// 扩容if (_n * 10 / _tables.size() >= 7){//size_t newsize = _tables.size() * 2;//vector<HashData<K, V>> newtables(newsize); 旧表重新计算负载到新表//for (size_t i = 0; i < _tables.size(); i++)//{}HashTable<K, V, Hash> newHT;newHT._tables.resize(_tables.size() * 2);// 旧表重新计算负载到新表for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hs;size_t hashi = hs(kv.first) % _tables.size();// 线性探测while (_tables[hashi]._state == EXIST){++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();// 线性探测while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST &&_tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;--_n;return true;}}private:vector <HashData<K, V>> _tables;size_t _n = 0;  // 有效数据个数};

2.3.2 哈希桶/拉链法

2.3.2.1 哈希桶

是用不带头单链表还是带头单链表？
用不带头的，能少一个节点是一个。

那么数据是选择头插，还是尾插？
头插，尾插的话，找尾麻烦。
比如：新插入节点是15
15先映射到对应位置，先让15指向55，再把15变成新的头节点（新节点指向头，再变成头）。

			size_t hashi = kv.first % _tables.size();Node* newnode = new Node(kv);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;

2.3.2.2 哈希桶代码实现

	template<class K, class T, class KeyOfT, class Hash>class HashTable{typedef HashNode<T> Node;public:// 友元声明/*template<class K, class T, class KeyOfT, class Hash>friend struct __HTIterator;*/// 内部类template<class Ptr, class Ref>struct __HTIterator{typedef HashNode<T> Node;typedef __HTIterator Self;Node* _node;const HashTable* _pht;__HTIterator(Node* node, const HashTable* pht):_node(node), _pht(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_next){// 当前桶没走完，找当前桶的下一个节点_node = _node->_next;}else{// 当前桶走完了，找下一个不为空的桶的第一个节点KeyOfT kot;Hash hs;size_t i = hs(kot(_node->_data)) % _pht->_tables.size();++i;for (; i < _pht->_tables.size(); i++){if (_pht->_tables[i])break;}if (i == _pht->_tables.size()){// 所有桶都走完了，最后一个的下一个用nullptr标记_node = nullptr;}else{_node = _pht->_tables[i];}}return *this;}bool operator!=(const Self& s){return _node != s._node;}};typedef __HTIterator<T*, T&> iterator;typedef __HTIterator<const T*, const T&> const_iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){// this -> HashTable*return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){// this -> const HashTable*return const_iterator(cur, this);}}return end();}const_iterator end() const{return const_iterator(nullptr, this);}HashTable(){_tables.resize(10, nullptr);_n = 0;}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}pair<iterator, bool> Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it != end())return make_pair(it, false);Hash hs;// 扩容// 负载因子为1时扩容if (_n == _tables.size()){//HashTable<K, V> newHT;//newHT._tables.resize(_tables.size() * 2); 旧表重新计算负载到新表//for (size_t i = 0; i < _tables.size(); i++)//{//	Node* cur = _tables[i];//	while (cur)//	{//		newHT.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newHT._tables);vector<Node*> newTables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 头插新表的位置size_t hashi = hs(kot(cur->_data)) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return end();}bool Erase(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){// 删除的是第一个if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<Node*> _tables; // 指针数组size_t _n;//vector<list<pair<K, V>>> _tables;};
}

2.3.3 开散列

开散列概念
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

开散列中每个桶中放的都是发生哈希冲突的元素

开散列实现：

template<class V>
struct HashBucketNode
{HashBucketNode(const V& data): _pNext(nullptr), _data(data){}HashBucketNode<V>* _pNext;V _data;
};
// 本文所实现的哈希桶中key是唯一的
template<class V>
class HashBucket
{typedef HashBucketNode<V> Node;typedef Node* PNode;
public:HashBucket(size_t capacity = 3) : _size(0){_ht.resize(GetNextPrime(capacity), nullptr);}// 哈希桶中的元素不能重复PNode* Insert(const V& data){// 确认是否需要扩容。。。元素(data不会重复)，返回删除元素的下一个节点PNode* Erase(const V & data){size_t bucketNo = HashFunc(data);PNode pCur = _ht[bucketNo];PNode pPrev = nullptr, pRet = nullptr;while (pCur){if (pCur->_data == data){if (pCur == _ht[bucketNo])_ht[bucketNo] = pCur->_pNext;elsepPrev->_pNext = pCur->_pNext;pRet = pCur->_pNext;delete pCur;_size--;return pRet;}}return nullptr;}PNode* Find(const V & data);size_t Size()const;bool Empty()const;void Clear();bool BucketCount()const;void Swap(HashBucket<V, HF>&ht;~HashBucket();private:size_t HashFunc(const V & data){return data % _ht.capacity();}private:vector<PNode*> _ht;size_t _size; // 哈希表中有效元素的个数}；

开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

void _CheckCapacity(){size_t bucketCount = BucketCount();if (_size == bucketCount){HashBucket<V, HF> newHt(bucketCount);for (size_t bucketIdx = 0; bucketIdx < bucketCount; ++bucketIdx){PNode pCur = _ht[bucketIdx];while (pCur){// 将该节点从原哈希表中拆出来_ht[bucketIdx] = pCur->_pNext;// 将该节点插入到新哈希表中size_t bucketNo = newHt.HashFunc(pCur->_data);pCur->_pNext = newHt._ht[bucketNo];newHt._ht[bucketNo] = pCur;pCur = _ht[bucketIdx];}}newHt._size = _size;this->Swap(newHt);}}