重庆建设监理协会网站,手机触屏网站幻灯片,做外贸网站推广什么比较好,wordpress com login#x1f4dd; 个人主页 #xff1a;超人不会飞)#x1f4d1; 本文收录专栏#xff1a;《C的修行之路》#x1f4ad; 如果本文对您有帮助#xff0c;不妨点赞、收藏、关注支持博主#xff0c;我们一起进步#xff0c;共同成长#xff01; 目录 前言一、基于哈希表的两个… 个人主页 超人不会飞) 本文收录专栏《C的修行之路》 如果本文对您有帮助不妨点赞、收藏、关注支持博主我们一起进步共同成长 目录 前言一、基于哈希表的两个容器1.1 unordered_map1.2 unordered_set1.3 小试牛刀 二、哈希表2.1 哈希的概念2.2 哈希冲突2.3 哈希函数2.4 字符串哈希算法 三、哈希冲突的解决3.1 闭散列3.1.1 线性探测3.1.2 二次探测 3.2 开散列3.2.1 链地址法的思想3.2.2 哈希桶的模拟实现 四、封装unordered_map和unordered_set4.1 哈希表的迭代器4.2 改造哈希表4.3 unordered_set的封装4.4 unordered_map的封装 前言 在前面的文章中我们学习了红黑树其查找数据的效率很高查找的次数最差是树的高度logN次并且要进行多次比较。而哈希表是一种元素存储位置与元素的关键码建立一一映射关系的结构无需进行比较其查找效率更高最优可以一次直接找到。在C中map和set的底层是红黑树结构。那么在详细介绍哈希表之前我们也要先介绍C中提供的另外两种关联式容器——unordered_map和unordered_set它们的底层是哈希表。 unordered_map 和 unordered_set的功能、接口与map和set都大差不差所以使用起来感觉一样但是底层可大不相同。
一、基于哈希表的两个容器
1.1 unordered_map
文档介绍
对其概念的解释 Unordered maps是一种存储key,value键值对元素的关联式容器允许通过键值快速地索引到与其对应的实值。 在unordered_map中一个键值通常用于唯一地标识元素而实值是一个对象其内容与键值相关联。键值类型和实值类型可能不同。 在unordered_map中元素不以任何特定的顺序排序与键值和实值都无关而是根据每个元素的哈希值以桶的形式被组织起来以达到通过键值key快速获取与其对应的实值(value)的目的。 unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。 unordered_maps实现了直接访问操作符(operator[])它允许使用key作为参数直接访问value。 它的迭代器至少是前向迭代器。 unordered_map的接口与map类似通过查文档学习即可有以下几个比较特殊的接口。 函数声明接口功能size_t bucket_count() const返回哈希桶中桶的总个数size_t bucket_size(size_t n) const返回n号桶中元素的个数size_t bucket(size_t key) const返回元素键值为key的桶编号 1.2 unordered_set
文档介绍
对其概念的解释 Unordered sets是一种无序的、存储单一元素的容器允许通过键值快速找到元素。 在unordered_set中元素的实值value同时是元素的键值key标识唯一的元素。 键值是永恒不变的因此unordered_set只能插入和删除新元素不可修改其中已存在的元素。 和unordered_map一样底层是哈希桶。 unordered_set容器通过key访问单个元素要比set快但它通常在遍历元素子集的范围迭代方面效率较低。 它的迭代器至少是前向迭代器。 1.3 小试牛刀 对于unordered_map和unordered_set来几道OJ以熟练掌握它们的使用 1.在长度2N的数组中找出重复N次的元素
class Solution {
public:int repeatedNTimes(vectorint nums) {// 统计每个元素出现的个数unordered_mapint,int countMap;for(auto e:nums){countMap[e];}// 找出出现N次的元素int N nums.size() / 2;for(auto kv:countMap){if(kv.second N){return kv.first;}}return -1;}
};2.两个数组的交集
class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {// 交集必然存在于较小集合中// 将较小的数组哈希映射然后较大数组到较小数组的哈希表中找交集// O(max(n,m,max(n,m))) O(max(n,m))// 1.找出较小数组vectorint minNums nums1;vectorint maxNums nums2;if(nums1.size() nums2.size()){minNums.swap(maxNums);}// 2.较小数组哈希映射unordered_mapint,int count1;for(auto e:minNums){count1[e];}// 3.较大数组计数unordered_mapint,int count2;for(auto e:maxNums){count2[e];}// 4.count2到count1找交集vectorint ret;for(auto kv:count2){auto it count1.find(kv.first);if(it ! count1.end()){// 计算出现的次数int times kv.second it-second ? kv.second : it-second;// 加入交集ret.resize(ret.size()times,kv.first);}}return ret;}
};3.存在重复元素
class Solution {
public:bool containsDuplicate(vectorint nums) {unordered_setint us;for(auto e:nums){// 插入unordered_set出现插入失败的情况即nums数组存在重复元素if(!(us.insert(e).second)){return true;}}return false;}
};4.两句话中的不常见单词
class Solution {
public:vectorstring uncommonFromSentences(string s1, string s2) {//key值是单词value值是出现的次数unordered_mapstring,int cnt1;unordered_mapstring,int cnt2;// 词频统计// 统计s1中每个单词出现的次数int begin1 0, end1 0;while(begin1 s1.size()){end1 s1.find( ,begin1);if(end1 string::npos){end1 s1.size();}string word(s1.begin() begin1,s1.begin() end1);cnt1[word];begin1 end11;}// 统计s2中每个单词出现的次数int begin2 0, end2 0;while(begin2 s2.size()){end2 s2.find( ,begin2);if(end2 string::npos){end2 s2.size();}string word(s2.begin() begin2,s2.begin() end2);cnt1[word];begin2 end21;}//寻找两句话中的不常见单词vectorstring ret;for(auto kv:cnt1){if(kv.second 1 cnt2.find(kv.first) cnt2.end()){ret.push_back(kv.first);}}for(auto kv:cnt2){if(kv.second 1 cnt1.find(kv.first) cnt1.end()){ret.push_back(kv.first);}}return ret;}
};二、哈希表 OK掌握了unordered_map和unordered_set的上层接口接着我们就要着重来研究其底层的哈希表了~ 2.1 哈希的概念 顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数。频繁地比较会降低查询的效率。 哈希表又名散列表是一种无需进行比较即可完成查找的数据结构。它通过哈希函数(hashFunc)使元素的存储位置与键值之间建立一一映射的关系那么在查找时即可迅速找到元素。当向哈希表中插入或查询时先以元素的键值结合哈希函数计算出该元素的存储位置这个位置称为哈希地址在哈希地址上插入或查询即可可能会发生哈希冲突后面会讲最优情况一次就能查找到插入位置/对应元素。 举个栗子设哈希函数为 hashi(key) key % capacity且capacity10并插入一些元素则有如下哈希表。 2.2 哈希冲突
上面举的例子中哈希函数hashi key % capacity是一个比较常用的哈希函数称之为除留余数法求哈希值。延用上面这个例子两个不同的key使用除留余数可能会求出相同的哈希地址。如图 可见若想插入键值为13的元素方便起见后面称键值为i的元素为元素i计算hashi(13)3。但发现hashi3的位置已经存在元素3此时发生了冲突键值13不能直接插入hashi3的位置因为该位置已经被占用了。这种冲突称之为哈希冲突。 概念
对于两个数据元素的关键字 k i k_i ki和 k j k_j kj(i ! j)有 k i k_i ki ! k j k_j kj但有Hash( k i k_i ki) Hash( k j k_j kj)即不同关键字通过相同哈希函数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。把具有不同关键码key而具有相同哈希地址的数据元素称为“同义词”。 2.3 哈希函数 优秀的哈希函数可以尽量避免哈希冲突注意只能避免无法消除因此哈希函数的设计十分重要 ⭕哈希函数的设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中尽量少的出现堆积现象哈希函数应该比较简单
⭕ 常用的哈希函数
直接定址法(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点 简单、均匀 缺点 需要事先知道关键字的分布情况、可能会造成空间浪费 适用场景 数据区间比较集中、连续
除留余数法(最常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址。 优点 简单、运算速度快 缺点 均匀性差易发生冲突
平方取中法(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址再比如关键字4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址平方取中法比较适合不知道关键字的分布而位数又不是很大的情况。 折叠法(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况 随机数法(了解) 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法 数学分析法(了解) 设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。例如电话号码的后四位、身份证后六位。数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀的情况 2.4 字符串哈希算法 哈希函数hash(key)中传入的key必须是整型才能计算出哈希地址。而实际中数据的键值不一定是整型可能是浮点类型、字符串、自定义类型等等而这些非整型类型的键值就需要先转换成整型再去进行映射插入时查询时都需要转换成整型才能计算hashi。像浮点数这种能够直接强转成整型了强转即可。而字符串、自定义类型之类的就需要专门设计算法去转换了实际中键值为字符串的情况比较常见因为我们讨论字符串转整型的哈希算法。 优秀的字符串哈希算法能够尽量少的出现不同字符串转换为重复的整型值从而降低冲突发生的概率。此处给出比较常用的两种字符串哈希算法。
// 转换整型的哈希算法设计为仿函数方便通过模板参数传递给哈希表// 通用的转换整型哈希算法K类型能强制类型转换为int类型
template class K
struct Hash
{int operator()(const K key){return key;}
};// 模板的特化
template
struct Hashstring
{//1.字符串每个字符相加//int operator()(const string str)//{// int key 0;// for (auto ch : str)// {// key ch - a;// }// return key;//}//2.BKDR算法int operator()(const string key){int hash 0;for (auto ch : key){hash hash * 131 ch;}return hash;}
};参考文章《各种字符串哈希函数》
三、哈希冲突的解决 解决哈希冲突是实现哈希表的关键常见的解决方法有两种闭散列和开散列 3.1 闭散列 闭散列又称开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把元素存放到冲突位置中的下一个空位置中去。 那如何寻找下一个空位置呢常见的有两种方法线性探测和二次探测。我们主要讨论线性探测这种方法并借此深入了解哈希表的设计。
注意以下举的例子皆以除留余数法求哈希地址
3.1.1 线性探测
从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。就像找车位一样在一排占满的车位中挨个找到下一个空车位即可 插入 如下为过程要插入key值为16的元素求出hashi为6发生哈希冲突线性探测找下一个空位置插入。 删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响 其他元素的搜索。比如删除元素8如果直接删除掉查找元素16可能会受影响查找的路径断裂了。 因此线性探测采用标记的伪删除法来删除一个元素。 ⭕解决方法给哈希表每一个空间设置一个状态值标志该位置 为空、有值、已被删除 三种状态。 enum State
{EMPTY, // 为空EXIST, // 已存在元素DELETE // 元素被删除
};开放定址法的负载因子 哈希表的特性往往会使其陷入两难之境。已知哈希表的空间是一个连续的数组 若其空间利用率较高那么经过哈希函数计算的哈希地址很可能已经存有数据了则哈希冲突发生的概率也会增高发生哈希冲突需要消耗更多成本去查找那么插入和查找的效率就会下降。但如果为了降低哈希冲突发生的概率扩大空间又会导致空间浪费空间利用率较低。 负载因子的出现就是为了解决这个问题。 负载因子 哈希表的有效元素个数 / 表的长度 负载因子表示哈希标志数据元素的填满程度。若负载因子较大表示哈希表空间利用率较高但发生冲突的概率也大。若负载因子较小表示发生冲突的概率较低但哈希表空间利用率也低了。因此必须在“冲突的概率”与“空间利用率”之间寻找一种平衡与折中也就是求一个合适的负载因子上限超过这个上限就要扩容以降低负载因子。还要考虑上限过低可能增加扩容的次数降低效率。 综合各种因素经过大量的实践和数学计算开放定址法的负载因子应严格控制在0.7 ~ 0.8之间。因此一些采用开放定址法的hash库C标准库中的哈希表并不是采用开放定址法如Java的系统库限制了负载因子为0.75。 参考文章HashMap的负载因子为什么是0.75 扩容的门道 哈希表的扩容也是有讲究的。不像vector的扩容先开一块大的新空间再将数据直接拷贝到新空间上。哈希表的扩容需要重新计算每个元素的哈希映射地址再拷贝到新空间的相应位置上。因为哈希函数总是和空间大小有关空间变大了每个元素的哈希地址都有可能改变。 哈希冲突频发使用线性探测处理冲突后可能出现堆积现象这种堆积现象会随着哈希表的扩容而得到缓解。 如图负载因子已达到0.7随便插入一个元素2会发生扩容。扩容之前hashi6的元素堆积在一起扩容之后堆积现象得到缓解。这个概念和密度的概念很像想象一杯很浓的咖啡加水之后变得没那么浓了因为咖啡因稀释开了这里是堆积的元素稀释开了一个道理。 线性探测的代码实现
namespace closeHash
{// 哈希表空间的状态enum State{EMPTY,EXIST,DELETE};// 哈希表中的元素template class K, class Vstruct hash_data{pairK, V _data;// 键值对State _state EMPTY;// 状态值};// 哈希表主体// HashToKey为键值转换为整型的仿函数类型template class K, class V, class HashToKeyclass hash_table{typedef hash_dataK, V Data;public:hash_table():_table(10)//调用vector的n个val的构造函数//尽量保持底层vector的size和capacity相等避免没必要的空间浪费,_n(0){}// 查询键值为k的元素Data* find(const K k){int hashi HashToKey()(k) % _table.size();int start hashi;// 起始位while (_table[hashi]._state ! EMPTY){// 存在且key值为k查找成功if (_table[hashi]._state EXIST _table[hashi]._data.first k){return _table[hashi];}// 存在但key值不为k/已经被删除继续查找hashi (hashi 1) % _table.size();if (hashi start)// 极端情况下无空位除了EXIST就是DELETE最多走一圈{break;}}return nullptr;}bool insert(const pairK, V kv){// 已存在不插入if (find(kv.first)){return false;}// 再插入超出负载因子上限(0.7)需扩容后再插入if ((double)_n / _table.size() 0.7){//建立新的哈希表容量为原来的2倍hash_tableK, V, HashToKey newHashTable;auto newTable newHashTable._table;newTable.resize(_table.size() * 2);// 遍历旧表在新表中建立新的哈希映射for (auto e : _table){if (e._state EXIST){newHashTable.insert(e._data);}}//两个空间交换_table.swap(newTable);}int hashi HashToKey()(kv.first) % _table.size();// 若发生哈希冲突用线性探测解决// 碰到 空or删除即可插入while (_table[hashi]._state EXIST){hashi (hashi 1) % _table.size();}_table[hashi]._data kv;_table[hashi]._state EXIST;_n;return true;}// 删除键值为k的元素bool erase(const K k){Data* p find(k);if (p){p-_state DELETE;_n--;return true;}else{return false;}}private:vectorData _table;size_t _n; // 哈希表中有效数据的个数};
}3.1.2 二次探测 二次探测是线性探测的优化一定程度上缓解了线性探测中因为堆积现象而导致的查找、插入效率低下的问题。 二次探测找下一个空位置的方法为 H i H_i Hi ( H 0 H_0 H0 i 2 i^2 i2 )% m, 或者 H i H_i Hi ( H 0 H_0 H0 - i 2 i^2 i2 )% m。其中i 1,2,3… H 0 H_0 H0是通过哈希函数Hash(x)对元素的关键码 key 进行计算得到的哈希地址m是表的大小。
插入 拿上面用线性探测解决插入时遇到哈希冲突的例子试着用二次探测解决。如下为过程要插入key值为16的元素求出hashi为6发生哈希冲突线性探测找下一个空位置插入要查找5次才能找到下一个空位置。 而用二次探测只需要三次即可找到下一个空位。
可见二次探测的效率一般优于线性探测。 研究表明若使用二次探测当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。 二次探测关键部分代码
int hash0 HashToKey()(kv.first) % _table.size();
int hashi 0, i 0;
while (_table[hashi]._state EXIST)
{hashi (hash0 i * i) % _table.size();i;
}3.2 开散列
3.2.1 链地址法的思想
开散列的概念 开散列法又叫链地址法(拉链法)首先对关键码集合用哈希函数计算哈希地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表头结点存储在哈希表中。这样的哈希表结构称之为哈希桶。 开散列的思想 总而言之开散列解决哈希冲突的思想就是将发生冲突的元素都存储在一个集合中这个存放冲突键值元素的集合称为桶。物理结构上是一个单链表。 ⭕哈希桶的结构如图所示 可见哈希桶有一个指针数组数组中的指针指向桶的头结点无桶则为NULL每一个桶中存放的都是发生哈希冲突的元素。
3.2.2 哈希桶的模拟实现 其实unordered_map和unordered_set的底层就是用哈希桶封装的有了红黑树封装map和set的知识储备接下来我们模拟实现哈希桶时尽可能考虑设计为方便unordered_map和unordered_set封装的模式。 哈希桶的节点
template class T
// T是value_type
// unordered_map的T是pairK,V
// unordered_set的T是Kstruct hash_node
{hash_node(const T data):_data(data),_next(nullptr){}T _data; // 数据域hash_nodeT* _next; // 指向同一个桶的下一个节点
};哈希桶的大致框架
// T在set中是K在map中是pairK,V
// Hash是将key值转换为整型的哈希算法
// KeyOfT是用于取出节点数据中的键值key的仿函数类型template class K, class T, class Hash, class KeyOfT
class hash_table
{typedef hash_nodeT Node;
public:// 构造函数hash_table():_table(10, nullptr), _n(0){}// 析构函数~hash_table(){for (auto cur : _table){while (cur){Node* next cur-_next;delete cur;cur next;}}}//各类接口//...
private:vectorNode* _table;// 指针数组存放每一个桶的头指针size_t _n;// 有效元素个数
};哈希桶的插入 检测哈希桶中是否存在键值重复的元素已存在则不插入不存在则继续下一步检测负载因子是否到达上限若是则需扩容后再进行下一步通过哈希函数计算插入元素的哈希地址即元素对应的桶号元素进入相应的桶头插对于单链表头插的效率比尾插高。 1️⃣查重
要想找出哈希桶中是否存在键值重复的元素写一个find函数并复用是比较简单的。哈希桶的查找很简单若想查找到键值为key的元素先通过哈希函数计算桶编号再从对应的桶中遍历找键值为key的元素即可。平均时间复杂度为O(1)。
代码实现
Node* find(const K key)
{// 计算桶号size_t hashi Hash()(key) % _table.size();// 遍历桶查找key遍历链表Node* cur _table[hashi];while (cur){if (KeyOfT()(cur-_data) key) // KeyOfT()用于取出节点数据中的键值key{return cur;}cur cur-_next;}return nullptr;
}2️⃣ 哈希桶的扩容 开散列哈希桶一般规定负载因子为1即有效个数和指针数组长度相等时再插入需要先扩容。 tips如果开散列的扩容采用闭散列的方式遍历旧表重新计算旧表中元素的映射位置插入新表因为开散列是以链表的形式存在而非连续空间那么创建新节点插入新表删除旧表的的节点将会是一个很大的消耗。因此哈希桶的扩容应该将旧表的节点取而用之而非先新建再删旧。
后两步都很简单不必过多解释直接上最终insert函数的代码。
bool insert(const T data)
{KeyOfT kot;// 1.已存在不插入if (find(kot(data))){return false;}// 2.当负载因子1时扩容if (_n _table.size()){vectorNode* newTable(2 * _table.size(), nullptr);for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;// 将当前节点插到新表对应的位置中size_t new_hashi Hash()(kot(cur-_data)) % newTable.size();cur-_next newTable[new_hashi];newTable[new_hashi] cur;cur next;}// 清除旧表中遗留的指针避免二次释放空间_table[i] nullptr;}//交换两个表_table.swap(newTable);}// 3.计算哈希地址size_t hashi Hash()(kot(data)) % _table.size();Node* newNode new Node(data);// 4.头插有效元素个数1newNode-_next _table[hashi];_table[hashi] newNode;_n;return true;
}哈希桶的元素删除
bool erase(const K key)
{size_t hashi Hash()(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (KeyOfT()(cur-_data) key){// 删除if (cur _table[hashi])//删头要特殊处理{_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;
}四、封装unordered_map和unordered_set 接下来我们要模拟C标准库中用哈希桶来封装unordered_map和unordered_set。 4.1 哈希表的迭代器 与list、rb_tree的迭代器一样哈希表的迭代器也需要一个指针来指向节点。不同的是由于哈希表的桶是分散的即有多条链表因此迭代器前进时有可能会从一个桶跳转到另一个桶 如图it指向31时指向it检测到当前桶已经没有下一个元素故跳转到下一个桶的头结点。 ⭕要想做到能找到下一个不为空的桶迭代器就必须要能访问哈希表的指针数组下面是hashIterator类的实现
注意由于哈希桶单链表的结构所以它的迭代器是单向的只能不能--。
template class K, class T, class Hash, class KeyOfT
struct hashIterator
{typedef hash_nodeT Node;typedef hashIteratorK, T, Hash, KeyOfT Self;typedef hash_tableK, T, Hash, KeyOfT hash_table;hashIterator(Node* node, hash_table* pht) // 构造函数:_node(node), _pht(pht){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}Self operator(){if (_node-_next){_node _node-_next;}else{KeyOfT kot;size_t hashi Hash()(kot(_node-_data)) % _pht-_table.size();// 找下一条链size_t i 0;for (i hashi 1; i _pht-_table.size(); i){if (_pht-_table[i]){_node _pht-_table[i];break;}}// 找不到if (i _pht-_table.size()){_node nullptr;}}return *this;}bool operator(const Self it) const{return _node it._node _pht it._pht;}bool operator!(const Self it) const{return !operator(it);}Node* _node; // 指向节点的指针hash_table* _pht;// 指向哈希表指针数组的指针
};4.2 改造哈希表 改造hash_table类使得其能够适配unordered_map和unordered_set的封装。 template class K, class T, class Hash, class KeyOfT
class hash_table
{// 迭代器中可能会访问hash_table类所以要设置为友元类template class K, class T, class Hash, class KeyOfTfriend struct hashIterator;template class K, class T, class Hash, class KeyOfTfriend struct const_hashIterator;typedef hash_nodeT Node;public:// 为什么普通迭代器和const迭代器不封装成一个类见下文分析typedef hashIteratorK, T, Hash, KeyOfT iterator;typedef const_hashIteratorK, T, Hash, KeyOfT const_iterator;hash_table():_table(10, nullptr), _n(0){}~hash_table(){for (auto cur : _table){while (cur){Node* next cur-_next;delete cur;cur next;}}}// 迭代器的接口iterator begin(){// 找第一个元素即可for (int i 0; i _table.size(); i){if (_table[i]){return iterator(_table[i], this);}}return iterator(nullptr, this);}iterator end(){// 设空迭代器为endreturn iterator(nullptr, this);}const_iterator begin() const{for (int i 0; i _table.size(); i){if (_table[i]){return const_iterator(_table[i], this);//const迭代器构造函数异常?下面具体分析}}return const_iterator(nullptr, this);}const_iterator end() const{return const_iterator(nullptr, this);}iterator find(const K key){size_t hashi Hash()(key) % _table.size();Node* cur _table[hashi];while (cur){if (KeyOfT()(cur-_data) key){return iterator(cur, this);}cur cur-_next;}return end();}const_iterator find(const K key) const{size_t hashi Hash()(key) % _table.size();Node* cur _table[hashi];while (cur){if (KeyOfT()(cur-_data) key){return const_iterator(cur, this);}cur cur-_next;}return end();}iterator erase(const K key){size_t hashi Hash()(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (KeyOfT()(cur-_data) key){// 删除iterator next iterator(cur, this);if (cur _table[hashi])//删头要特殊处理{_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_n;return next;}prev cur;cur cur-_next;}return end();}//insert的返回值类型要修改为pairiterator, bool与库中一致。pairiterator, bool insert(const T data){KeyOfT kot;// 已存在不插入iterator fit find(kot(data));if (fit ! end()){return make_pair(fit, false);}// 当负载因子1时扩容if (_n _table.size()){vectorNode* newTable(2 * _table.size(), nullptr);for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;// 将当前节点插到新表对应的位置中size_t new_hashi Hash()(kot(cur-_data)) % newTable.size();cur-_next newTable[new_hashi];newTable[new_hashi] cur;cur next;}// 清除旧表中遗留的指针避免二次释放空间_table[i] nullptr;}//交换两个表_table.swap(newTable);}size_t hashi Hash()(kot(data)) % _table.size();Node* newNode new Node(data);// 头插newNode-_next _table[hashi];_table[hashi] newNode;_n;return make_pair(iterator(newNode, this), true);}private:vectorNode* _table;size_t _n;// 有效元素个数
};⭕这里有一个问题链表、红黑树的const迭代器和普通迭代器用的是同一个类只不过用Ref和Ptr两个模板参数来区分它们。而哈希表这里const迭代器和普通迭代器用的是两个类因为无法用Ref和Ptr两个模板参数来区分它们。原因如下 看这段代码
const_iterator begin() const
{for (int i 0; i _table.size(); i){if (_table[i]){return const_iterator(_table[i], this);}}return const_iterator(nullptr, this);
}如果const_iterator底层是hashIterator类在下面这句代码会出现错误。
return const_iterator(_table[i], this);因为此时this是const类型的指针而_table[i]相当于this-_table.operator[](i)由于this是const类型其指向的类的成员变量也是const类型所以_table是const类型的vector类因此_table[i]取出来的值是const Node*类型的。
两个参数都是const指针类型但hashIterator类的两个成员变量都是非cons指针t类型构造函数无法完成构造存在权限放大。
Node* _node;
hash_table* _pht;因此const迭代器另起一个类const_hashIterator。
template class K, class T, class Hash, class KeyOfT
struct const_hashIterator
{typedef hash_nodeT Node;typedef const_hashIteratorK, T, Hash, KeyOfT Self;typedef hashIteratorK, T, Hash, KeyOfT iterator;typedef hash_tableK, T, Hash, KeyOfT hash_table;const_hashIterator(const Node* node, const hash_table* pht):_node(node), _pht(pht){}// 普通迭代器构造const迭代器const_hashIterator(const iterator it):_node(it._node), _pht(it._pht){}const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}Self operator(){if (_node-_next){_node _node-_next;}else{KeyOfT kot;size_t hashi Hash()(kot(_node-_data)) % _pht-_table.size();// 找下一条链size_t i 0;for (i hashi 1; i _pht-_table.size(); i){if (_pht-_table[i]){_node _pht-_table[i];break;}}// 找不到if (i _pht-_table.size()){_node nullptr;}}return *this;}bool operator(const Self it) const{return _node it._node _pht it._pht;}bool operator!(const Self it) const{return !operator(it);}const Node* _node;const hash_table* _pht;
};unordered_map和unordered_set的封装与红黑树封装map和set的思路很像这里就不过多赘述直接上代码。 4.3 unordered_set的封装
namespace ckf
{template class K, class HashtoKey HashKclass unordered_set{struct SetKov{const K operator()(const K v){return v;}};public:typedef typename bucketHash::hash_tableK, K, HashtoKey, SetKov::const_iterator iterator;typedef typename bucketHash::hash_tableK, K, HashtoKey, SetKov::const_iterator const_iterator;//迭代器iterator begin() const{return _ht.begin();}iterator end() const{return _ht.end();}iterator find(const K key) const{return _ht.find(key);}pairiterator, bool insert(const K key){pairiterator, bool pRet _ht.insert(key);return make_pair(iterator(pRet.first), pRet.second); // 需要将普通迭代器转化为const迭代器}iterator erase(const K key){return _ht.erase(key);// 这里自动将普通迭代器转化为const迭代器}private:bucketHash::hash_tableK, K, HashtoKey, SetKov _ht;};
}4.4 unordered_map的封装
namespace ckf
{template class K,class V,class HashtoKey HashKclass unordered_map{struct MapKov{const K operator()(const pairconst K, V kv){return kv.first;}};public:typedef typename bucketHash::hash_tableK, pairconst K, V, HashtoKey, MapKov::iterator iterator;typedef typename bucketHash::hash_tableK, pairconst K, V, HashtoKey, MapKov::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();}pairiterator, bool insert(const pairconst K, V kv){return _ht.insert(kv);}iterator erase(const K key){return _ht.erase(key);}V operator[](const K key){return (_ht.insert(make_pair(key, V())).first)-second;}private:bucketHash::hash_tableK, pairconst K, V, HashtoKey, MapKov _ht;};
}本文完。如果这篇文章对你有帮助动动小手点赞收藏加关注支持博主你的支持是我最大的动力
