-
哈希的模拟实现和封装unorder_map和unorder_set
1， 哈希的概念
哈希也叫散列。它的本质就是映射。我们说的哈希表就是一个数组。
常见的哈希函数
1，直接定址法（重要）
优点：每个值都有一个唯一位置，效率很高，每个数都是一次都能找到。
缺点：适用场景比较局限，通常要求数据是整数，范围集中。2，除留余数法（重要）
开辟固定的一块空间， 用key % size() 算出映射位置。
优点：适用常见广，不受限制。
缺点：存在哈希冲突，并且哈希冲突越多，效率越低。（什么是哈希冲突，就是不同的元素根据相同的哈希哈数算出相同的位置）
如何解决哈希冲突呢？3, 平方取中法（了解）
4，折叠法（了解）
5，随机数法（了解）
6，数学分析法（了解）如何解决哈希冲突呢？
1，闭散列------开放定址法（线性探测 ，二次探测）
线性探测： 算出的位置如果有值，继续向后找空位置， + i (i = 1, 2, 3, 4,)
二次探测：算出的位置如果有元素，也是继续向后找空位置 + i ^ 2 (i = 1, 2 ,3 ,4 ,5).随着冲突的越多，我们需要扩容。什么时候需要扩容呢？ 当负载因子大于0.7的时候。
负载因子 = 当前存储的元素个数 / 空间大小（size（））。2，开散列-----哈希桶/拉链法。数组中存放节点的指针，如果位置相同，则挂在后面
如何去控制负载因子呢？
1，负载因子越小，冲突的概率越低，效率越高，但是浪费的空间越多。
反之， 高， 低， 少。实际中，哈希桶这种结构更加实用。
原因在于： 1，空间利用率高
2，极端情况下可以应对（数据不多，但是全部冲突）。闭散列解决方案的具体实现
大致的框架：
插入函数：
bool Insert(const pair<K, V>& kv) { HashFunc hf; if (Find(kv.first)) //为什么这里不用hf（kv。first）呢？ 因为查找的时候不需要转换成int类型 { return false; } if (_table.size() == 0) { _table.resize(10); } else if ((_n * 10) / _table.size() > 7) //负载因子大于0.7就扩容处理 { //需要扩容处理 HashTable newHash; newHash._table.resize(_table.size() * 2); for (const auto& e : _table) { newHash.Insert(e._kv); } _table.swap(newHash._table); } size_t start = hf(kv.first) % _table.size(); size_t i = 1,index = start; while (_table[index]._state == EXITS) { index += i; //如果是二次探测，只需要改为 index += i^2; index %= _table.size(); i++; } _table[index]._kv = kv; _table[index]._state = EXITS; _n++; return 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
查找
HashDate<K,V>* Find(const K& key) { HashFunc hf; if (_table.size() == 0) return nullptr; size_t start = hf(key) % _table.size(); size_t index = start, i = 1; while (_table[index]._state != EMPTY) { if (_table[index]._state == EXITS && _table[index]._kv.first == key) { return &_table[index]; } index += i; i++; index %= _table.size(); } return nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
删除
bool Erase(const K& key) { HashFunc hf; HashDate<K, V>* ret = Find(hf(key)); if (ret == nullptr) { return false; } ret->_state = DELETE; _n--; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
2，开散列
大致结构：
插入函数
bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } HashFunc hf; if (_table.size() == 0) { _table.resize(10); } else if (_n / _table.size() >= 1) { //扩容处理 HashTable<K, V, HashFunc> newht; newht._table.resize(_table.size() * 2); for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; if (_table[i]) { while (cur) { //只要是获取位置的时候都要用hf去获取对应的整形，因为int可以直接使用，但是string就要进行转换 size_t index = hf(cur->_kv.first) % newht._table.size(); cur->_next = newht._table[index]; //头插 newht._table[index] = cur; cur = cur->_next; newht._n++; } } } _table.swap(newht._table); } size_t index = hf(kv.first) % _table.size(); Node* newnode = new Node(kv); newnode->_next = _table[index]; _table[index] = newnode; _n++; return 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
- 46
- 47
- 48
查找函数
Node* Find(const K& key) { HashFunc hf; if (_table.size() == 0) { return nullptr; } size_t i = hf(key) % _table.size(); Node* cur = _table[i]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
删除函数
bool Erase(const K& key) { HashFunc hf; size_t i = hf(key) % _table.size(); Node* cur = _table[i]; Node* pre = nullptr; while (cur) { if (cur->_kv.first == key) { if (pre == nullptr) { _table[i] = cur->_next; } else { pre->_next = cur->_next; } delete cur; return true; } pre = cur; cur = cur->_next; } return false; }- 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
用哈希桶来封装unordered_set和unordered_map
这个和用红黑树封装map和set类似。
哈希桶封装unordered_set 和unordered_map的时候，如何只用一份代码去封装呢?改装后的hashtable---->主要就是利用仿函数来获得map和set各自的key，并且模拟实现的迭代器。
namespace openHash { //templatetemplate<class T> struct HashNode { HashNode<T>* _next; T _data; HashNode(const T& data) :_next(nullptr) , _data(data) {} }; template<class K> struct Hash { const K& operator()(const K& key) { return key; } }; template<> struct Hash<string> { size_t operator()(const string& s) { size_t val; for (const auto e : s) { val += e; val *= 131; } } }; template<class K, class T, class KeyOfT, class HashFunc> class HashTable; template<class K, class T, class TOfKey, class HashFunc = Hash<K>> struct _table_iterator { typedef HashNode<T> Node; typedef _table_iterator<K, T, TOfKey, HashFunc> Self; typedef HashTable<K, T,TOfKey, HashFunc > HT; HT* _pht; //多存放一个哈希表的指针，方便实现++操作 Node* _node; _table_iterator(HT* pht,Node* node) :_pht(pht) ,_node(node) {} Self& operator++() { if (_node->_next) { _node = _node->_next; } else { HashFunc hf; TOfKey kot; size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //这个_table是私有变量，需要设置友元 index++; while (index < _pht->_table.size()) { if (_pht->_table[index]) { _node = _pht->_table[index]; return *this; } else { index++; } } _node = nullptr; return *this; } } T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } }; template<class K,class T,class TOfKey,class HashFunc = Hash<K>> class HashTable { template<class K, class T, class TOfKey, class HashFunc> friend struct _table_iterator; public: typedef HashNode<T> Node; typedef _table_iterator<K, T, TOfKey, HashFunc> iterator; HashTable() {} HashTable(const HashTable& ht) { _n = ht._n; _table.resize(ht._table.size()); size_t i = 0; for (size_t i = 0; i < ht.size(); i++) { if (ht._table[i]) { Node* cur = ht._table[i]; while (cur) { Node* newnode = Node(cur->_data); newnode->_next = _table[i]; _table[i] = newnode; cur = cur->_next; } } } } HashTable& operator=(HashTable newht) { _n = newht._n; _table.swap(newht._table); return *this; } ~HashTable() { size_t i = 0; for (i = 0; i < _table.size(); i++) { if (_table[i]) { Node* cur = _table[i]; while (cur) { Node* savenext = cur->_next; delete cur; cur = savenext; } } } } iterator begin() { size_t index = 0; while (index < _table.size()) { if (_table[index]) { return iterator(this, _table[index]); } else { index++; } } return end(); } iterator end() { return iterator(this, nullptr); } bool Insert(const T& data) { HashFunc hf; TOfKey kot; if( Find(kot(data)) ) { return false; } if (_table.size() == 0) { _table.resize(10); } else if (_n / _table.size() >= 1) { //这里需要扩容处理 HashTable<K, T, TOfKey, HashFunc> newht; newht._table.resize(_table.size() * 2); for (size_t i = 0; i < _table.size(); i++) { Node* cur = _table[i]; if (_table[i]) { while (cur) { size_t index = hf(kot(cur->_data)) % newht._table.size(); cur->_next = newht._table[index]; //头插 newht._table[index] = cur; cur = cur->_next; newht._n++; } } } _table.swap(newht._table); } size_t index = hf(kot(data)) % _table.size(); Node* newnode = new Node(data); newnode->_next = _table[index]; _table[index] = newnode; _n++; return true; } Node* Find(const K& key) { HashFunc hf; TOfKey kot; if (_table.size() == 0) { return nullptr; } size_t i = hf(key) % _table.size(); Node* cur = _table[i]; while (cur) { if (hf(kot(cur->_data)) == key) { return cur; } cur = cur->_next; } return nullptr; } bool Erase(const K& key) { HashFunc hf; size_t i = hf(key) % _table.size(); Node* cur = _table[i]; Node* pre = nullptr; while (cur) { if (cur->_kv.first == key) { if (pre == nullptr) { _table[i] = cur->_next; } else { pre->_next = cur->_next; } delete cur; return true; } pre = cur; cur = cur->_next; } return false; } private: vector<Node*> _table; size_t _n; }; } - 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
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
unordered_set
#include "Hash.h" namespace chen { template<class K> class unordered_set { struct SetOfKey { const K& operator()(const K& key) { return key; } }; public: typedef typename openHash::HashTable<K, K, SetOfKey>::iterator iterator; bool insert(const K& key) { return _ht.Insert(key); } iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } private: openHash::HashTable<K, K, SetOfKey> _ht; }; }- 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
unorder_map
#include "Hash.h" namespace chen { template <class K, class V> class unordered_map { public: struct MapOfKey { const K& operator()(const pair<K,V>& data) { return data.first; } }; typedef typename openHash::HashTable<K, pair<K, V>, MapOfKey>::iterator iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } bool insert(const pair<K, V>& kv) { return _ht.Insert(kv); } private: openHash::HashTable<K, pair<K, V>, MapOfKey> _ht; }; }- 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
-
相关阅读:
直播视频处理过程
[论文评析]MediaPipe Hands: On-device Real-time Hand Tracking， ArXiv,2020
python安装wind10
开发环境之Spring.profiles.active
GitHub：ViT-pytorch相关学习-视觉分类方向-1
《WEB安全漏洞100讲》（第4讲）CSRF漏洞
【区块链 + 智慧政务】一体化政务数据底座平台 | FISCO BCOS应用案例
quarkus依赖注入之七：生命周期回调
LeetCode 1742. 盒子中小球的最大数量
mmcv的环境 真 TM 难配
- 原文地址：https://blog.csdn.net/CL2426/article/details/126836997
