unordered系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到l o g 2 N log_2Nlog2N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。
最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是
其底层结构不同。
unordered_set与unordered_map
template < class Key, // unordered_set::key_type/value_type
class Hash = hash, // unordered_set::hasher
class Pred = equal_to, // unordered_set::key_equal
class Alloc = allocator // unordered_set::allocator_type
class unordered_set;
#include<iostream> #include<unordered_set> using namespace std; int main() { unordered_set<int>us; us.insert(3); us.insert(4); us.insert(2); us.insert(3); us.insert(0); for (auto e : us) { cout << e << " "; } cout << endl; return 0; }
这里是无序的。
template < class Key, // unordered_map::key_type
class T, // unordered_map::mapped_type
class Hash = hash, // unordered_map::hasher
class Pred = equal_to, // unordered_map::key_equal
class Alloc = allocator< pair<const Key,T> > // unordered_map::allocator_type
class unordered_map;
set VS unordered_set
这里用几组测试用例来看看它们的各大接口效率。
插入效率
#include<iostream> #include<unordered_set> #include<set> #include<vector> #include<ctime> using namespace std; int main() { const size_t N = 100000; unordered_set<int>arr1; set<int>arr2; vector<int>arr; arr.reserve(N); srand(time(0)); for (int i = 0; i < N; i++) { arr.push_back(rand()); } size_t begin1 = clock(); for (auto e : arr) { arr1.insert(e); } size_t end1 = clock(); size_t begin2 = clock(); for (auto e : arr) { arr2.insert(e); } size_t end2 = clock(); cout << "unordered_set:" << end1 - begin1 << endl; cout << "set:" << end2 - begin2 << endl; }
这里set更慢一些，因为插入的是随机值，如果是有序的，set速度会比unordered_set更快一些。
查找效率
#include<iostream> #include<unordered_set> #include<set> #include<vector> #include<ctime> using namespace std; int main() { const size_t N = 100000; unordered_set<int>arr1; set<int>arr2; vector<int>arr; arr.reserve(N); srand(time(0)); for (int i = 0; i < N; i++) { arr.push_back(rand()); } size_t begin1 = clock(); for (auto e : arr) { arr1.insert(e); } size_t end1 = clock(); size_t begin2 = clock(); for (auto e : arr) { arr2.insert(e); } size_t end2 = clock(); cout << "unordered_set:" << end1 - begin1 << endl; cout << "set:" << end2 - begin2 << endl; size_t begin3 = clock(); for (auto e : arr) { arr1.find(e); } size_t end3 = clock(); size_t begin4 = clock(); for (auto e : arr) { arr2.find(e); } size_t end4 = clock(); cout << "unordered_set:" << end3 - begin3 << endl; cout << "set:" << end4 - begin4 << endl; }
把数组里面的数再多加一点，变成一百万。
这里就算set里面是最平衡的数据（插入的时候都是有序数组），查找的效率也是不如unordered_set。
删除效率
#include<iostream> #include<unordered_set> #include<set> #include<vector> #include<ctime> using namespace std; int main() { const size_t N = 1000000; unordered_set<int>arr1; set<int>arr2; vector<int>arr; arr.reserve(N); srand(time(0)); for (int i = 0; i < N; i++) { arr.push_back(rand()); } size_t begin1 = clock(); for (auto e : arr) { arr1.insert(e); } size_t end1 = clock(); size_t begin2 = clock(); for (auto e : arr) { arr2.insert(e); } size_t end2 = clock(); cout << "unordered_set:" << end1 - begin1 << endl; cout << "set:" << end2 - begin2 << endl; size_t begin3 = clock(); for (auto e : arr) { arr1.find(e); } size_t end3 = clock(); size_t begin4 = clock(); for (auto e : arr) { arr2.find(e); } size_t end4 = clock(); cout << "unordered_set:" << end3 - begin3 << endl; cout << "set:" << end4 - begin4 << endl; size_t begin5 = clock(); for (auto e : arr) { arr1.erase(e); } size_t end5 = clock(); size_t begin6 = clock(); for (auto e : arr) { arr2.erase(e); } size_t end6 = clock(); cout << "unordered_set:" << end5 - begin5 << endl; cout << "set:" << end6 - begin6 << endl; }
如果是有序的话，set会更快。
总结：对于查找来说，unordered系列的查找是最快的。
底层结构
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。
哈希概念与哈希冲突
哈希映射：key值跟储存位置建立关联关系。（类似于计数排序一样）
但是这种方式有一个很大的问题，如果最小值和最大值差距非常大，那么值就会非常分散，并且会消耗很大的空间。
这个方法叫做：直接定址法。（一般适用于范围集中的一组值）
如果遇到那种一组值大小分散的很大，就用除留余数法：
1 10 55 3 6 88 123 1234
这里给了8个值，我们开辟10个空间就够了，然后让这组数%10就能找到值的相对位置。
但是这里就会有新问题，123%10=3，与数组里面的3相同，那么3的位置应该放哪一个？
这里就叫做哈希冲突，不同的值映射到相同的位置。
哈希冲突的解决
闭散列——开放定址法
如果映射的位置已经有值了，那么就按照某种规律找其他位置。
这里123%10等于3，但是下标为3的位置已经被占用了，所以只能向后找位置，发现下标为4的位置没有被占用，后续的1234插入的时候发现下标为4的位置被占用了，就向后找没被占用位置的位置。
但是如果冲突很多，查找的效率就会降低。
线性探测：
如果我们要找1234这个值是否存在，先让1234%10，然后到4下标找，发现不是1234这个值，那么就向后继续找，最后在下标为7的位置找到1234。
如果要找66这个值，先从下标为6的地方找，然后继续往后找，但是走到下标为9的时候，发现为空，那么这里久没必要在进行查找了，说明没有此值。
如何删除一个值
如果想删除哈希表中的一个值，搜狐先不能牵动哈希表中的任何值，如果移动了其他值就会导致原本在正确位置上的值变得不正确，查找就可能会出问题：不移动只是删除然后变成空也不行，因为查找的时候遇到空停下，那么这个时候删除的这个位置后面的值就有可能无法被查找到了。
这个时候的解决办法就是：
给每个数组中元素都设置三个状态——空，删除，存在
闭散列的实现
首先考虑要给问题，扩容。
什么时候扩容最合适？肯定不是满了在扩容，有一个叫做负载因子（载荷因子）= 表中有效数据的个数/表的大小。
负载因子越小，冲突概率越小，消耗空间越多。
负载因子越大，冲突概率越大，消耗空间利用率越高。
一般负载因子控制在0.7就可以了。
那么扩容的时候就需要将原来表中的数据重新放入新表中，这样就会让一些数据回到本该属于他们的位置，线性探测消耗的时间就不会太多了。
还有一个问题，那么如果插入的不是整形数据，是一个字符串呢？
一个字符串没办法去取%，所以我们要用仿函数对于字符串等类型进行特殊处理。（转成整形在进行映射）
#include<iostream> #include<cassert> #include<vector> #include<string> using namespace std; template<class K> struct HashFunc//能直接转成整型类型的仿函数 { size_t operator()(const K& key) { return (size_t)key; } }; template<class K> struct Hashstring//让string类型转成整形,这里也可以用HashFunc的特化支持string类型 { size_t operator()(const K& key) { size_t sum = 0; size_t count = 0; for (auto e : key) { ++count; sum += e; } return sum; } }; //闭散列的状态 enum State { EMPTY,//空 EXIST,//存在 DELETE//删除 }; //闭散列的每个元素 template<class K, class V> struct Closed { pair<K, V> _kv; State _state = EMPTY; }; template<class K, class V, class HashF = HashFunc<K>> class Closed_hash { public: typedef Closed<K, V> data; Closed_hash() :_n(0) { _hash.resize(10); } bool Insert(const pair<K, V>& kv) { if (find(kv.first)) return false; if (_n * 10 / _hash.size() > 7)//如果等于0.7就扩容 { Closed_hash<K, V, HashF> node; node._hash.resize(_hash.size() * 2); for (auto& e : _hash) { if (e._state == EXIST)//如果存在就插入新开辟的node里面 { node.Insert(e._kv); } } node._hash.swap(_hash);//交换两个表中的数组 } HashF datum; size_t hashi = datum(kv.first) % _hash.size();//找到原本插入的位置 while (_hash[hashi]._state == EXIST)//线性探测 { ++hashi; hashi = hashi % _hash.size();//防止越界 }//如果找到删除或者是空的位置就插入数据 _hash[hashi]._kv = kv; _hash[hashi]._state = EXIST;//改变状态 ++_n; return true; } data* find(const K& key) { HashF datum; size_t hashi = datum(key) % _hash.size(); size_t start = hashi; while (_hash[hashi]._state != EMPTY) { if (_hash[hashi]._state == EXIST && _hash[hashi]._kv.first == key) { return &_hash[hashi]; } ++hashi; hashi %= _hash.size(); if(start == hashi)//极端场景下，表中的数据不是存在就是删除，没有空 break; } return nullptr; } bool Erase(const K& key) { data* ret = find(key); if (ret != nullptr) { ret->_state = DELETE; return true; } return false; } private: vector<data> _hash;//哈希表 size_t _n = 0;//哈希表中有效数据的个数 };
二次探测
二次探测是按照二次方的顺序探测。
这个是为了解决连续冲突数据。
