福州电子商务网站建设,老板让我做网站负责人,windows优化大师如何卸载,浙江网站建设哪家专业哈希表模板参数的控制
首先需要明确的是#xff0c;unordered_set是K模型的容器#xff0c;而unordered_map是KV模型的容器。
要想只用一份哈希表代码同时封装出K模型和KV模型的容器#xff0c;我们必定要对哈希表的模板参数进行控制。
为了与原哈希表的模板参数进行区分…哈希表模板参数的控制
首先需要明确的是unordered_set是K模型的容器而unordered_map是KV模型的容器。
要想只用一份哈希表代码同时封装出K模型和KV模型的容器我们必定要对哈希表的模板参数进行控制。
为了与原哈希表的模板参数进行区分这里将哈希表的第二个模板参数的名字改为T。
templateclass K, class T
class HashTable如果上层使用的是unordered_set容器那么传入哈希表的模板参数就是key和key。
templateclass K
class unordered_set {
public://...
private:HashTableK, K _ht;//传入底层哈希表的是K和K
};但如果上层使用的是unordered_map容器那么传入哈希表的模板参数就是key以及key和value构成的键值对。
templateclass K, class V
class unordered_map {
public://...
private:HashTableK, pairK, V _ht;//传入底层哈希表的是K以及K和V构成的键值对
};也就是说哈希表中的模板参数T的类型到底是什么完全却决于上层所使用容器的种类。 而哈希结点的模板参数也应该由原来的K、V变为T
上层容器是unordered_set时传入的T是键值哈希结点中存储的就是键值。上层容器是unordered_map时传入的T是键值对哈希结点中存储的就是键值对。
更改模板参数后哈希结点的定义如下
templateclass T
struct HashNode {HashNodeT *_next;T _data;HashNode(const T data): _data(data), _next(nullptr) {}
};在哈希映射过程中我们需要获得元素的键值然后通过哈希函数计算出对应的哈希地址进行映射。
现在由于我们在哈希结点当中存储的数据类型是T这个T可能就是一个键值也可能是一个键值对对于底层的哈希表来说它并不知道哈希结点当中存储的数据究竟是什么类型因此需要由上层容器提供一个仿函数用于获取T类型数据当中的键值。
因此unordered_map容器需要向底层哈希表提供一个仿函数该仿函数返回键值对当中的键值。
templateclass K, class V
class unordered_map {
public:struct MapKeyOft {const K operator()(const pairK, V kv) {return kv.first;}};private:HashTableK, pairconst K, V, MapKeyOft _ht;
};而虽然unordered_set容器传入哈希表的T就是键值但是底层哈希表并不知道上层容器的种类底层哈希表在获取键值时会统一通过传入的仿函数进行获取因此unordered_set容器也需要向底层哈希表提供一个仿函数。
templateclass K
class unordered_set {
public:struct SetKeyOfT {const K operator()(const K key) {return key;}};private:HashTableK, K, SetKeyOfT _ht;
};因此底层哈希表的模板参数现在需要增加一个用于接收上层容器提供的仿函数。
templateclass K, class T, class KeyOfT
class HashTablestring类型无法取模问题
经过上面的分析后我们让哈希表增加了一个模板参数此时无论上层容器是unordered_set还是unordered_map我们都能够通过上层容器提供的仿函数获取到元素的键值。
但是在我们日常编写的代码中用字符串去做键值key是非常常见的事比如我们用unordered_map容器统计水果出现的次数时就需要用各个水果的名字作为键值。
而字符串并不是整型也就意味着字符串不能直接用于计算哈希地址我们需要通过某种方法将字符串转换成整型后才能代入哈希函数计算哈希地址。
但遗憾的是我们无法找到一种能实现字符串和整型之间一对一转换的方法因为在计算机中整型的大小是有限的比如用无符号整型能存储的最大数字是4294967295而众多字符能构成的字符串的种类却是无限的。
鉴于此无论我们用什么方法将字符串转换成整型都会存在哈希冲突只是产生冲突的概率不同而已。
因此现在我们需要在哈希表的模板参数中再增加一个仿函数用于将键值key转换成对应的整型。
templateclass K, class T, class KeyOfT, class HashFunc HashK
class HashTable若是上层没有传入该仿函数我们则使用默认的仿函数该默认仿函数直接返回键值key即可但是用字符串作为键值key是比较常见的因此我们可以针对string类型写一个类模板的特化
templateclass K
struct HashFunc {size_t operator()(const K key) {return key;}
};// 特化模板传string的话就走这个
template
struct HashFuncstring {size_t operator()(const string s) {size_t hash 0;for (auto ch: s) {hash ch;hash * 31;}return hash;}
};哈希表正向迭代器的实现
哈希表的正向迭代器实际上就是对哈希结点指针进行了封装但是由于在实现运算符重载时可能需要在哈希表中去寻找下一个非空哈希桶因此每一个正向迭代器中都应该存储哈希表的地址。
代码
//前置声明
templateclass K, class T, class KeyOft, class Hash HashFuncK
class HashTable;templateclass K, class T, class Ref, class Ptr, class KeyOft, class Hash
struct HashIterator {typedef HashNodeT Node;typedef HashTableK, T, KeyOft, Hash HT;//Ref和Ptr可能是T和T*也可能是const T/const T*需要创建一个支持普通转换为const的迭代器typedef HashIteratorK, T, Ref, Ptr, KeyOft, Hash Self;typedef HashIteratorK, T, T , T *, KeyOft, Hash iterator;//正向迭代器HashIterator(Node *node, HT *ht): _node(node), _ht(ht) {}//正向迭代器实现反向迭代器,不能只靠self如果self传的就是const迭代器再加上const就有问题了HashIterator(const iterator it): _node(it._node), _ht(it._ht) {}Ref operator*() {return _node-_data;}Ptr operator-() {return _node-_data;}bool operator!(const Self s) {return _node ! s._node;}bool operator(const Self s) {return _node s._node;}Self operator() {if (_node-_next ! nullptr) {_node _node-_next;} else {//找下一个不为空的桶KeyOft kot;Hash hash;// 算出我当前的桶位置size_t hashi hash(kot(_node-_data)) % _ht-_tables.size();hashi;while (hashi _ht-_tables.size()) {if (_ht-_tables[hashi] ! nullptr) {_node _ht-_tables[hashi];break;} else {hashi;}}//没有找到的话返回_node为空if (hashi _ht-_tables.size()) {_node nullptr;}return *this;}return *this;}Node *_node;//迭代器指针HT *_ht; //哈希表用于定位下一个桶
};注意 哈希表的迭代器类型是单向迭代器没有反向迭代器即没有实现–运算符的重载若是想让哈希表支持双向遍历可以考虑将哈希桶中存储的单链表结构换为双链表结构。
正向迭代器实现后我们需要在哈希表的实现当中进行如下操作
进行正向迭代器类型的typedef需要注意的是为了让外部能够使用typedef后的正向迭代器类型iterator我们需要在public区域进行typedef。由于正向迭代器中运算符重载函数在寻找下一个结点时会访问哈希表中的成员变量_table而_table成员变量是哈希表的私有成员因此我们需要将正向迭代器类声明为哈希表类的友元。将哈希表中查找函数返回的结点指针改为返回由结点指针和哈希表地址构成的正向迭代器。将哈希表中插入函数的返回值类型改为由正向迭代器类型和布尔类型所构成的键值对。
完整的HashTable
#pragma once
#include cstdlib
#include ctime
#include iostream
#include utility
#include vector
using namespace std;templateclass K
struct HashFunc {size_t operator()(const K key) {return key;}
};// 特化模板传string的话就走这个
template
struct HashFuncstring {size_t operator()(const string s) {size_t hash 0;for (auto ch: s) {hash ch;hash * 31;}return hash;}
};templateclass T
struct HashNode {HashNodeT *_next;T _data;HashNode(const T data): _data(data), _next(nullptr) {}
};//前置声明
templateclass K, class T, class KeyOft, class Hash HashFuncK
class HashTable;templateclass K, class T, class Ref, class Ptr, class KeyOft, class Hash
struct HashIterator {typedef HashNodeT Node;typedef HashTableK, T, KeyOft, Hash HT;//Ref和Ptr可能是T和T*也可能是const T/const T*需要创建一个支持普通转换为const的迭代器typedef HashIteratorK, T, Ref, Ptr, KeyOft, Hash Self;typedef HashIteratorK, T, T , T *, KeyOft, Hash iterator;//正向迭代器HashIterator(Node *node, HT *ht): _node(node), _ht(ht) {}//正向迭代器实现反向迭代器,不能只靠self如果self传的就是const迭代器再加上const就有问题了HashIterator(const iterator it): _node(it._node), _ht(it._ht) {}Ref operator*() {return _node-_data;}Ptr operator-() {return _node-_data;}bool operator!(const Self s) {return _node ! s._node;}bool operator(const Self s) {return _node s._node;}Self operator() {if (_node-_next ! nullptr) {_node _node-_next;} else {//找下一个不为空的桶KeyOft kot;Hash hash;// 算出我当前的桶位置size_t hashi hash(kot(_node-_data)) % _ht-_tables.size();hashi;while (hashi _ht-_tables.size()) {if (_ht-_tables[hashi] ! nullptr) {_node _ht-_tables[hashi];break;} else {hashi;}}//没有找到的话返回_node为空if (hashi _ht-_tables.size()) {_node nullptr;}return *this;}return *this;}Node *_node;//迭代器指针HT *_ht; //哈希表用于定位下一个桶
};templateclass K, class T, class KeyOft, class Hash// Hash用于将key转换成可以取模的类型
class HashTable {
public:typedef HashNodeT Node;typedef HashIteratorK, T, T , T *, KeyOft, Hash iterator;typedef HashIteratorK, T, const T , const T *, KeyOft, Hash const_iterator;templateclass K1, class T1, class Ref1, class Ptr1, class KeyOft1, class Hash1friend struct HashIterator;//用于迭代器访问HashTable中的private成员变量即_tables、public:~HashTable() {for (auto cur: this-_tables) {while (cur) {Node *next cur-_next;delete cur;cur next;}cur nullptr;}}iterator begin() {Node *cur nullptr;for (size_t i 0; i _tables.size(); i) {cur _tables[i];if (cur ! nullptr) {break;}}return iterator(cur, this);}iterator end() {return iterator(nullptr, this);}const_iterator begin() const {Node *cur nullptr;for (size_t i 0; i _tables.size(); i) {cur _tables[i];if (cur ! nullptr) {break;}}return const_iterator(cur, this);}const_iterator end() const {return const_iterator(nullptr, this);}//查找Key也是K类型iterator Find(const K key) {if (this-_tables.size() 0) {return iterator(nullptr, this);}KeyOft kot;//模板参数用来区分是kv还是v由上层map、set传模板参数过来(通过仿函数实现)Hash hash;size_t hashi hash(key) % this-_tables.size();Node *cur this-_tables[hashi];while (cur) {if (kot(cur-_data) key) {return iterator(cur, this);}cur cur-_next;}return iterator(nullptr, this);}//删除的值key为K类型bool Erase(const K key) {Hash hash;KeyOft kot;size_t hashi hash(key) % this-_tables.size();Node *prev nullptr;Node *cur this-_tables[hashi];while (cur) {if (kot(cur-_data) key) {if (prev nullptr) {this-_tables[hashi] cur-_next;} else {prev-_next cur-_next;}delete cur;return true;} else {prev cur;cur cur-_next;}}return false;}// 扩容优化使用素数扩容size_t GetNextPrime(size_t prime) {// SGIstatic const int _stl_num_primes 28;static const uint64_t _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};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[_stl_num_primes - 1];}//插入的类型是T类型可能是K可能是pairK,V 通过模板参数传过来pairiterator, bool Insert(const T data) {Hash hash;// 仿函数用于不能取模的值KeyOft kot;// 已经有这个数就不用插入了iterator it Find(kot(data));//如果it不是end()说明找到了数就不用插入返回迭代器和falseif (it ! end()) {return make_pair(it, false);}// 负载因子 1时扩容if (this-n this-_tables.size()) {// size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;size_t newsize this-GetNextPrime(_tables.size());vectorNode * newtables(newsize, nullptr);for (auto cur: this-_tables) {// cur是Node*while (cur) {// 保存下一个Node *next cur-_next;// 头插到新表size_t hashi hash(kot(cur-_data)) % newtables.size();cur-_next newtables[hashi];newtables[hashi] cur;cur next;}}_tables.swap(newtables);}size_t hashi hash(kot(data)) % this-_tables.size();// 头插Node *newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;this-n;//插入成功返回通过newnode和this构造迭代器返回true。return make_pair(iterator(newnode, this), true);}// 获取哈希表索引最大长度(哈希桶长度)size_t MaxBucketSize() {size_t max 0;for (int i 0; i _tables.size(); i) {auto cur _tables[i];size_t size 0;while (cur) {size;cur cur-_next;}printf([%d]-%d\n, i, size);if (size max) {max size;}if (max 5121) {printf(%d, i);break;}}return max;}private:vectorNode * _tables;size_t n 0;// 存储有效数据的个数
};封装unordered_set的代码
#pragma once
#include HashTable.htemplateclass K, class Hash HashFuncK
class unordered_set {
public:struct SetKeyOfT {const K operator()(const K key) {return key;}};public:typedef typename HashTableK, K, SetKeyOfT, Hash::const_iterator iterator;typedef typename HashTableK, K, SetKeyOfT, Hash::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中的iterator是const类型的而Insert返回的是普通迭代器pairiterator, 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);}private:HashTableK, K, SetKeyOfT, Hash _ht;
};封装unordered_map的代码
#pragma once#include HashTable.h
templateclass K, class V, class Hash HashFuncK
class unordered_map {
public:struct MapKeyOft {const K operator()(const pairK, V kv) {return kv.first;}};//typename 告诉编译器引入的是一个类型而不是成员typedef typename HashTableK, pairconst K, V, MapKeyOft, Hash::iterator iterator;typedef typename HashTableK, pairconst K, V, MapKeyOft, Hash::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 pairK, V kv) {return _ht.Insert(kv);}V operator[](const K key) {pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}iterator find(const K key) {return _ht.Find(key);}bool erase(const K key) {return _ht.Erase(key);}private:HashTableK, pairconst K, V, MapKeyOft, Hash _ht;
};测试
#include unordered_map.h
#include unordered_set.h
#include iostream
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;
}//自定义Hash模板最后一个参数传自定义类型的话需要自己写
struct HashDate {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;}
};struct unordered_map_Test {static void unordered_map_Test1() {unordered_mapint, int mp;mp.insert(make_pair(1, 1));mp.insert(make_pair(2, 2));mp.insert(make_pair(3, 3));unordered_mapint, int::iterator it mp.begin();while (it ! mp.end()) {cout it-first it-second endl;it;}cout endl;}static void unordered_map_Test2() {string arr[] {西瓜, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉, 梨};unordered_mapstring, int countMap;for (auto e: arr) {countMap[e];}for (auto kv: countMap) {cout kv.first kv.second endl;}}static void unordered_map_Test3() {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_mapDate, int, HashDate countMap;for (auto e: a) {countMap[e];}for (auto kv: countMap) {cout kv.first : kv.second endl;}}
};struct unordered_set_Test {static void unordered_set_Test1() {unordered_setint s;s.insert(1);s.insert(3);s.insert(2);s.insert(7);s.insert(8);unordered_setint::iterator it s.begin();while (it ! s.end()) {cout *it ;//(*it) 1;it;}cout endl;}
};int main() {unordered_set_Test::unordered_set_Test1();unordered_map_Test::unordered_map_Test1();unordered_map_Test::unordered_map_Test2();unordered_map_Test::unordered_map_Test3();return 0;
}
