一、unordered系列关联式容器

在C++98中，STL提供了以红黑树为底层数据结构的关联式容器（map、set等），查询时的效率可以达到,最差情况下需要比较红黑树的高度次。因此在C++11中，STL提供了四个unordered系列关联式容器，与红黑树的结构类似，但是底层结构不同。其中unordered意为无序

1.unordered_map

在unordered_map中，键值通常用于唯一标识元素，而映射值是具有与此键关联的内容的对象。键和映射值的类型可能不同。内部不会对键值或映射值进行排序，而是根据哈希值存储在桶内，并且按照键值直接快速访问单个元素（平均时间复杂度恒定）

unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问 value.

unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低

函数名称	功能说明
bool empty() const	检测unordered_map是否为空
size_t size() const	返回unordered_map的有效元素个数
operator[]	返回key对应的value值，如果无匹配key则插入该新元素
at	返回unordered_map中key对应的value值，如果无匹配key则引发异常
size_t bucket_count() const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n) const	返回n号桶中有效元素的总个数
size_t bucket(const K& key)	返回元素key所在的桶号

2.unordered_set

在unordered_set中，元素的值同时也是键值。键值是不可以改变的。unordered_set中的元素不可以修改，但是可以插入和删除

unordered_set中的元素不按照任何特定顺序排序，根据哈希值存储在桶中

函数名称	功能说明
operator=	销毁原有unordered_set对象中的元素，并替换
pair<iterator,bool> emplace()	构造和插入元素。只有原对象没有该元素才会插入
size_t bucket_count() const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n) const	返回n号桶中有效元素的总个数
size_t bucket(const K& key)	返回元素key所在的桶号
rehash()	设置桶的个数

二、性能对比

运行下述测试代码可以看出

对于有序数据来说，set和map的插入性能更优，删除性能也更优

对于随机部分重复数据来说，两者差距不大

对于随机大量重复数据来说，unordered插入性能更优

综合各种场景unordered系列性能更优，尤其是find方面查找非常迅速

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <vector>
#include <time.h>
using namespace std;void test_unordered_set1()
{unordered_set<int> s;s.insert(1);s.insert(3);s.insert(2);s.insert(7);s.insert(2);unordered_set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;
}void test_unordered_set2()
{const size_t N = 100000;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());//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;size_t begin3 = clock();for (auto e : v){s.find(e);}size_t end3 = clock();cout << "set find:" << end3 - begin3 << endl;size_t begin4 = clock();for (auto e : v){us.find(e);}size_t end4 = clock();cout << "unordered_set find:" << end4 - begin4 << endl << 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;
}void test_unordered_map()
{string arr[] = { "电脑", "平板", "电脑", "平板", "电脑", "电脑", "平板", "电脑", "手机", "电脑", "手机", "平板" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}int main()
{test_unordered_map();//test_unordered_set1();//test_unordered_set2();return 0;
}

三、底层结构

由于树形搜索最优时间复杂度为，因此理想的搜索方法是不经过任何比较，直接一次从表中获取搜索的元素。由此寻找一种函数使得元素的存储位置与其关键字值能够建立一一映射的关系。这种方法就叫做哈希方法，使用的函数称为哈希函数，构造的结构叫做哈希表（散列表）

1.哈希函数 

对于不同的关键字值使用同一个哈希函数，可能计算出相同的哈希地址，这种现象称为冲突。引起哈希冲突可能是由于哈希函数设置的不合理，因此有以下哈希函数设计规则

哈希函数设计原则：

·哈希函数的定义域必须包括需要存储的全部关键字值。假设哈希表有m个地址，则值域必须在0到m-1之间

·哈希函数计算后关键字值能尽量均匀的分布在整个空间内

·哈希函数需要简单明了

常见的哈希函数包括除留余数法、直接定址法等

①直接定址法：取关键字的某个线性函数为散列函数，比如 h(key)=A*key+B。这种方法简单，分布均匀。但是需要事先知道关键字的分布情况，适合查找比较小且连续的情况

②除留余数法：h(key)=key mod M。M一般为散列表的长度，M的取值十分重要，M选取不当可能造成严重冲突。如果key是十进制数，则M应当避免取10的幂。一般而言，选择一个不超过M的最大的素数P

③平方取中法：这个方法是先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。比较适合不知道关键字的分布，而位数又不是很大的情况

④折叠法：折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位），并按照散列表的长度，取最后级位作为散列地址。适合不知道关键字分布，二关键字位数比较多的情况

⑤随机数法：选择一个随机函数，取关键字的随机函数值作为哈希地址。通常适用关键字长度不等的情况

⑥数学分析法：设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定 相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散 列地址。只适合处理关键字位数比较大，知道关键字分布并且若干位分布均匀的情况

哈希函数设计的越精妙，产生哈希冲突的可能性越低，但是哈希冲突不可被避免

2.哈希冲突解决

首先引入概念负载因子：负载因子=表中存储元素个数 / 哈希表长度。负载因子越接近一，说明元素越多，冲突的可能性越大

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，因此可以将key存放在冲突位置的下一个位置中

寻找下一个位置的方法包括：线性探测、二次探测

 线性探测程序实现

#pragma once
//线性探测 哈希表
#include<vector>
#include<iostream>
using std::make_pair;
using std::endl;
using std::cout;
using std::pair;
using std::vector;namespace my_hashtable
{enum State{EMPTY,EXIST,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K,class V>class HashTable{public:bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}//负载因子超过0.7就扩容if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newht;newht._tables.resize(newsize);//新表大小等于扩容后大小//遍历旧表，映射到新表for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}this->_tables.swap(newht._tables);}//线性探测size_t hashi = kv.first % _tables.size();//如果是capacity可能会越界size_t i = 1;size_t index = hashi;while (_tables[index]._state == EXIST){index = hashi + i;index %= _tables.size();//取模防止越界i++;}_tables[index]._kv = kv;_tables[index]._state = EXIST;_n++;return true;}HashData<K,V>* Find(const K& key){if (_tables.size() == 0){return nullptr;}size_t hashi = key % _tables.size();//线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY){if (_tables[index]._state == EXIST && _tables[index]._kv.first == key){return &_tables[index];}index = hashi + i;index %= _tables.size();i++;if (index == hashi)//已经寻找一圈说明所有位置都是存在或删除状态{break;}}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;_n--;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n = 0;//存储的数据个数};void testHashTable1(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(15, 15));if (ht.Find(13)){cout << "13在" << endl;}else{cout << "13不在" << endl;}ht.Erase(13);if (ht.Find(13)){cout << "13在" << endl;}else{cout << "13不在" << endl;}}
}

开散列

开散列：也叫拉链法，对key值通过散列函数计算散列地址，具有相同地址的key属于同一个子集，每个子集被称为一个桶。每个桶中的元素通过一个单链表链接，各个链表的头节点存储在哈希表中

拉链法程序实现

#pragma once
//拉链法 哈希表
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;namespace my_HashBucket
{template<class K, class V>struct HashNode{HashNode<K, V>* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_next(nullptr), _kv(kv){}};template<class K, class V>class HashTable{typedef HashNode<K, V> Node;public:~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}Node* Find(const K& key){if (_tables.size() == 0){return nullptr;}//定位哈希表中位置size_t hashi = key % _tables.size();Node* cur = _tables[hashi];//在位置上的vector中查找while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){size_t hashi = key % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == 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;}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}//负载因子为1时 扩容if (_n == _tables.size()){size_t newsize = _tables.size() == 0?10 : _tables.size() * 2;vector<Node*> newtables(newsize, nullptr);for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = cur->_kv.first % newtables.size();//头插进新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = kv.first % _tables.size();//头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}private:vector<Node*> _tables;//指针数组size_t _n = 0;//存储有效数据个数};void TestHashBucket1(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(15, 15));ht.Insert(make_pair(25, 25));ht.Insert(make_pair(35, 35));ht.Insert(make_pair(45, 45));}void TestHashBucket2(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Erase(12);ht.Erase(3);ht.Erase(33);}
}

问题分析

上面的两种程序实现都采用int类型进行测试，但是实际上哈希表中也可以存储字符串类型。当带入字符串类型进行测试时，会发现

size_t hashi = kv.first % _tables.size();

这样的取余定位方法会报错。如果一直只插入string类型数据，则可以将代码改成如下形式

size_t hashi = kv.first[1] % _tables.size();

但这样就达不到泛型编程的要求，因此需要增加模板参数使其应用场景更加广泛

因此需要修改成如下所示的代码

四、哈希表程序实现

 KV模型

#pragma once
//拉链法 哈希表
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::string;namespace my_HashBucket
{template<class K>struct HashFunc//将double之类的可以直接转换成int类型的数据进行转换{size_t operator()(const K& key){return key;}};//特化 用于处理字符串转整形template<>struct HashFunc<string>{//如果传入空字符串就会报错//size_t operator()(const string& s)//{//	return s[0];//}size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){//计算方式通过数学统计效率得知hash += ch;hash *= 31;}return hash;}};template<class K, class V>struct HashNode{HashNode<K, V>* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_next(nullptr), _kv(kv){}};template<class K, class V,class Hash=HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}Node* Find(const K& key){if (_tables.size() == 0){return nullptr;}//定位哈希表中位置Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];//在位置上的vector中查找while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hash;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == 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;}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}//负载因子为1时 扩容if (_n == _tables.size()){size_t newsize = _tables.size() == 0?10 : _tables.size() * 2;vector<Node*> newtables(newsize, nullptr);for (auto& cur : _tables){while (cur){Node* next = cur->_next;Hash hash;size_t hashi = hash(cur->_kv.first) % newtables.size();//头插进新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}Hash hash;size_t hashi = hash(kv.first) % _tables.size();//头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}private:vector<Node*> _tables;//指针数组size_t _n = 0;//存储有效数据个数};
}

泛型模型

1.仿函数 用于实现将其他类型参数转换为整型参数

2.HashNode结构体 节点保存数据与下一个节点位置

3._HashIterator结构体 迭代器结构体包括哈希表节点与哈希表

4.HashTable结构体 包括哈希表的增删查改功能，迭代器操作。其中Map式对KV模型进行操作 因此返回的都是键值对

#pragma once
//拉链法 哈希表
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::string;template<class K>
struct HashFunc
{size_t operator()(const K& key){return key;}
};// 特化
template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}
};namespace my_HashBucket
{template<class T>struct HashNode{HashNode<T>* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}};//前置声明template<class K, class T, class KeyOfT, class Hash>class HashTable;//哈希表迭代器template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash >struct _HashIterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef _HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;typedef _HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;Node* _node;const HT* _ht;_HashIterator(Node* node, const HT* ht):_node(node), _ht(ht){}_HashIterator(const Iterator& it):_node(it._node), _ht(it._ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){if (_node->_next != nullptr){_node = _node->_next;}else//寻找不为空的桶{KeyOfT kot;Hash hash;//定位当前桶的位置size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();hashi++;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{hashi++;}}//没找到if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};template<class K, class T, class KeyOfT, class Hash>class HashTable{template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct _HashIterator;typedef HashNode<T> Node;public:typedef _HashIterator<K, T, T&, T*, KeyOfT, Hash> iterator;typedef _HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}//迭代器iterator begin(){Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); i++){cur = _tables[i];if (cur){break;}}return iterator(cur, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin()const{Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); i++){cur = _tables[i];if (cur){break;}}return const_iterator(cur, this);}const_iterator end()const{return const_iterator(nullptr, this);}//接口函数iterator Find(const K& key){if (_tables.size() == 0){return end();}//定位哈希表中位置KeyOfT kot;Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];//在位置上的vector中查找while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return end();}bool Erase(const K& key){Hash hash;KeyOfT kot;size_t hashi = hash(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;}pair<iterator, bool> Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it != end()){return make_pair(it, false);//找到了}Hash hash;//负载因子为1时 扩容if (_n == _tables.size()){//size_t newsize = _tables.size() == 0?10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());vector<Node*> newtables(newsize, nullptr);for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newtables.size();//头插进新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kot(data)) % _tables.size();//头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return make_pair(iterator(newnode, this), false);}size_t GetNextPrime(size_t prime)//每扩容一次就更新模值{// SGIstatic 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};size_t i = 0;for (; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];}size_t MaxBucketSize(){size_t max = 0;for (size_t i = 0; i < _tables.size(); ++i){auto cur = _tables[i];size_t size = 0;while (cur){++size;cur = cur->_next;}//printf("[%d]->%d\n", i, size);if (size > max){max = size;}}return max;}private:vector<Node*> _tables;//指针数组size_t _n = 0;//存储有效数据个数};
}

五、unorderedMap封装

#pragma once#include"HashBucket.h"namespace my_unorderedMap
{template<class K,class V,class Hash=HashFunc<K>>class unordered_map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename my_HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;typedef typename my_HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin()const{return _ht.begin();}const_iterator end()const{return _ht.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:my_HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_unordered_map1(){unordered_map<int, int> m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));unordered_map<int, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;}void test_unordered_map2(){string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}
}

六、unorderedSet封装

#pragma once
#include"HashBucket.h"namespace my_unorderedSet
{template<class K,class Hash=HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename my_HashBucket::HashTable<K, K, SetKeyOfT, Hash>::iterator iterator;typedef typename my_HashBucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin()const{return _ht.begin();}const_iterator end()const{return _ht.end();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}bool erase(const K& key){return _ht.Erase(key);}iterator find(const K& key){return _ht.Find(key);}private:my_HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht;};void print(const unordered_set<int>& s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;}void test_unordered_set1(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };unordered_set<int> s;for (auto e : a){s.insert(e);}s.insert(54);s.insert(107);unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;print(s);}
}