吉隆网站建设,怎么建免费论坛网站,网站开发遇到的最大困难,代理网店#x1f440;樊梓慕#xff1a;个人主页 #x1f3a5;个人专栏#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》
#x1f31d;每一个不曾起舞的日子#xff0c;都是对生命的辜负 目录
前言
1.哈希桶源码 2.哈希…
樊梓慕个人主页 个人专栏《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》
每一个不曾起舞的日子都是对生命的辜负 目录
前言
1.哈希桶源码 2.哈希表模板参数的控制
3.字符串作为键值如何映射哈希值
3.1BKDRHash算法
4.封装
4.1构造函数
4.拷贝构造
4.2析构函数
4.3赋值运算符重载
4.4正向迭代器
4.4.1定义
4.4.2构造
4.4.3重载解引用*操作符
4.4.4重载箭头-操作符
4.4.5重载与!操作符
4.4.6重载前置操作符
5.源码
哈希表与迭代器封装源码
MyUnordered_set源码
MyUnordered_map源码
测试源码 前言
上次我们模拟实现了闭散列的哈希表与开散列的哈希表但很明显上次实现的很粗糙功能很简单迭代器并没有实现以及泛型编程思想也没有应用那么对于本篇文章我们要用一个哈希表同时封装出unordered_set 与 unordered_map对此我们之前已经成功用一颗红黑树同时封装出set与map大致的思想是类似的只不过这里会略微复杂一些。 欢迎大家收藏以便未来做题时可以快速找到思路巧妙的方法可以事半功倍。 GITEE相关代码樊飞 (fanfei_c) - Gitee.com 1.哈希桶源码
//每个哈希桶中存储数据的结构
templateclass K, class V
struct HashNode
{pairK, V _kv;HashNodeK, V* _next;//构造函数HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}
};//哈希表
templateclass K, class V
class HashTable
{
public:typedef HashNodeK, V Node;//插入函数bool Insert(const pairK, V kv){//1、查看哈希表中是否存在该键值的键值对if (Find(kv.first)) //哈希表中已经存在该键值的键值对不允许数据冗余{return false; //插入失败}//2、判断是否需要调整哈希表的大小if (_n _tables.size()) //负载因子超过1{//增容//a、创建一个新的哈希表新哈希表的大小设置为原哈希表的2倍vectorNode* newTables(_tables.size() * 2, nullptr);//b、将原哈希表当中的结点插入到新哈希表for (size_t i 0; i _tables.size(); i){//取出旧表中的节点重新计算挂到新表桶中Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi cur-_kv.first % newTables.size();//将该结点头插到新哈希表中编号为index的哈希桶中cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr; //该桶取完后将该桶置空}//c、交换这两个哈希表_tables.swap(newTables);}//3、将键值对插入哈希表size_t hashi kv.first % _tables.size(); //通过哈希函数计算出对应的哈希桶编号index除数不能是capacityNode* newnode new Node(kv); //根据所给数据创建一个待插入结点//将该结点头插到新哈希表中编号为index的哈希桶中newnode-_next _tables[hashi];_tables[hashi] newnode;//4、哈希表中的有效元素个数加一_n;return true;}//查找函数HashNodeK, V* Find(const K key){if (_tables.size() 0) //哈希表大小为0查找失败{return nullptr;}size_t hashi key % _tables.size();//遍历编号为index的哈希桶HashNodeK, V* cur _tables[hashi];while (cur) //直到将该桶遍历完为止{if (cur-_kv.first key) //key值匹配则查找成功{return cur;}cur cur-_next;}return nullptr; //直到该桶全部遍历完毕还没有找到目标元素查找失败}//删除函数bool Erase(const K key){//1、通过哈希函数计算出对应的哈希桶编号hashi除数不能是capacitysize_t hashi key % _tables.size();//2、在编号为index的哈希桶中寻找待删除结点Node* prev nullptr;Node* cur _tables[hashi];while (cur) //直到将该桶遍历完为止{if (cur-_kv.first key) //key值匹配则查找成功{//3、若找到了待删除结点则删除该结点if (prev nullptr) //待删除结点是哈希桶中的第一个结点{_tables[hashi] cur-_next; //将第一个结点从该哈希桶中移除}else //待删除结点不是哈希桶的第一个结点{prev-_next cur-_next; //将该结点从哈希桶中移除}delete cur; //释放该结点//4、删除结点后将哈希表中的有效元素个数减一_n--;return true; //删除成功}prev cur;cur cur-_next;}return false; //直到该桶全部遍历完毕还没有找到待删除元素删除失败}private:vectorNode* _tables; //哈希表size_t _n 0; //哈希表中的有效元素个数
}; 2.哈希表模板参数的控制
templateclass K, class T
class HashTable
那么对于unordered_set
templateclass K
class unordered_set
{
public://...
private:HashTableK, K _ht; //传入底层哈希表的是K和K
}; 对于unordered_map
templateclass K, class V
class unordered_map
{
public://...
private:HashTableK, pairK, V _ht; //传入底层哈希表的是K以及K和V构成的键值对
};
即 而哈希结点的模板参数也应该由原来的K、V变为T
上层容器是unordered_set时传入的T是键值哈希结点中存储的就是键值。上层容器是unordered_map时传入的T是键值对哈希结点中存储的就是键值对。
更改模板参数后哈希结点的定义如下
//哈希结点的定义
templateclass T
struct HashNode
{T _data;HashNodeT* _next;//构造函数HashNode(const T data):_data(data), _next(nullptr){}
};
与红黑树类似红黑树需要获取 T 中的key值用来比较大小在哈希映射中我们需要获得 T 的键值然后通过哈希函数计算出对应的哈希地址进行映射。
现在由于我们在哈希结点当中存储的数据类型是T这个T可能就是一个键值也可能是一个键值对对于底层的哈希表来说它并不知道哈希结点当中存储的数据究竟是什么类型因此需要由上层容器提供一个『 仿函数』用于获取T类型数据当中的键值。
对于unordered_map
templateclass K, class V
class unordered_map
{//仿函数struct MapKeyOfT{const K operator()(const pairK, V kv) //返回键值对当中的键值key{return kv.first;}};
public://...
private:HashTableK, pairK, V, MapKeyOfT _ht;
};
而虽然unordered_set容器传入哈希表的T就是键值但是底层哈希表并不知道上层容器的种类底层哈希表在获取键值时会统一通过传入的仿函数进行获取因此unordered_set容器也需要向底层哈希表提供一个仿函数。
对于unordered_set
templateclass K
class unordered_set
{//仿函数struct SetKeyOfT{const K operator()(const K key) //返回键值key{return key;}};
public://...
private:HashTableK, K, SetKeyOfT _ht;
};
因此底层哈希表的模板参数现在需要增加一个用于接收上层容器提供的仿函数。
templateclass K, class T, class KeyOfT
class HashTable 3.字符串作为键值如何映射哈希值
上篇文章我在结尾留下一个问题 除留余数法是映射哈希值的有效方法但是这里我们考虑的都是整型情况下那如果是字符串呢如果key值是字符串字符串可没办法取余数而我们最终是一定要实现泛型编程的我们怎样才能构建出一个通用的映射关系呢 3.1BKDRHash算法
经过实验BKDRHash算法无论是在实际效果还是编码实现中效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie的《The C Programing Language》一书被展示而得名是一种简单快捷的hash算法也是Java目前采用的字符串的hash算法。
因此现在我们需要在哈希表的模板参数中再增加一个『 仿函数』用于将键值key转换成对应的整型。
templateclass K, class T, class KeyOfT, class HashFunc HashK
class HashTable
若是上层没有传入该仿函数我们则使用默认的仿函数该默认仿函数直接返回键值key即可但是用字符串作为键值key是比较常见的因此我们可以针对string类型写一个类模板的『 特化』此时当键值key为string类型时该仿函数就会根据BKDRHash算法返回一个对应的整型。
templateclass K
struct Hash
{size_t operator()(const K key) //返回键值key{return key;}
};
//string类型的特化
template
struct Hashstring
{size_t operator()(const string s) //BKDRHash算法{size_t value 0;for (auto ch : s){value value * 131 ch;}return value;}
};4.封装
4.1构造函数
我们知道哈希表在插入之前一定size0因为如果size0就无法计算哈希值所以我们之前说在构造这里处理让哈希表创建出来之后就有一定大小的空间。
HashTable()
{_tables.resize(10, nullptr); //构造10个大小的空间默认存放空指针_n 0; //实际存储个数为0
}
4.拷贝构造
4.2析构函数
因为哈希表当中存储的结点都是new出来的因此在哈希表被析构时必须进行结点的释放。在析构哈希表时我们只需要依次取出非空的哈希桶遍历哈希桶当中的结点并进行释放即可。
~HashTable()
{for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}
}
4.3赋值运算符重载
实现赋值运算符重载函数时可以通过参数间接调用拷贝构造函数之后将拷贝构造出来的哈希表和当前哈希表的两个成员变量分别进行交换即可当赋值运算符重载函数调用结束后拷贝构造出来的哈希表会因为出了作用域而被自动析构此时原哈希表之前的数据也就顺势被释放了。
HashTable operator(HashTable ht)
{//交换哈希表中两个成员变量的数据_tables.swap(ht._table);swap(_n, ht._n);return *this; //支持连续赋值
}
4.4正向迭代器
哈希表的正向迭代器实际上就是对哈希结点指针进行了封装但是由于在实现运算符重载时可能需要在哈希表中去寻找下一个非空哈希桶因此每一个正向迭代器中都应该存储哈希表的地址。
4.4.1定义
//正向迭代器
templateclass K, class T, class KeyOfT, class Hash HashK
struct __HTIterator
{typedef HashNodeT Node; //哈希结点的类型typedef HashTableK, T, KeyOfT, Hash HT; //哈希表的类型typedef __HTIteratorK, T, KeyOfT, Hash Self; //正向迭代器的类型Node* _node; //结点指针HT* _ht; //哈希表的地址
};
4.4.2构造
因此在构造正向迭代器时我们不仅需要对应哈希结点的指针还需要该哈希结点所在哈希表的地址。
__HTIterator(Node* node, HT* ht):_node(node), _ht(ht)
{}
4.4.3重载解引用*操作符
T operator*()
{return _node-_data; //返回哈希结点中数据的引用
}
4.4.4重载箭头-操作符
T* operator-()
{return _node-_data; //返回哈希结点中数据的地址
}
4.4.5重载与!操作符
bool operator!(const Self s) const
{return _node ! s._node; //判断两个结点的地址是否不同
}bool operator(const Self s) const
{return _node s._node; //判断两个结点的地址是否相同
}
4.4.6重载前置操作符
前置的逻辑我们只需要额外考虑以下可能会换桶的情况即可。
若当前结点不是当前哈希桶中的最后一个结点则后走到当前哈希桶的下一个结点。若当前结点是当前哈希桶的最后一个结点则后走到下一个非空哈希桶的第一个结点。
Self operator()
{if (_node-_next){// 当前桶还是节点_node _node-_next;}else{// 当前桶走完了找下一个桶KeyOfT kot;Hash hs;size_t hashi hs(kot(_node-_data)) % _ht-_tables.size();// 找下一个桶hashi;while (hashi _ht-_tables.size()){if (_ht-_tables[hashi]){_node _ht-_tables[hashi];break;}hashi;}// 后面没有桶了if (hashi _ht-_tables.size()){_node nullptr;}}return *this;
} 注意 哈希表的迭代器类型是单向迭代器没有反向迭代器所以没有实现–运算符的重载。 5.源码
在具体实现时需要注意迭代器与哈希表的相互引用由于迭代器实现在哈希表前面而编译器只会向前寻找哈希表的定义所以会发生迭代器不认识哈希表的情况这是就需要一个前置声明具体看代码中的体现而迭代器要访问哈希表中的private成员所以要在哈希表中声明迭代器为友元。
哈希表与迭代器封装源码
#pragma oncetemplateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 特化
template
struct HashFuncstring
{size_t operator()(const string s){size_t hash 0;for (auto e : s){hash e;hash * 131;}return hash;}
};namespace Open_Hash
{templateclass Tstruct HashNode{HashNodeT* _next;T _data;HashNode(const T data):_next(nullptr), _data(data){}};// 前置声明templateclass K, class T, class KeyOfT, class Hashclass HashTable;templateclass K, class T, class KeyOfT, class Hashstruct __HTIterator{typedef HashNodeT Node;typedef HashTableK, T, KeyOfT, Hash HT;typedef __HTIteratorK, T, KeyOfT, Hash Self;Node* _node;HT* _ht;__HTIterator(Node* node, HT* ht):_node(node), _ht(ht){}T operator*(){return _node-_data;}Self operator(){if (_node-_next){// 当前桶还是节点_node _node-_next;}else{// 当前桶走完了找下一个桶KeyOfT kot;Hash hs;size_t hashi hs(kot(_node-_data)) % _ht-_tables.size();// 找下一个桶hashi;while (hashi _ht-_tables.size()){if (_ht-_tables[hashi]){_node _ht-_tables[hashi];break;}hashi;}// 后面没有桶了if (hashi _ht-_tables.size()){_node nullptr;}}return *this;}bool operator!(const Self s){return _node ! s._node;}};templateclass K, class T, class KeyOfT, class Hashclass HashTable{//迭代器要访问哈希表的私有成员所以要声明友元templateclass K, class T, class KeyOfT, class Hashfriend struct __HTIterator;typedef HashNodeT Node;public:typedef __HTIteratorK, T, KeyOfT, Hash iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){// 找到第一个桶的第一个节点if (_tables[i]){return iterator(_tables[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}HashTable(){_tables.resize(10, nullptr);_n 0;}~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}bool Insert(const T data){KeyOfT kot;if (Find(kot(data)))return false;Hash hs;// 负载因子到1就扩容if (_n _tables.size()){vectorNode* newTables(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){// 取出旧表中节点重新计算挂到新表桶中Node* cur _tables[i];while (cur){Node* next cur-_next;// 头插到新表size_t hashi hs(kot(cur-_data)) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi hs(kot(data)) % _tables.size();Node* newnode new Node(data);// 头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}Node* Find(const K key){KeyOfT kot;Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K key){KeyOfT kot;Hash hs;size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){// 删除if (prev){prev-_next cur-_next;}else{_tables[hashi] cur-_next;}delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;}private:vectorNode* _tables; // 指针数组size_t _n;};}
MyUnordered_set源码
#pragma once#includeOpen_Hash.hnamespace MyHash
{templateclass K, class Hash HashFuncKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename Open_Hash::HashTableK, const K, SetKeyOfT, Hash::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const K key){return _ht.Insert(key);}private:Open_Hash::HashTableK, const K, SetKeyOfT, Hash _ht;};void test_set1(){unordered_setint us;us.insert(3);us.insert(1);us.insert(5);us.insert(15);us.insert(45);us.insert(7);unordered_setint::iterator it us.begin();while (it ! us.end()){//*it 100;cout *it ;it;}cout endl;for (auto e : us){cout e ;}cout endl;}
}
MyUnordered_map源码
#pragma once#includeOpen_Hash.hnamespace MyHash
{templateclass K, class V, class Hash HashFuncKclass unordered_map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename Open_Hash::HashTableK, pairconst K, V, MapKeyOfT, Hash::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const pairK, V kv){return _ht.Insert(kv);}private:Open_Hash::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;};void test_map1(){unordered_mapstring, string dict;dict.insert(make_pair(sort, 排序));dict.insert(make_pair(left, 左面));dict.insert(make_pair(right, 右面));for (auto kv : dict){//kv.first x;kv.second y;cout kv.first : kv.second endl;}}
}
测试源码
#includeiostream
#includestring
#includevectorusing namespace std;#includeOpen_Hash.h#includeMyUnordered_map.h
#includeMyUnordered_set.hint main()
{MyHash::test_set1();MyHash::test_map1();return 0;
}如果你对该系列文章有兴趣的话欢迎持续关注博主动态博主会持续输出优质内容
博主很需要大家的支持你的支持是我创作的不竭动力
~ 点赞收藏关注 ~
