-
【C++模拟实现】哈希与unorder_set和unorder_map关联式容器的模拟实现
【C++模拟实现】哈希与unorder_set和unorder_map关联式容器的模拟实现
作者：爱写代码的刚子
时间：2023.10.4
前言：本篇博客主要介绍C++中的哈希以及两大重要的容器：unorder_set和unorder_map，以及模拟实现的注意事项
哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经 过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( logN)，搜索的效率取决 于搜索过程中元素的比较次数。
理想的搜索方法:可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过 某种函数(hashFunc)****使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函 数可以很快找到该元素。
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表 **(Hash Table)(**或者称散列表)
哈希的闭散列法（开放定址法）
- 线性探测法：
enum STATE{ EXIST, EMPTY, DELETE }; template<class K,class V> struct HashDate { pair<K,V> _kv; STATE _state=EMPTY; }; template<class K> struct HashFunc { size_t operator()(const K&key) { return (size_t)key; } }; template<> struct HashFunc<string> { size_t operator()(const string&str) { size_t size=0; for(auto e: str) { size*=131; size+=e; } return size; } }; template<class K,class V,class HashDefault=HashFunc<K> > class __HashTable { public: __HashTable() { _table.resize(10); } bool insert(const pair<K,V>& kv) { //扩容 if(_n*10/_table.size()>=7) { size_t newsize= _table.size()*2; //重新映射到新表 __HashTable<K,V> newhash; newhash._table.resize(newsize); for(int i=0;i<_table.size();i++) { newhash.insert(_table[i]._kv); } _table.swap(newhash._table); } HashDefault hf; size_t hashi=hf(kv.first)%_table.size(); while(_table[hashi]._state==EXIST) { ++hashi; hashi%=_table.size(); } _table[hashi]._kv=kv; _table[hashi]._state=EXIST; ++_n; return true; } HashDate<const K,V>* find(const K&key) { HashDefault hf; size_t hashi=hf(key)%_table.size(); while(_table[hashi]._state!=EMPTY) { if(_table[hashi]._state!=EMPTY&&hf(_table[hashi]._kv.first)==hf(key)) { return (HashDate<const K,V>*)&_table[hashi]; } ++hashi; hashi%=_table.size(); } return nullptr; } bool erase(const K&key) { HashDate<const K,V>* ret=find(key); if(ret) { ret->_state=DELETE; --_n; return true; } else{ return false; } } private: vector<HashDate<K,V> > _table; size_t _n=0;//C++11 };- 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
-
二次探测法：
与线性探测法类似，将插入和查找的探测元素的顺序变成hashi，hashi+12，hashi+22,hashi+3^2…即可，计算好的哈希地址对哈希表的总大小取模
将线性探测法中的hashi++的逻辑改成
hashi=hashi+i*i;hashi %= _ht.size();即可
研究表明:当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置 都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
哈希的开散列法（哈希桶）
开散列概念
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码 归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
因为扩容时桶的总数改变了，所以每个元素需要重新映射地址，所以有大的性能消耗。理想情况下是每个桶一个元素，可以在桶的个数等于存储的元素个数的时候进行扩容操作。（将原链表节点一个个插入到新的哈希桶）
开散列的模拟实现：
namespace Hash_bucket { template<class K,class V> struct HashNode { HashNode(const pair<K,V>& kv) :_kv(kv) ,_next(nullptr) {} pair<K,V> _kv; HashNode<K,V>* _next; }; template<class K> struct HashFunc { size_t operator()(const K&key) { return (size_t)key; } }; template<> struct HashFunc<string> { size_t operator()(const string&str) { size_t size=0; for(auto e: str) { size*=131; size+=e; } return size; } }; template<class K,class V,class DefaultHashFunc = HashFunc<K> > class HashTable { typedef HashNode<K,V> Node; public: HashTable() :_n(0) { _table.resize(10,nullptr); } ~HashTable()//不要复用erase函数，不然很繁琐 { for(int i=0;i<_table.size();i++) { Node* cur=_table[i]; while(cur) { Node* nextnode = cur->_next; delete cur; cur = nextnode; } _table[i]=nullptr; } _n=0; } bool insert(const pair<K,V>& kv) { DefaultHashFunc hf; if(_n==_table.size()) { size_t newsize=_table.size()*2; HashTable<K,V> _hs; _hs._table.resize(newsize,nullptr); printf("扩容成功\n"); for(int i=0;i<_table.size();i++)//不是单纯的将整个链表牵下来 { Node* cur=_table[i]; while(cur) { size_t hashi =hf(_table[i]->_kv.first)%_hs._table.size(); Node* next=cur->_next; cur->_next=_hs._table[hashi]; _hs._table[hashi]=cur; ++_n; cur=next; } _table[i]=nullptr; } _table.swap(_hs._table); } size_t hashi=hf(kv.first)%_table.size(); //进行头插 Node* newnode=new Node(kv); newnode->_next=_table[hashi]; _table[hashi]=newnode; ++_n; return true; } void Print() const { for(int i=0;i<_table.size();i++) { if(_table[i]==nullptr) { printf("NULLPTR\n"); } else{ Node* cur=_table[i]; printf("[%d]",i); while(cur) { cout<<"->"<<cur->_kv.first; cur=cur->_next; } cout<<endl; } } } Node* Find(const K&key) const { DefaultHashFunc hf; size_t hashi =hf(key)%_table.size(); Node* cur=_table[hashi]; while(cur) { if(hf(cur->_kv.first)==hf(key)) { return cur; } cur=cur->_next; } return nullptr; } bool erase(const K&key) { DefaultHashFunc hf; size_t hashi = hf(key)%_table.size(); Node* prev = nullptr; Node* cur = _table[hashi]; while(cur) { if(hf(cur->_kv.first)==hf(key)) { if(prev==nullptr) { delete cur; return true; } else{ prev->_next = prev->_next->_next; delete cur; } return true; } prev=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
对哈希的开散列式封装unordered系列容器，加上迭代器
#include#include using namespace std; namespace Hash_bucket { template<class K,class T> struct HashNode { HashNode(const T& data) :_data(data) ,_next(nullptr) {} T _data; HashNode<K,T>* _next; }; template<class K> struct DefaultHashFunc { size_t operator()(const K&key) { return (size_t)key; } }; template<> struct DefaultHashFunc<string> { size_t operator()(const string&str) { size_t size=0; for(auto e: str) { size*=131; size+=e; } return size; } }; iterator,需要将HashTable传进去 /同时迭代器和hash表存在一个相互依赖，迭代器用到hash表，hash表用到迭代器 template<class K,class T,class KeyOfT,class HashFunc>//前置声明 class HashTable; //迭代器用到了HashTable中的私有成员_table,所以要在HashTable将迭代器模版声明为友元 template<class K,class T,class Ref,class Ptr,class KeyOfT,class HashFunc>//这里不要给缺省值 struct __HashTable_iterator { typedef HashNode<K,T> Node; typedef __HashTable_iterator<K,T,Ref,Ptr,KeyOfT,HashFunc> Self; typedef __HashTable_iterator<K,T,T&,T*,KeyOfT,HashFunc> Iterator; Node* _node; const HashTable<K,T,KeyOfT,HashFunc>* _pht; __HashTable_iterator(Node* node,const HashTable<K,T,KeyOfT,HashFunc>* pht) :_node(node) ,_pht(pht) {} __HashTable_iterator(const Iterator& it) :_node(it._node) ,_pht(it._pht) {}//如果这个对象是const迭代器，实现的是普通迭代器转为const迭代器， //如果这个对象是普通迭代器，实现的是普通迭代器的拷贝构造。 Self& operator++() { if(_node->_next) { _node=_node->_next; } else{ HashFunc hf; KeyOfT kot; size_t hashi =hf(kot(_node->_data))%_pht->_table.size(); ++hashi; while (hashi<_pht->_table.size()) { if(_pht->_table[hashi]) { _node=_pht->_table[hashi]; return *this; } else{ ++hashi; } } _node=nullptr; } return *this; } bool operator!=(const Self& self) const { return _node!=self._node; } bool operator==(const Self& self) const { return _node==self._node; } Ptr operator->() { return &_node->_data; } Ref operator*()//T& { return _node->_data; } }; template<class K,class T,class KeyOfT,class HashFunc = DefaultHashFunc<K> > class HashTable { template<class U,class I,class Y,class Z,class A,class B>//这里不要给缺省值,两个类不同，最好使用不同的模版参数 friend struct __HashTable_iterator; public: typedef HashNode<K,T> Node; typedef __HashTable_iterator<K,T,T&,T*,KeyOfT,HashFunc> iterator; typedef __HashTable_iterator<K,T,const T&,const T*,KeyOfT,HashFunc> const_iterator; iterator begin() { for(int i=0;i<_table.size();i++) { Node* cur=_table[i]; if(cur) { return iterator(cur,this); } } return iterator(nullptr,this); } iterator end() { return iterator(nullptr,this); } const_iterator begin() const { for(int i=0;i<_table.size();i++) { Node* cur=_table[i]; if(cur) { return iterator(cur,this); } } return const_iterator(nullptr,this); } const_iterator end() const { return const_iterator(nullptr,this); } HashTable() :_n(0) { _table.resize(10,nullptr); } ~HashTable()//不要复用erase函数，不然很繁琐 { for(int i=0;i<_table.size();i++) { Node* cur=_table[i]; while(cur) { Node* nextnode = cur->_next; delete cur; cur = nextnode; } _table[i]=nullptr; } _n=0; } pair<iterator,bool> insert(const T& data) { HashFunc hf; KeyOfT kot; if(_n==_table.size()) { size_t newsize=_table.size()*2; HashTable<K,T,KeyOfT> _hs; _hs._table.resize(newsize,nullptr); printf("扩容成功\n"); for(int i=0;i<_table.size();i++)//不是单纯的将整个链表牵下来 { Node* cur=_table[i]; while(cur) { size_t hashi =hf(kot(_table[i]->_data))%_hs._table.size(); Node* next=cur->_next; cur->_next=_hs._table[hashi]; _hs._table[hashi]=cur; ++_n; cur=next; } _table[i]=nullptr; } _table.swap(_hs._table); } size_t hashi=hf(kot(data))%_table.size(); //进行头插 Node* newnode=new Node(data); newnode->_next=_table[hashi]; _table[hashi]=newnode; ++_n; return make_pair(iterator(newnode,this),true); } void Print() const { KeyOfT kot; for(int i=0;i<_table.size();i++) { if(_table[i]==nullptr) { printf("NULLPTR\n"); } else{ Node* cur=_table[i]; printf("[%d]",i); while(cur) { cout<<"->"<<kot(cur->_data); cur=cur->_next; } cout<<endl; } } } //库里面的返回值为迭代器 iterator Find(const K&key) const //注意，传入的模版参数K不能省略，即使有KeyOfT，但KeyOfT不能取出类型 { HashFunc hf; KeyOfT kot; size_t hashi =hf(key)%_table.size(); Node* cur=_table[hashi]; while(cur) { if(hf(kot(cur->_data))==hf(key)) { return iterator(cur,this); } cur=cur->_next; } return iterator(nullptr,this); } /*pair - 则会释放,所以我们写的unordered_map需要手动写析构函数
//struct DefaultHashFunc中会发生报错 - 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
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
- 413
- 414
- 415
- 416
- 417
- 418
- 419
- 420
- 421
- 422
- 423
- 424
- 425
- 426
- 427
- 428
- 429
- 430
- 431
- 432
- 433
- 434
- 435
- 436
- 437
- 438
- 439
- 440
- 441
- 442
- 443
- 444
- 445
- 446
- 447
- 448
- 449
- 450
- 451
- 452
- 453
- 454
- 455
- 456
- 457
- 458
- 459
- 460
- 461
- 462
- 463
- 464
- 465
- 466
- 467
- 468
- 469
- 470
- 471
- 472
- 473
- 474
- 475
- 476
- 477
- 478
- 479
- 480
- 481
- 482
- 483
- 484
- 485
- 486
unorder_set和unorder_map关联式容器的模拟实现注意事项
由于该模拟实现和set，map的模拟实现方法类似，不做详细记录了，代码注释里记录了一些需要注意的地方。
-
相关阅读:
华为OD:0019-0020:-最小步骤数—删除字符串中出现次数最少的字符
基于小程序探索如何实现数字传媒内容价值最大化
vgg16猫狗识别
聊聊 C# 中的多态底层 (虚方法调用) 是怎么玩的
详解【数据结构】栈和队列
golang中实现一个异步延时程序
蓝桥杯刷题单
Leetcode—392.判断子序列【简单】
《自然语言处理实战：利用Python理解、分析和生成文本》读书笔记：第2章 构建自己的词汇表——分词
MySQL精髓：如何使用ALL一次找到最大值
- 原文地址：https://blog.csdn.net/m0_74215144/article/details/133555599
