哈希表模板参数改造

针对模板参数V改造

因为不同容器的类型不同,如果是unordered_map,V代表一个键值对,如果unordered_set,V代表Key值,而底层哈希表并不知道上层容器所要传递的
V模板参数类型,为了与哈希表的模板参数区分,我们将哈希表中的V模板参
数改为T.

增加仿函数获取具体数据类型.

例如: 在哈希表中当我们使用Find函数进行查找时:
如果上层传递的数据类型为Key值,我们就可以直接与查找数据比较.
如果上层传递的数据类型为pair<K,V>键值对,我们就不可以直接比较,需要利用仿函数获取键值对的first进行比较.
unordered_set仿函数SetKeyOfT代码:

struct SetKeyOfT              //根据map还是set传递不同数据类型给底层.
{
const K& operator()(const K& key)
{
return key;
}
};
1
2
3
4
5
6
7

unordered_map仿函数MapKeyOfT代码:

struct MapKeyOfT                   //根据map还是set传递不同数据类型给底层.
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;   //获取pair<K,V>键值对中的first.
}
};
1
2
3
4
5
6
7

所以,我们要在哈希表模板参数中增加一个仿函数KeyOfT.
如果是unordered_set,就传 SetKeyOfT类型的仿函数.
如果是unordered_map,就传MapKeyOfT类型的仿函数.

模板参数转换图示如下:

额外说明:
1: 我们对原先哈希表中的Hash进行了修改,不要缺省值,因为我们肯定是使用上层容器传递不同的仿函数类型,所以在unordered_set与unordered_map中传递仿函数类型.

哈希表的正向迭代器

正向迭代器中的内置成员:

哈希表正向迭代器有两个内置成员:
1: 结点指针
2: 哈希表的指针

template < class K, class T, class Hash, class KeyOfT >
class HashTable;                   //重新声明哈希表类模板.
//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{
typedef HashNode<T> Node; //重新定义哈希结点的类型为Node.
typedef HashTable<K, T, KeyOfT, HashFunc> HT; //重新定义哈希表的类型为HT.
typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //重新定义正向迭代器的类型为Self.

Node* _node; //结点指针
HT* _pht; //哈希表指针
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意:
因为迭代器中要使用到哈希表类型,所以我们在哈希表迭代器前面必须声明一下哈希表类模板.

正向迭代器的成员函数

以下成员函数较为简单,就不另外说明:

_HashIterator( Node* node,HT* pht )  //初始化列表
:_node(node)
, _pht(pht)
{
}
        
T& operator*()                     //解引用运算符重载
{
return _node->_data;
}

T* operator->()                 //->运算符重载
{
return &_node->_data;
}

bool operator!=( const Self& s ) const  //外面增加const可以使const对象也能调用该成员函数.
{
return _node != s._node;  //实质上是迭代器中的_node比较
}


bool operator==( const Self& s )const 
{
return _node == s._node;
}

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

前置++运算符重载:
前置++运算符重载主要有两个步骤:
1: 如果当前结点指针的下一个结点存在,则结点指针指向下一个结点.

2: 如果当前结点指针的下一个结点不存在:
(1): 通过哈希函数计算哈希桶的位置.

(2): 在哈希表中,从哈希桶中的下一个位置开始遍历查找.
如果哈希桶存在,则将结点指针指向该哈希桶.
如果哈希表遍历完还没有找到,则说明这是哈希表中的最后一个数据的迭代器,则结点指针指向空,表明最后一个数据的下一个结点.

Self& operator++()
{
if (_node->_next)  //在当前桶中迭代
{
_node = _node->_next;
}
                  //如果该哈希桶迭代完毕，则在哈希表中找下一个哈希桶迭代寻找．
else
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _pht->_table.size(); //迭代器访问哈希表的私有成员
size_t i = hashi + 1;

for (;  i < _pht->_table.size(); ++i)
{
if (_pht->_table[i])
{
_node = _pht->_table[i];
break;                       //++完就退出.
}
        
}
if (i == _pht->_table.size())        //此时,这也说明正式哈希桶迭代器的end.
{
_node = nullptr;
}

}

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

哈希表插入函数的修改(适用于unordered_map)

为了支持unordered_map中的[]操作符重载,我们针对哈希表中的插入函数返回值进行修改
(1): 如果哈希表中已有所给数据,则返回已有数据的迭代器与插入结果(失败)所构成的键值对.

(2): 如果哈希表没有所给数据,则将新数据头插该哈希桶组成的单链表上,返回新插入结点指针构造与插入结果(成功)组成的键值对.

插入函数代码如下:

      pair< Iterator,bool> Insert(const T& data)
   {
Hash hash;
KeyOfT kot;                                                   
Iterator ret = Find(kot(data));                    
if (ret != end())
{
return make_pair( ret, false);
}
if (_size == _table.size())                                //扩容.
{
//size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
vector<Node*> newTable;
newTable.resize(GetNextPrime(_table.size()), nullptr); 

Hash hash;
//从旧表结点移动映射新表.
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;

size_t hashi = hash(kot(cur->_data)) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;

cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
               
}
size_t hashi = hash(kot(data)) % _table.size();
Node* newNode = new Node(data);
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_size;
return make_pair(Iterator(newNode,this),true);                //如果是新插入的数据,则返回新插入结点构造的迭代器与插入结果组成的pair.
}

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

一个类型K去做set和unordered_set他的模板参数的必备条件.

set容器模板参数:
(1):set模板参数要求能够支持小于比较,例如:二叉搜索树查找成员函数中,我们可以利用compare仿函数将当前结点值与所给值比较,从而决定cur遍历左子树还是右子树,为了能够支持大于比较的,我们可以交换一下实参位置,这也间接支持了大于比较.并且条件判断,进而也支持了等于.
unordered_set容器模板参数要求:
(1)针对于K类型(指针,打浮点数,有符号整型)可以转换为无符号整数取模.对于string,日期类类型,这两个类型与整型类型无关的,此时不可以直接强转为整数,需要相应的提供将该类型转换为整数的仿函数.

(2):K类型对象能够支持等于比较(因为在查找中就是要确定存储的对象与所传的对象是否相等,例如Data日期类),如果不支持需要额外提供等于比较的仿函数.

unordered_set的模拟实现(完整代码)

在上述中,我们已经将unordered_set重点内容讲解完毕,剩下的成员函数只需要复用哈希表中的就可以了.

namespace yzh
{
//2:因为我们使用map,set是将实参传给,map,set的所以当string类型取模时要在map,set中写仿函数.
template < class K,class Hash = HashFunc<K>> //1:由第二个模板参数决定要存储的数据.
class unordered_set
{
struct SetKeyOfT                                  //根据map还是set传递不同数据类型给底层.
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashBucket::HashTable< K,K,Hash,SetKeyOfT>::Iterator iterator;  //重新定义一下迭代器类型为iterator.

iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}

pair<iterator,bool> Insert(const K& key)
{
return _ht.Insert(key);
}
private:
HashBucket::HashTable<K,K,Hash,SetKeyOfT> _ht;
};
void test_set()                      //测试
{
unordered_set<int> set;
set.Insert(1);
set.Insert(2);
set.Insert(3);

unordered_set<int>::iterator it = set.begin();
while ( it != set.end() )
{
cout << *it << " ";
++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

unordered_map的实现(完整代码)

在上述中,我们已经将unordered_map重点内容讲解完毕,剩下的成员函数只需要复用哈希表中的就可以了.

namespace yzh
{
template < class K, class V, class Hash = HashFunc<K> >            //由第二个模板参数决定要存储的数据类型,
class unordered_map
{
struct MapKeyOfT                                             //根据map还是set传递不同数据类型给底层.
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};

public:
typedef typename HashBucket::HashTable< K, pair<K, V>, Hash, MapKeyOfT>::Iterator iterator;//重新定义一下迭代器类型为iterator.
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
   pair<iterator,bool> Insert( const pair<K, V>& kv )
{
return _ht.Insert(kv);
}
   V& operator[]( const K& key  )                      //给一个key,返回V的引用.
   {
   pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));   //如果插入失败,返回已有数据的迭代器与返回结果组成的pair.                                                 //如果插入成功,返回新插入数据的迭代器与返回结果组成的pair.
   return ret.first->second;
   }
   
private:
HashBucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;     //map和set都知道传递什么来类型的仿函数,以及要传递的数据类型.
};
void test_map()
{
unordered_map<string, string> dict;
dict.Insert(make_pair("sort", "排序"));
dict.Insert(make_pair("string", "排序"));

unordered_map<string,string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second  << endl;
     ++it;
}
}

void testmap1()
{
unordered_map<string, int> countMap;
string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","西瓜","苹果","香蕉" };
for (auto& e : arr)
{
countMap[e]++;
}

for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << 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

适用于unordered_set和unordered_map的哈希表代码

#include <map>
#include <vector>
#include <string>
#include <string>
#include <iostream>
using namespace std;
template < class K >                   //仿函数的默认值,如果不显示传就会默认调用.
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

template< >                                 //1:对于常见类型,为了方便,我们可以对类模板进行特化.
struct HashFunc <string>                    //并且根据实参所传类型,优先走特化版本.                                     
{
size_t operator()(const string& key)
{
size_t  val = 0;
for (auto& ch : key) //遍历string,将一个个字母替换成ASCI码进行相加.
{
val += ch;
}
return val;
}
};
namespace HashBucket
{

template < class T >
struct HashNode
{
T _data;
HashNode<T>* _next;

HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};

template < class K, class T, class Hash, class KeyOfT >
class HashTable;

template < class K, class T, class Hash, class KeyOfT >
struct _HashIterator
{
typedef HashNode<T> Node;
typedef HashTable< K, T, Hash, KeyOfT> HT;
typedef _HashIterator< K, T, Hash, KeyOfT> Self;
Node* _node;
    HT* _pht;

_HashIterator( Node* node,HT* pht )
:_node(node)
, _pht(pht)
{
}
        
T& operator*()
{
return _node->_data;
}

T* operator->()
{
return &_node->_data;
}

Self& operator++()
{
if (_node->_next)  //在当前桶中迭代
{
_node = _node->_next;
}
                  //如果该哈希桶迭代完毕，则在哈希表中找下一个哈希桶迭代寻找．
else
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _pht->_table.size(); //迭代器访问哈希表的私有成员
size_t i = hashi + 1;

for (;  i < _pht->_table.size(); ++i)
{
if (_pht->_table[i])
{
_node = _pht->_table[i];
break;                       //++完就退出.
}
        
}
if (i == _pht->_table.size())        //此时,这也说明正式哈希桶迭代器的end.
{
_node = nullptr;
}

}

return *this;
}

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 Hash, class KeyOfT >
struct HashTable
{
typedef HashNode<T> Node;
template < class K, class T, class Hash, class KeyOfT > //为了迭代器能够访问哈希表的私有成员,我们设为迭代器是哈希表的
                                                        //友元,类模板声明友元需要增加类模板.
friend struct  _HashIterator;

public:
typedef _HashIterator< K, T, Hash, KeyOfT> Iterator;

Iterator begin()//获取第一个迭代器
{
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
{
return Iterator( _table[i], this );
}
}
return end();
}

Iterator end()  //获取最后一个迭代器
{
return Iterator(nullptr, this);
}

size_t GetNextPrime(size_t prime)
{
const int PRIMECOUNT = 28;
//素数序列
const size_t primeList[PRIMECOUNT] =
{
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 = 0; i < PRIMECOUNT; i++)
{
if (primeList[i] > prime)         //从这个数组里面取第一个大于prime的值.
return primeList[i];
}
return primeList[i];                 //虽然数据不可能那么大,但是也有可能不会走if判断,
 // 所以从语法上来说还要考虑所给值prime大于素数数组整个数据的情况.
}

~HashTable()         //vvector会调用析构函数,但是哈希桶必须自己写.
{
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
//cout << "~HushTable()" << endl;

}

bool  Erase(const K& key)
{
if (_table.size() == 0)
{
return true;
}
Hash hash;
size_t hashi = hash(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_size;
return true;
}

prev = cur;
cur = cur->_next;
}
return false;
}

      pair< Iterator,bool> Insert(const T& data)
   {
Hash hash;
KeyOfT kot;

                                                   //去重
Iterator ret = Find(kot(data));                    //如果该数据已经有了,则返回已有数据的迭代器与插入结果构成的pair.
if (ret != end())
{
return make_pair( ret, false);
}
if (_size == _table.size())                                //扩容.
{
//size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
vector<Node*> newTable;
newTable.resize(GetNextPrime(_table.size()), nullptr);    //扩容

Hash hash;
//从旧表结点移动映射新表.
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;

size_t hashi = hash(kot(cur->_data)) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;

cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
               
}
size_t hashi = hash(kot(data)) % _table.size();
Node* newNode = new Node(data);
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_size;
return make_pair(Iterator(newNode,this),true);                //如果是新插入的数据,则返回新插入结点构造的迭代器与插入结果组成的pair.
}

     Iterator Find(const K& key)
{
if (_table.size() == 0)        //表为空,就返回nullptr.
{
return end();
}
Hash hash;
KeyOfT kot;
size_t hashi = hash(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return Iterator(cur, this);
}
cur = cur->_next;
}
return end();
}

size_t size()
{
return _size;
}
size_t TablesSize()          //表的长度
{
return  _table.size();
}

size_t BucketNum()           //有多少个桶被用了.
{
size_t Num = 0;
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
{
++Num;
}
}
return Num;
}
size_t MaxBucketLenth()
{
size_t maxLen = 0;
for (size_t i = 0; i < _table.size(); ++i)
{
size_t len = 0;
Node* cur = _table[i];
while (cur)
{
++len;
cur = cur->_next;
}
if (len > maxLen)
{
maxLen = len;
}
}
return maxLen;
}
private:
vector<Node*> _table;
size_t _size = 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
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