C++：哈希表和unordered系列容器的封装

一、unordered系列关联式容器的介绍

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

其底层结构不同（哈希表）

1.1 unordered_map

unordered_map的介绍

1. unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。

2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

3. 在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。

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

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

6. 它的迭代器至少是前向迭代器。

7.unordered就是无序的意思

使用细节基本上和map一致

1.2 unordered_set

unordered_set的文档说明

1.3 性能对比

通过一个测试代码来比较unordered_set 和set的效率

void testop() //测试  底层是红黑树和哈希表的效率比对    {const size_t N = 1000000;unordered_set us;set s;vector v;v.reserve(N);srand((unsigned int)time(0));for (size_t i = 0; i _next) _node = _node->_next;// 如果结点下一个不为空，就去找下一个else //如果结点的下一个为空，那么就去哈希桶找下一个桶{KeyOfT kot;//控制data取出来的是什么//先算一下自己在当前桶的位置 size_t hashi = _ht->bucket(kot(_node->_data)); //无法访问私有成员 要么用友元 要么封装gettable和getbucketsize这两个函数 ++hashi;while (hashi _buckets.size()){if (_ht->_buckets[hashi]) //如果找到了{_node = _ht->_buckets[hashi];break;}++hashi; //继续找下一个桶}           //此时可能有两种情况  一种是成功找到，一种是走到最后都没找到if (hashi == _ht->_buckets.size()) _node = nullptr;}return *this;}Self operator++(int){Self temp = *this;++*this;return temp;}};//    class Pred = equal_totemplateclass HashTable{     typedef HashNode Node; //友元  为了能够让迭代器访问私有成员table  但是这样会破坏封装性 不推荐使用  还有一种方法是封装一个getbucketsize函数和gettables的函数       template friendstruct _HashIterator; public:~HashTable(){clear();}typedef _HashIterator  iterator;typedef _HashIterator const_iterator;typedef HashTable   Self;iterator begin()  //得找到第一个有效的桶{Node* cur = nullptr; //防止全部为空的时候for (size_t i = 0; i _kv);//cur = cur->_next;//}//}//_buckets.swap(newht._buckets); vector newtables(newsize, nullptr);//将结点一个个解下来放到新表中 （复用的话会创建很多新的结点 其实没有什么必要 ） 所以这里不用第一种方法  for (Node*& cur : _buckets)while (cur){Node* next = cur->_next;size_t hashi = bucket(kot(cur->_data)); //重新计算   //头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_buckets.swap(newtables);//交换过来 }size_t hashi = bucket(kot(data));  //只有整形是支持取模的，其他的类型是不一定的//执行头插的逻辑Node* newnode = new Node(data);newnode->_next = _buckets[hashi];_buckets[hashi] = newnode;//成为新的头++_n;return make_pair(iterator(newnode,this),true);}iterator Find(const K& key){if (empty())  return end(); //为空 就没啥好找的了KeyOfT kot;//控制data取出来的是什么size_t hashi = bucket(key); //找到这个点Node* cur = _buckets[hashi];while (cur){if (kot(cur->_data) == key) return iterator(cur, this);cur = cur->_next;}return iterator(nullptr, this);}bool Erase(const K& key){Hash hash;//控制模出来的情况 因为可能会是字符串什么的KeyOfT kot;//控制data取出来的是什么//这边就不能直接复用find了，因为只是拿到该结点，但是还得从里面删掉才有用size_t hashi = bucket(key);//找到key对应的桶Node* prev = nullptr;Node* cur = _buckets[hashi];while (cur){if (kot(cur->_data) == key) //执行删除{if (prev == nullptr)   _buckets[hashi] = cur->_next;         //说明第一个就要删else  prev->_next = cur->_next;delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false; //说明找不到}void clear() //清空桶中的元素{for (Node*& cur : _buckets){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}size_t size() const //哈希表中的元素个数{return _n;}bool empty() const{return size() == 0;}void swap(Self& s){_buckets.swap(s._buckets);std::swap(_n, s._n);}//SGI版本    主要是数学上提到说如果表的长度是素数的话，模的时候更不容易冲突  //但是如果我们正常的扩2倍肯定是难以维持他是素数的，所以就有了这样一个解决方案，专门给了一个素数表 让哈希表的长度按照这个表去更新 这样可以保证长度一直是素数//SGI版本是这么实现的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}; //实际上是不可能扩到最大的 因为 2^32次方  哪怕是char类型都有4G了  指针都有16G了/*1Byte（字节）=8bit（位）1 KB = 1024 Byte1 MB = 1024 KB1 GB = 1024 MB1TB = 1024GB*/size_t i = 0;for (; i  prime)return __stl_prime_list[i];}return __stl_prime_list[i];  //在表里依次遍历 找到比原先大的那个素数值}const size_t MaxBucketSize() const  //统计桶的最大长度并返回  检测查找的效率   测试用的  不是刚需{size_t max = 0;for (size_t i = 0; i %zd\n", i, size); //打印所有桶的长度 让我们看到具体的分布情况  这样就可以测出查找的时间复杂度if (size > max) max = size;}return max;} size_t bucket(const K& key) const //返回key所在哈希桶的编号{Hash hash;//控制模出来的情况 因为可能会是字符串什么的size_t hashi = hash(key) % _buckets.size(); //找到这个点return hashi;} size_t bucket_size(size_t n) const  //返回这个桶有多少个元素 { Node* cur = _buckets[n]; size_t size = 0; while (cur) { ++size; cur = cur->_next; } return size; }private:vector _buckets; //指针数组  哈希桶集合size_t _n = 0;//记录有效元素的个数 };

字符串哈希函数算法

由于string很常用，所以库里面有默认支持string类型的哈希函数，将哈希函数转化成可以取模的整数

3.2 unordered_set的封装

#pragma once#include"HashTable.h"namespace cyx{template //不要再Hashtable里面传  会写*** 这样自定义类型的key就没有办法解决了class unordered_set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};~unordered_set(){ clear();}//取类模板的内嵌类型 一定要用typename  不然无法区分这是一个类型还是成员变量 typedef typename HashTable ::const_iterator iterator; //set的迭代器不可被修改typedef typename HashTable::const_iterator const_iterator;iterator begin() //普通迭代器转化const迭代器 就会去调用那个拷贝构造{return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pair insert(const K& key){return _ht.Insert(key);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}void clear() {_ht.clear();}bool empty() const{return _ht.empty();}private:HashTable  _ht ;};}

3.3 unordered_map的封装

#pragma once#include"HashTable.h"namespace cyx{templateclass unordered_map{public:struct MapKeyOfT{const K& operator()(const pair& kv) //帮助我们拿到key{return kv.first;}}; ~unordered_map(){clear();}//取类模板的内嵌类型 一定要用typename  不然无法区分这是一个类型还是成员变量 typedef typename HashTable ::iterator iterator; //pair的key无论什么情况都不能修改 所以我们通过传const K控制typedef typename HashTable::const_iterator const_iterator;typedef unordered_map Self;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 insert(const pair& kv){return _ht.Insert(kv);}iterator find(const K& key) const{return _ht.Find(key);}bool erase(const K& key){return _ht.Erase();}V& operator[](const K& key)  //重载方括号{pair ret = insert(make_pair(key, V()));return ret.first->second;}void clear() {_ht.clear();}bool empty() const{return _ht.empty();}void swap(Self& s){_ht.swap(s._ht);}private:HashTable _ht; };

 3.4 自定义类型的key

class Date{friend struct HashDate; //确保能够访问其私有成员public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}bool operator==(const Date& d) const{return _year == d._year&& _month == d._month&& _day == d._day;}friend ostream& operator