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

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

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

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. 它的迭代器至少是前向迭代器。

7.unordered就是无序的意思

使用细节基本上和map一致


1.2 unordered_set

unordered_set的文档说明

1.3 性能对比

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

void testop() //测试  底层是红黑树和哈希表的效率比对    
{const size_t N = 1000000;unordered_set<int> us;set<int> s;vector<int> v;v.reserve(N);srand((unsigned int)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;
}

 我们发现,整体而言都是unordered系列更优一点,尤其是find的效率最为突出

二、哈希表

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

2.1 哈希表的概念

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

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

(1)插入元素
       根据待插入元素的关键码,以此哈希函数计算出该元素的存储位置并按此位置进行存放
(2)搜索元素
       对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置
取元素比较,若关键码相等,则搜索成功
(3)删除元素

       对元素的关键码进行同样的计算,找到对应的位置并删除

        该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表
 

2.2 哈希冲突

         不同关键字通过相同哈希哈数计算出相同的哈希地址(不同的值映射到了同一个位置),该种现象称为哈希冲突或哈希碰撞把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。


下面我们就会重点介绍什么情况下会出现哈希冲突以及如何解决哈希冲突!!

2.3 哈希函数

哈希函数:将任意长度的数据映射到固定长度输出的算法(将键值映射为存储位置)

哈希函数设计原则:
(1)哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
(2)哈希函数计算出来的地址能均匀分布在整个空间中
(3)哈希函数应该比较简单

引起哈希冲突的一个原因可能是:哈希函数设计不够合理。
 

常见的哈希函数:

(1)直接定址法--(常用)

取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
优点:简单、均匀
缺点:需要事先知道关键字的分布情况
使用场景:适合查找比较小且连续的情况


我们的位图其实就是用的直接定址法,可以理解为每个键值都有一个单独的映射位置。

(2) 除留余数法(常用)

设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址
 

哈希表的实现就是用的这个方法!!

(3)平方取中法--(不常用)

假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址;再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况
 

(4)折叠法--(不常用)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
折叠法适合:事先不需要知道关键字的分布,适合关键字位数比较多的情况
 

(5)随机数法--(不常用)

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法
 

(6)数学分析法(不常用)

       设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定
相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。

       假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前7位都是 相同
的,那么我们可以选择后面的四位作为散列地址,如果这样的抽取工作还容易出现 冲突,还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
          数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的
若干位分布较均匀的情况

 

哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

接下来我们将会重点讲解哈希表的实现,其底层用的是除留余数法,  解决其哈希冲突的方法有两种,即开放定址法和拉链法。
 

2.4 开放定址法实现简单哈希表

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

那么我们如何寻找下一个位置呢?答案就是线性探测。

         比如图中的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,hashAddr为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突
        但是线性探测会存在以下两个问题:

(1)不确定每个位置的初始值放多少,不能是放0,否则该位置如果本来就要放0的话,这个时候我们就没办法区分了!!

(2)插入的时候线性探测是向后查找直到空停止并放入,所以删除的时候也应该是线性探测向后查找直到空的这段区域必然可以找到这个要删除的元素,但是如上图44的位置依赖于前面4567的定位,假如4-7中的任意一个元素删除了,那么下一次要删44的时候就会找不到44.

    为了解决上面的两个问题,我们的策略就是设置3种状态,EMPTY 表示空, EXIST表示有,DELETE表示已删除。 我们给每个位置都存一个状态。

    同时为了防止元素扎堆的情况,可以采用二次线性探测,这样可以减少冲突。

2.4.1 基本结构

enum State //设置状态本质上是为了解决两个问题 1,一开始的元素不知道是多少比较合适  如果是0的话  可能加入的数也正好是0  2.如果该位置元素删除了,那么会导致因为该元素占位而到别的位置的元素找不到!!!
{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:private:vector<HashData<K, V>> _tables;size_t _n = 0; //记录有效的数据个数
};

2.4.2 插入

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))  return false;//键值不冗余, 所以如果存在,就没有必要去插入//考虑扩容的问题   负载因子为0.7if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){//利用现代写法 让你去搞  然后窃取革命成果size_t newsize = _tables.size() == 0 ? 10 :_tables.size()*2;HashTable<K, V> newt;newt._tables.resize(newsize);//遍历旧表 然后重新搞到新表上for (auto& data : _tables)if (data._state == EXIST)newt.Insert(data._kv);_tables.swap(newt._tables);//窃取革命成果}size_t hashi = kv.first % _tables.size();//%容量是没有用的,%size才是有用的  因为光扩容,也是不敢随机访问的!//进行线性探测 当前如果存在就要往后推size_t i = 1;size_t index = hashi;while (_tables[index]._state == EXIST) //{index = hashi + i; //这样子方便后面修改成二次检测//index可能会越界,可能需要去修正一下index %= _tables.size();++i;}//在相应的位置进行操作_tables[index]._kv = kv;_tables[index]._state = EXIST;++_n; //更新次数return true;
}

  (1) 哈希表在%的时候一定要%size而不是%capacity(可能会存在越界,比如说size只有10,而capacity是20,如果映射到15也是不可以访问的!!),因为我们空间一定是开好了的而不是中间插入进去。 扩容的时候也是一定要用resize而不是reserve。

(2)哈希表在某些时候需要去扩容,我们设置一个负载因子(假设0.7),超出这个范围我们就是扩容,但是我们不能单纯地去resize,因为映射关系会完全改变。比如说原本10的空间,12是插入在2的位置,但是空间变成20后,12就应该插入到12的位置上。所以我们要创建一个新表,然后遍历旧表拿数据,重新计算映射位置。      每次又要走一次线性探测,为了防止代码冗余,此时有两种方案,一种是将线性探测的代码封装起来,然后复用   另一种方案是现代写法,再创建一个新的对象,然后让该对象去调用insert,最后再利用swap窃取成果。

2.4.3 查找

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)  //前面的判断是确保当前位置不为DETELE 状态  因为为我们封装的删除是一个伪删除,并不是真的删除return &_tables[index];//如果找不到,往后继续走index = hashi + i;index %= _tables.size();++i;//极端情况    插入一部分 +删除一部分 +插入一部分 正好所有的位置都是存在+删除 此时上面面临着死循环  所以我们堆i进行判断,如果index==hashi说明已经找了一圈了,此时就跳出去if (index == hashi) break;}return nullptr;
}

        不等于空就可以继续向后线性探测,因为我们设置delete状态就是想实现伪删除,这样在删除某些元素的时候不会影响线性探测。

极端情况:如果正好插入一部分,删除一部分,再插入一部分,导致所有的位置都是存在+删除,那么循环永远不会停止,这个时候我们就要去判断如果正好走了一圈了,就可以break了。

2.4.4 删除

bool Erase(const K& key)
{HashData<K, V>* ret = Find(key); //复用findif (ret) //如果找到了  将该位置改成删除{ret->_state = DELETE; //伪删除--_n;return true;}return false;
}

复用Find即可,然后进行伪删除。 

2.4.5 整体代码的实现

	enum State //设置状态本质上是为了解决两个问题 1,一开始的元素不知道是多少比较合适  如果是0的话  可能加入的数也正好是0  2.如果该位置元素删除了,那么会导致因为该元素占位而到别的位置的元素找不到!!!{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.7if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){//利用现代写法 让你去搞  然后窃取革命成果size_t newsize = _tables.size() == 0 ? 10 :_tables.size()*2;HashTable<K, V> newt;newt._tables.resize(newsize);//遍历旧表 然后重新搞到新表上for (auto& data : _tables)if (data._state == EXIST)newt.Insert(data._kv);_tables.swap(newt._tables);//窃取革命成果}size_t hashi = kv.first % _tables.size();//%容量是没有用的,%size才是有用的  因为光扩容,也是不敢随机访问的!//进行线性探测 当前如果存在就要往后推size_t i = 1;size_t index = hashi;while (_tables[index]._state == EXIST) //{index = hashi + i; //这样子方便后面修改成二次检测//index可能会越界,可能需要去修正一下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)  //前面的判断是确保当前位置不为DETELE 状态  因为为我们封装的删除是一个伪删除,并不是真的删除return &_tables[index];//如果找不到,往后继续走index = hashi + i;index %= _tables.size();++i;//极端情况    插入一部分 +删除一部分 +插入一部分 正好所有的位置都是存在+删除 此时上面面临着死循环  所以我们堆i进行判断,如果index==hashi说明已经找了一圈了,此时就跳出去if (index == hashi) break;}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key); //复用findif (ret) //如果找到了  将该位置改成删除{ret->_state = DELETE; //伪删除--_n;return true;}return false;}private:vector<HashData<K, V>> _tables;size_t _n = 0; //记录有效的数据个数};

2.5 拉链法实现简单哈希表

        开放定址法是一个比较粗暴的方式,因为其是一种恶性循环,冲突之后就占别的位置,而后面一旦出现本该放在该位置的元素,也得另外占别的位置。 

       而拉链法相对来说更文明一点,如果发生冲突了,我就跟你挤一挤。接在一起。

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

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

//因为有扩容(负载因子控制)的存在!!!!,哈希桶增删查改的时间复杂度都是O(1)      虽然插入可能会存在扩容,扩容操作是O(N) 但是整体而言扩容只在那一瞬间 因为我们的哈希表是不断在插入元素的 //相当于是一个好学生考试,他大多数情况下都考得好就偶尔一两次考不好  同理,这边插入的时间复杂度大多数情况是O(1) O(N)只在一瞬间
//跟快排一样,快排也非常难出现最坏情况 因为有了随机取KEY(针对有序) 以及这个三路划分(针对重复)
namespace 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>struct HashFunc //默认 int{size_t operator()(const K& key){return key;}};template<>  //因为string 用的比较多, 所以我们可以专门搞一个模板特化版本  专门针对string  有特化走特化,没特化走普通类型struct HashFunc<string>{// 尽量要控制不要重复  1.将字符串的所有ASCII码加起来 2,但是加起来之后,对于字符相同但是顺序不同的字符串 还是不太好区分,所以这里要用以恶搞BKDR哈希算法size_t operator()(const string& s){size_t hash = 0;for (auto ch : s)  //将字符串转化成整型,通过映射整型去找到字符串对应的位置{hash += ch;  //但是光有这一句代码的话, 应对一些字符相同但是顺序相同的字符串的时候,仍然是不好区分的 hash *= 31;  //BKDR哈希 }return hash;}};template<class K,class V,class Hash= HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:~HashTable(){clear();}bool Insert(const pair<K, V>& kv){if (Find(kv.first)) return false;//如果有就不用找了  Hash hash;//通过仿函数控制可以K变成可以取模//负载因子为1时进行扩容if (_n == _tables.size()) //这里不适合用现代写法,因为如果去调用insert的话,会重新申请很多新的结点,然后又要释放很多结点 效率太低了    //解决方案就是  原表的结点重新计算,挪动到新表的位置                                                                  {//size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2; 原来的版本size_t newsize = GetNextPrime(_tables.size()); //按照SGI版本的素数表第一种方案  创建一个新的表来完成这个任务//HashTable<K, V> newht;//newht._tables.resize(newsize);//for (auto&cur : _tables)//{//	while (cur)//	{//		newht.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newht._tables); vector<Node*> newtables(newsize, nullptr);//将结点一个个解下来放到新表中 (复用的话会创建很多新的结点 其实没有什么必要 )for (Node*& cur : _tables)while (cur){Node* next = cur->_next;size_t hashi = hash(cur->_kv.first) % newtables.size(); //重新计算   //头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables.swap(newtables);//交换过来 }size_t hashi = hash(kv.first) % _tables.size();  //只有整形是支持取模的,其他的类型是不一定的//执行头插的逻辑Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;//成为新的头++_n;return true;}Node* Find(const K&key){if (_tables.size() == 0)  return nullptr;Hash hash;size_t hashi = hash(key) % _tables.size(); //找到这个点Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key) return cur;cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hash;//这边就不能直接复用find了,因为只是拿到该结点,但是还得从里面删掉才有用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;--_n;return true;}prev = cur;cur = cur->_next;}return false; //说明找不到}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("[%zd]->%zd\n", i, size); //打印所有桶的长度 让我们看到具体的分布情况  这样就可以测出查找的时间复杂度if (size > max) 	max = size;}return max;}void clear(){for (Node*& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}//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 < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];  //在表里依次遍历 找到比原先大的那个素数值}private:vector<Node*> _tables; //指针数组size_t _n=0;//记录有效元素的个数 };

三、unordered系列容器的封装

3.1 改造拉链法哈希表

//自己实现的时候  一定要一步一步来, 先封装哈希表 然后再封装简单的map和set  然后再封装迭代器让插入跑起来,然后再去考虑其他的一些细节问题, 不要一下子把所有的模板参数都加上 
//要一步一步来template<class T>
struct HashNode
{HashNode<T>* _next;T _data; //T决定存的是KV 还是KHashNode(const T& data):_next(nullptr),_data(data){}
};
template<class K>
struct HashFunc //默认 int
{size_t operator()(const K& key){return key;}
};template<>  //因为string 用的比较多, 所以我们可以专门搞一个模板特化版本  专门针对string  有特化走特化,没特化走普通类型  默认支持
struct HashFunc<string>
{// 尽量要控制不要重复  1.将字符串的所有ASCII码加起来 2,但是加起来之后,对于字符相同但是顺序不同的字符串 还是不太好区分,所以这里要用以恶搞BKDR哈希算法size_t operator()(const string& s){size_t hash = 0;for (auto ch : s)  //将字符串转化成整型,通过映射整型去找到字符串对应的位置{hash += ch;  //但是光有这一句代码的话, 应对一些字符相同但是顺序相同的字符串的时候,仍然是不好区分的 hash *= 31;  //BKDR哈希 }return hash;}
};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; //服务set普通迭代器 //在红黑树中也是按照这个逻辑,key被修改会破坏红黑树的整体结构, 所以我们必须要去控制//成员变量 必然要有结点指针以及哈希桶的指针Node* _node;const HT* _ht;_HashIterator(Node* node,const HT* ht) //这样可以保证const可以接收 普通的也可以接收 因为权限可以缩小:_node(node), _ht(ht){}_HashIterator(const Iterator& it) //拷贝构造  本质上是为了set去服务的:_node(it._node)   //普通迭代器可以转化成const迭代器 , _ht(it._ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &operator*();}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){if (_node->_next) _node = _node->_next;// 如果结点下一个不为空,就去找下一个else //如果结点的下一个为空,那么就去哈希桶找下一个桶{KeyOfT kot;//控制data取出来的是什么//先算一下自己在当前桶的位置 size_t hashi = _ht->bucket(kot(_node->_data)); //无法访问私有成员 要么用友元 要么封装gettable和getbucketsize这两个函数 ++hashi;while (hashi < _ht->_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_to<Key>template<class K, class T, class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;//友元  为了能够让迭代器访问私有成员table  但是这样会破坏封装性 不推荐使用  还有一种方法是封装一个getbucketsize函数和gettables的函数  template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend	struct _HashIterator; 
public:~HashTable(){clear();}typedef _HashIterator<K, T,T&,T*,KeyOfT, Hash>  iterator;typedef _HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;typedef HashTable<K, T, KeyOfT, Hash>   Self;iterator begin()  //得找到第一个有效的桶{Node* cur = nullptr; //防止全部为空的时候for (size_t i = 0; i < _buckets.size(); ++i){if (_buckets[i]){cur = _buckets[i];break;}}return iterator(cur, this);  //this指针}iterator end()  {return iterator(nullptr, this);  //this指针}const_iterator begin() const{Node* cur = nullptr;for (size_t i = 0; i < _buckets.size(); ++i){cur = _buckets[i];if (_buckets[i]){cur = _buckets[i];break;}}return const_iterator(cur, this);}const_iterator end() const{return const_iterator(nullptr, this);}pair<iterator, bool> Insert(const T& data){KeyOfT kot;//控制data取出来的是什么iterator it = Find(kot(data));if (it != end()) return make_pair(it, false);//如果有就不用找了  //负载因子为1时进行扩容if (_n == _buckets.size()) //这里不适合用现代写法,因为如果去调用insert的话,会重新申请很多新的结点,然后又要释放很多结点 效率太低了    //解决方案就是  原表的结点重新计算,挪动到新表的位置                                                                  {//size_t newsize = _buckets.size() == 0 ? 10 : _buckets.size() * 2; 原来的版本size_t newsize = GetNextPrime(_buckets.size()); //按照SGI版本的素数表第一种方案  创建一个新的表来完成这个任务//HashTable<K, V> newht;//newht._buckets.resize(newsize);//for (auto&cur : _buckets)//{//	while (cur)//	{//		newht.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_buckets.swap(newht._buckets); vector<Node*> 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 < __stl_num_primes; ++i){if (__stl_prime_list[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 < _buckets.size(); ++i){Node* cur = _buckets[i];size_t size = bucket_size(cur);printf("[%zd]->%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<Node*> _buckets; //指针数组  哈希桶集合size_t _n = 0;//记录有效元素的个数 
};

字符串哈希函数算法

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

3.2 unordered_set的封装

#pragma once
#include"HashTable.h"namespace cyx
{template<class K , class Hash = HashFunc<K>> //不要再Hashtable里面传  会写死 这样自定义类型的key就没有办法解决了class unordered_set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};~unordered_set(){clear();}//取类模板的内嵌类型 一定要用typename  不然无法区分这是一个类型还是成员变量 typedef typename HashTable<K, K,SetKeyOfT,Hash> ::const_iterator iterator; //set的迭代器不可被修改typedef typename HashTable<K, K, SetKeyOfT, Hash>::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<iterator, bool> 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<K, K, SetKeyOfT, Hash>  _ht ;};
}

3.3 unordered_map的封装

#pragma once
#include"HashTable.h"namespace cyx
{template<class K,class V,class Hash = HashFunc<K>>class unordered_map{public:struct MapKeyOfT{const K& operator()(const pair<K,V>& kv) //帮助我们拿到key{return kv.first;}};~unordered_map(){clear();}//取类模板的内嵌类型 一定要用typename  不然无法区分这是一个类型还是成员变量 typedef typename HashTable<K, pair<const K, V>, MapKeyOfT,Hash> ::iterator iterator; //pair的key无论什么情况都不能修改 所以我们通过传const K控制typedef typename HashTable<K, pair<const K, V>, MapKeyOfT,Hash>::const_iterator const_iterator;typedef unordered_map<K, V, Hash> 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<iterator, bool> insert(const pair<K,V>& 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<iterator, bool> 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<K, pair<const K, V>, MapKeyOfT, Hash> _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) ||(_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<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;};ostream& operator<<(ostream& cout, const Date& d){cout << d._year << "-" << d._month << "-" << d._day;return cout;}struct HashDate //自定义类型的key就手动传一个{size_t operator()(const Date& d){size_t hash = 0;hash += d._year;hash *= 31;hash += d._month;hash *= 31;hash += d._day;hash *= 31;return hash;}};// 一个类型要做unordered_map/unordered_set的key,要满足支持转换成取模的整形 和 ==比较// 一个类型要做map/set的key,要满足支持<比较/*if (cur->key < key){}else if (key < cur->key){}else{}*///如果有些类不是你写的,并不支持上面的东西 但是你还是想要去比较怎么办呢??   其实库里面还提供了一个仿函数  class Pred = equal_to<Key>//判断各个键值对相同的规则void test_unordered_map4(){Date d1(2023, 3, 13);Date d2(2023, 3, 13);Date d3(2023, 3, 12);Date d4(2023, 3, 11);Date d5(2023, 3, 12);Date d6(2023, 3, 13);Date a[] = { d1, d2, d3, d4, d5, d6 };unordered_map<Date, int, HashDate> countMap;for (auto e : a)  ++countMap[e];for (auto& kv : countMap)  cout << kv.first << ":" << kv.second << endl;}

注意:

1、 一个类型要做unordered_map/unordered_set的key,满足支持转换成 取模的整形==比较
       一个类型要做map/set的key,要满足支持<比较 

2、但是如果该类不是你自己写的,我们没有办法直接去访问其私有成员,那就得再加一个模版参数class Pred = equal_to<Key> 。增加判断键值相同的规则。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/323280.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

索引失效情况

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;面经 ⛺️稳中求进&#xff0c;晒太阳 一、索引列上运算操作。 不要在索引列上进行运算操作&#xff0c;否则索引会失效。 在tb_user的phone列加上索引&#xff0c;然后进行条件查询&am…

Kafka从0到消费者开发

安装ZK Index of /zookeeper/zookeeper-3.9.2 下载安装包 一定要下载-bin的&#xff0c;不带bin的是源码&#xff0c;没有编译的&#xff0c;无法执行。-bin的才可以执行。 解压 tar -zxvf apache-zookeeper-3.9.2-bin.tar.gz 备份配置 cp zoo_sample.cfg zoo_sample.cfg-b…

调用 gradio 创建聊天网页报错(使用远程服务器)

文章目录 写在前面1、使用默认IP地址&#xff08;失败&#xff09;2、使用本地IP地址&#xff08;失败&#xff09;3、使用远程服务器IP地址&#xff08;成功&#xff09; 写在前面 我复现了github上的 llama-chinese 的工作 使用的是 llama2&#xff0c;环境配置是在远程服务…

指针的奥秘(二):指针与数组的联系+字符指针+二级指针+指针数组+《剑指offer》笔试题

指针 一.指针与数组的联系1.数组名的理解2.使用指针访问数组3.一维数组传参的本质 二.字符指针1.字符指针隐藏秘密2.常量字符串3.《剑指offer》笔试题 三.二级指针四.指针数组1.指针数组模拟二维数组 一.指针与数组的联系 1.数组名的理解 也许大部分人认为数组名就是一个名称&…

使用 PXE+Kickstart 批量网络自动装机

前言&#xff1a; 正常安装系统的话使用u盘一个一个安装会非常慢&#xff0c;所以批量安装的技术就出来了。 一、 概念 PXE &#xff08;Preboot eXecute Environment&#xff0c;预启动执行环境&#xff09;是由 Intel 公司开发的技术&#xff0c;可以让计算机通过网络来启动…

如何判断nat网络?如何内网穿透

大家都清楚&#xff0c;如果你想开车&#xff0c;就必须要给车上一个牌照&#xff0c;随着车辆越来越多&#xff0c;为了缓解拥堵&#xff0c;就需要摇号&#xff0c;随着摇号的人数越来越多&#xff0c;车牌对于想开车的人来说已经成为奢望。在如今的IPv4时代&#xff0c;我们…

生信分析进阶2 - 利用GC含量的Loess回归矫正reads数量

在NGS数据比对后&#xff0c;需要矫正GC偏好引起的reads数量误差可用loess回归算法&#xff0c;使用R语言对封装的loess算法实现。 在NIPT中&#xff0c;GC矫正对检测结果准确性非常重要&#xff0c;具体研究参考以下文章。 Noninvasive Prenatal Diagnosis of Fetal Trisomy…

如何把多个文件(夹)平均复制到多个文件夹中

首先&#xff0c;需要用到的这个工具&#xff1a; 度娘网盘 提取码&#xff1a;qwu2 蓝奏云 提取码&#xff1a;2r1z 假定的情况是&#xff0c;共有20个兔兔的图片&#xff0c;想要平均的复制4个文件夹里&#xff0c;那么每个文件夹里面就有5个图片 &#xff08;如果是5个&a…

nginx自动部署-跨操作系统

项目里面有一个需求&#xff0c;就是需要用让nginx进程提供给系统管理一个start,stop和getPid方法&#xff0c;这样系统管理可以自动拉起来nginx&#xff0c;达到自动部署的目的。离线部署同样适用 这样一来&#xff0c;我就需要提供windows版本linux不同版本的nginx源码包&am…

Spring JdbcTemplate实现自定义动态sql拼接功能

需求描述&#xff1a; sql 需要能满足支持动态拼接&#xff0c;包含 查询字段、查询表、关联表、查询条件、关联表的查询条件、排序、分组、去重等 实现步骤&#xff1a; 1&#xff0c;创建表及导入测试数据 CREATE TABLE YES_DEV.T11 (ID BINARY_BIGINT NOT NULL,NAME VARCH…

【管理咨询宝藏93】大型制造集团数字化转型设计方案

【管理咨询宝藏93】大型制造集团数字化转型设计方案 【格式】PDF版本 【关键词】国际咨询公司、制造型企业转型、数字化转型 【核心观点】 - 235页大型制造型集团数字化转型方案设计&#xff01;细节非常详尽&#xff0c;图表丰富&#xff01; - 系统架构必须采用成熟、具有国…

美食推荐网站设计

**中文摘要&#xff1a;**在当今信息化、网络化的时代背景下&#xff0c;美食文化正逐渐融入人们的日常生活&#xff0c;而网络平台成为人们获取美食信息、分享美食体验的重要途径。为了满足广大美食爱好者对美食信息的探索和推荐需求&#xff0c;本文提出了一种创新的美食推荐…

YOLOv8网络结构介绍

将按照YOLOv8目标检测任务、实例分割任务、关键点检测任务以及旋转目标检测任务的顺序来介绍&#xff0c;主要内容也是在目标检测任务中介绍&#xff0c;其他任务也只是Head层不相同。 1.YOLOv8_det网络结构 首先&#xff0c;YOLOv8网络分成了三部分&#xff0c;分别是主干网络…

Spark云计算平台Databricks使用,创建workspace和Compute计算集群(Spark集群)

Databricks&#xff0c;是属于 Spark 的商业化公司&#xff0c;由美国加州大学伯克利 AMP 实验室的 Spark 大数据处理系统多位创始人联合创立。Databricks 致力于提供基于 Spark 的云服务&#xff0c;可用于数据集成&#xff0c;数据管道等任务。 1 创建workspace 点击创建wor…

word 毕业论文格式调整

添加页眉页脚 页眉 首先在页面上端页眉区域双击&#xff0c;即可出现“页眉和页脚”设置页面&#xff1a; 页眉左右两端对齐 如果想要页眉页脚左右两端对齐&#xff0c;可以选择添加三栏页眉&#xff0c;然后将中间那一栏删除&#xff0c;即可自动实现左右两端对齐&#x…

Spring Boot集成Ldap快速入门Demo

1.Ldap介绍 LDAP&#xff0c;Lightweight Directory Access Protocol&#xff0c;轻量级目录访问协议. LDAP是一种特殊的服务器&#xff0c;可以存储数据数据的存储是目录形式的&#xff0c;或者可以理解为树状结构&#xff08;一层套一层&#xff09;一般存储关于用户、用户…

吴恩达机器学习笔记:第 9 周-17大规模机器学习(Large Scale Machine Learning)17.3-17.4

目录 第 9 周 17、 大规模机器学习(Large Scale Machine Learning)17.3 小批量梯度下降17.4 随机梯度下降收敛 第 9 周 17、 大规模机器学习(Large Scale Machine Learning) 17.3 小批量梯度下降 小批量梯度下降算法是介于批量梯度下降算法和随机梯度下降算法之间的算法&…

基于Springboot的线上教学平台

基于SpringbootVue的线上教学平台设计与实现 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringbootMybatis工具&#xff1a;IDEA、Maven、Navicat 系统展示 用户登录 首页 学习资料 交流论坛 试卷列表 公告信息 后台登录 后台首页 学员管理 资料类型…

Junit 测试中如何对异常进行断言

本文对在 Junit 测试中如何对异常进行断言的几种方法进行说明。 使用 Junit 5 如果你使用 Junit 5 的话&#xff0c;你可以直接使用 assertThrows 方法来对异常进行断言。 代码如下&#xff1a; Exception exception assertThrows(NumberFormatException.class, () -> {n…

Universal Thresholdizer:将多种密码学原语门限化

参考文献&#xff1a; [LS90] Lapidot D, Shamir A. Publicly verifiable non-interactive zero-knowledge proofs[C]//Advances in Cryptology-CRYPTO’90: Proceedings 10. Springer Berlin Heidelberg, 1991: 353-365.[Shoup00] Shoup V. Practical threshold signatures[C…