热门标签
热门文章
- 1Vulnstack----1、ATT&CK红队评估实战靶场一_vulnstack靶场
- 2对于mp4 ios和mac safari不能播放问题处理
- 3【Android】 android suspend/resume总结（1）
- 4Unity如何使用手机进行调试（真机）_unity 真机调试
- 5自行搭建 Bitwarden 服务_服务器自建bitwarden
- 6理解Flink算子链
- 7微信小程序修改svg颜色_小程序 svg 颜色
- 8循环神经网络在自动翻译中的成果与未来
- 9关于 Linux Polkit 权限提升漏洞(CVE-2021-4034)的修复方法_poikit高危修复
- 10jmeter接口测试教程及接口测试流程_jmeter接口压测流程详解
当前位置: article > 正文
【C++/STL】：哈希表的改造 -- 封装unordered系列
作者：黑客灵魂 | 2024-08-21 06:40:48
赞
踩
【C++/STL】：哈希表的改造 -- 封装unordered系列
点击跳转至文章： 【C++/STL】：哈希 – 线性探测&哈希桶
前言
与map/set的封装类似，unordered系列的底层本质上也是复用，通过对哈希表的改造，再分别套上一层 unordered_map 和 unordered_set 的 “壳子”，以达到 “一表二用” 的目的。
各个结构的改造不再详细说明，细节可参考文章：map和set的封装
unordered系列的底层哈希表是用哈希桶结构实现的。
一，哈希表的改造
1. 哈希表的基本框架
(1) K：关键码类型；
(2) V:：不同容器V的类型不同，如果unordered_map，V代表一个键值对，如果是unordered_set，V 为 K；
(3) KeyOfValue：因为V的类型不同，通过value取key的方式就不同，详细见unordered_map/set的实现；
(4) Hash：哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模。
template <class K, class T, class KeyOfT,class Hash = HashFunc<K>> class HashBucket { //友元 template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash > friend struct HTIterator; typedef BucketNode<T> Node; public: typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator; typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator; //其他核心操作…… private: vector<Node*> _tables; //指针数组 size_t _n = 0; //表中数据的个数 }; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
2. 对哈希桶节点结构的改造
template <class T>
struct BucketNode
{
BucketNode<T>* _next;
T _data;
BucketNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
3. 哈希表的迭代器
3.1 迭代器类
(1) 这里的迭代器需要：构造节点指针和哈希表对象指针。
(2) 这里的迭代器类需要用到哈希表类的结构，相互依存，要用前置声明。
//前置声明 template <class K, class T, class KeyOfT, class Hash > class HashBucket; template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash > struct HTIterator { //需要节点指针，哈希表对象指针 typedef BucketNode<T> Node; typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self; const HashBucket<K, T, KeyOfT, Hash>* _pht; Node* _node; HTIterator(Node* node, const HashBucket<K, T, KeyOfT, Hash>* pht) :_node(node) ,_pht(pht) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) { return _node != s._node; } Self& operator++() { if (_node->_next) { _node = _node->_next; } else { KeyOfT kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size(); hashi++; while (hashi < _pht->_tables.size()) { if (_pht->_tables[hashi]) break; hashi++; } if (hashi == _pht->_tables.size()) //走完了 _node = nullptr; //End() else _node = _pht->_tables[hashi]; } return *this; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
3.2 Begin() 和 End()
Iterator Begin() { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) return Iterator(cur, this); } return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin()const { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) return ConstIterator(cur, this); } return End(); } ConstIterator End()const { return ConstIterator(nullptr, this); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
四，哈希表相关接口的改造
4.1 Find 函数的改造
Iterator Find(const K& key) { Hash hs; KeyOfT kot; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return Iterator(cur, this); else cur = cur->_next; } return End(); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
4.2 Insert 函数的改造
pair<Iterator, bool> Insert(const T& data) { Hash hs; KeyOfT kot; Iterator it = Find(kot(data)); if (it != End()) return make_pair(it, false); //扩容 if (_n == _tables.size()) { vector<Node*> newTables; newTables.resize(_tables.size() * 2, nullptr); //把旧表的节点挪到新表 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { size_t hashi = hs(kot(cur->_data)) % newTables.size(); Node* newnode = new Node(cur->_data); //头插 newnode->_next = newTables[hashi]; newTables[hashi] = newnode; 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 make_pair(Iterator(newnode, this), true); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
五，哈希表改造的完整代码
HashTable.h
template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; //对string类型的特化 template<> struct HashFunc<string> { size_t operator()(const string& s) { size_t n = 0; for (auto ch : s) { n += ch; n *= 31; } return n; } }; template <class T> struct BucketNode { BucketNode<T>* _next; T _data; BucketNode(const T& data) :_data(data) , _next(nullptr) {} }; //前置声明 template <class K, class T, class KeyOfT, class Hash > class HashBucket; template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash > struct HTIterator { //需要节点指针，哈希表对象指针 typedef BucketNode<T> Node; //typedef HTIterator<K, T, KeyOfT, Hash> Self; typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self; const HashBucket<K, T, KeyOfT, Hash>* _pht; Node* _node; HTIterator(Node* node, const HashBucket<K, T, KeyOfT, Hash>* pht) :_node(node) ,_pht(pht) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) { return _node != s._node; } Self& operator++() { if (_node->_next) { _node = _node->_next; } else { KeyOfT kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size(); hashi++; while (hashi < _pht->_tables.size()) { if (_pht->_tables[hashi]) break; hashi++; } if (hashi == _pht->_tables.size()) //走完了 _node = nullptr; //End() else _node = _pht->_tables[hashi]; } return *this; } }; template <class K, class T, class KeyOfT,class Hash = HashFunc<K>> class HashBucket { //友元 template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash > friend struct HTIterator; typedef BucketNode<T> Node; public: typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator; typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator; Iterator Begin() { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) return Iterator(cur, this); } return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin()const { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) return ConstIterator(cur, this); } return End(); } ConstIterator End()const { return ConstIterator(nullptr, this); } HashBucket() { _tables.resize(10, nullptr); } //依次把每个桶释放 ~HashBucket() { 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; } } pair<Iterator, bool> Insert(const T& data) { Hash hs; KeyOfT kot; Iterator it = Find(kot(data)); if (it != End()) return make_pair(it, false); //扩容 if (_n == _tables.size()) { vector<Node*> newTables; newTables.resize(_tables.size() * 2, nullptr); //把旧表的节点挪到新表 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { size_t hashi = hs(kot(cur->_data)) % newTables.size(); Node* newnode = new Node(cur->_data); //头插 newnode->_next = newTables[hashi]; newTables[hashi] = newnode; 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 make_pair(Iterator(newnode, this), true); } Iterator Find(const K& key) { Hash hs; KeyOfT kot; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return Iterator(cur, this); else cur = cur->_next; } return End(); } bool Erase(const T& data) { Hash hs; KeyOfT kot; size_t hashi = hs(kot(data)) % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; while (cur) { if (cur->_data == data) { //第一个节点 if (prev == nullptr) { _tables[hashi] = nullptr; } else { //在节点中间 prev->_next = cur->_next; } delete cur; _n--; return true; } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _tables; //指针数组 size_t _n = 0; //表中数据的个数 };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
六，unordered_set 的封装实现
unordered_set 的底层为哈希表，因此只需在unordered_set 内部封装哈希表，即可将该容器实现出来。
unordered_set .h
#include "HashTable.h" namespace bit { template <class K, class Hash = HashFunc<K>> class unordered_set { struct SetOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename HashBucket<K, const K, SetOfT, Hash>::Iterator iterator; typedef typename HashBucket<K, const K, SetOfT, Hash>::ConstIterator 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(); } pair<iterator, bool> insert(const K& key) { return ht.Insert(key); } private: bit::HashBucket<K,const K, SetOfT, Hash> ht; }; void Print(const unordered_set<int>& s) { unordered_set<int>::const_iterator it = s.begin(); while (it != s.end()) { // *it += 1; cout << *it << " "; ++it; } cout << endl; } void Test_set() { //int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; int a[] = { 16,3,7,11,9,26,18,14,15 }; unordered_set<int> s; for (auto e : a) s.insert(e); for (auto e : s) cout << e << " "; cout << endl; Print(s); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
七，unordered_map 的封装实现
unordered_map 的底层结构就是哈希表，因此在map中直接封装一个哈希表，然后将其接口包装下即可。
unordered_map.h
#include "HashTable.h" namespace bit { template <class K, class V, class Hash = HashFunc<K>> class unordered_map { struct MapOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: typedef typename HashBucket<K, pair<const K, V>, MapOfT, Hash>::Iterator iterator; typedef typename HashBucket<K, pair<const K, V>, MapOfT, Hash>::ConstIterator 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(); } pair<iterator, bool> insert(const pair<K,V>& kv) { return ht.Insert(kv); } V& operator[](const K& key) { pair<iterator, bool> ret = ht.Insert(make_pair(key, V())); return ret.first->second; } private: bit::HashBucket<K, pair<const K, V>, MapOfT, Hash> ht; }; void Test_map() { unordered_map<string, string> dict; dict.insert({ "left","左边" }); dict.insert({ "right","右边" }); dict.insert({ "insert","插入" }); dict["left"] = "剩余，左边"; bit::unordered_map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { //it->first += 'x'; //err it->second += 'y'; //ok cout << it->first << ":" << it->second << endl; ++it; } cout << endl; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/1010621
推荐阅读
相关标签
