五、完整代码段

HashTable.h

1. #pragma once
2. #include<vector>
3. #include<iostream>
4. using namespace std;
5. 
6. namespace OpenHash
7. {
8.  //哈希仿函数
9.  template<class K>
10.   struct Hash
11.   {
12.     size_t operator()(const K& key)
13.     {
14.       return key;
15.     }
16.   };
17. 
18.   //string仿函数
19.   template<>
20.   struct Hash<string>//模板特化
21.   {
22.     size_t operator()(const string& s)
23.     {
24.       size_t value = 0;
25.       for (auto e : s)
26.       {
27.         value += e;
28.         value *= 131;
29.       }
30. 
31.       return value;
32.     }
33.   };
34. 
35.   template<class T>
36.   struct HashNode
37.   {
38.     HashNode<T>* _next;
39.     T _data;
40. 
41.     HashNode(const T& data)
42.       :_data(data)
43.       , _next(nullptr)
44.     {}
45.   };
46. 
47.   //前置声明HashTable,因为HashTable类中使用了__HTIterator，且__HTIterator中使用了HashTable类的指针，为什么要用指针
48.   //C++编译器自上而下编译源文件的时候，对每一个数据的定义，总是需要知道定义的数据类型的大小。在预先声明语句class HashTable;之后，编译器已经知道HashTable是一个类，但是其中的数据却是未知的，因此HashTable类型的大小也不知道，这样就造成了编译失败；将__HTIterator中的_node更改为HashTable指针类型之后，由于在特定的平台上，指针所占的空间是一定的（在Win32平台上是4字节，在64位平台上是8字节），这样可以通过编译
49.     // 前置声明
50.   template<class K, class T, class KeyOfT, class HashFunc>
51.   class HashTable;
52. 
53.   // 迭代器
54.   template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
55.   struct __HTIterator
56.   {
57.     typedef HashNode<T> Node;//哈希节点
58.     typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;//实现++、--
59.     typedef HashTable<K, T, KeyOfT, HashFunc> HT;//哈希表
60.     Node* _node;
61.     HT* _pht;
62. 
63.     __HTIterator(Node* node, HT* pht)
64.       :_node(node)//哈希节点
65.       , _pht(pht)//哈希表
66.     {}
67. 
68.     Self& operator++()
69.     {
70.       //不是当前位置最后一个节点
71.       if (_node->_next)
72.       {
73.         _node = _node->_next;
74.       }
75.       else//是当前位置最后一个节点
76.       {
77.         KeyOfT kot;
78.         HashFunc hf;
79. 
80.         size_t index = hf(kot(_node->_data)) % _pht->_table.size();
81. 
82.         //找哈希表中下一个不为空的位置
83.         ++index;
84.         while (index < _pht->_table.size())
85.         {
86.           if (_pht->_table[index])//不为空
87.           {
88.             _node = _pht->_table[index];
89.             return *this;
90.           }
91.           else//为空
92.           {
93.             ++index;
94.           }
95.         }
96.         _node = nullptr;//后面的所有位置都为空，_node置空，返回当前位置即可
97.       }
98. 
99.       return *this;
100.    }
101. 
102.    T& operator*()
103.    {
104.      return _node->_data;
105.    }
106. 
107.    T* operator->()
108.    {
109.      return &_node->_data;
110.    }
111. 
112.    bool operator != (const Self& s) const
113.    {
114.      return _node != s._node;
115.    }
116. 
117.    bool operator == (const Self& s) const
118.    {
119.      return _node == s._node;
120.    }
121.  };
122. 
123.  template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
124.  class HashTable
125.  {
126.    typedef HashNode<T> Node;
127. 
128.    template<class K,class T,class KeyOfT,class HashFunc>
129.    friend struct __HTIterator;
130.  public:
131.    typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;
132. 
133.    //构造函数,default指定生成默认构造函数
134.    HashTable() = default;
135. 
136.    //拷贝构造
137.    HashTable(const HashTable& ht)
138.    {
139.      _n = ht._n;//存储有效数据的个数一致
140.      _table.resize(ht._table.size());//开同样大小的空间
141. 
142.      //遍历ht，将ht的每个结点都拷贝到_table中
143.      for (size_t i = 0; i < ht._table.size(); i++)
144.      {
145.        Node* cur = ht._table[i];
146.        while (cur)
147.        {
148.          Node* copy = new Node(cur->_data);
149. 
150.          //头插到新表
151.          copy->_next = _table[i];//copy的下一个桶为_table[i]
152.          _table[i] = copy;//把copy作为当前位置的第一个桶
153.          cur = cur->_next;//cur往下移         
154.        }
155.      }
156. 
157.    }
158. 
159.    //赋值运算符重载
160.    HashTable& operator=(HashTable ht)
161.    {
162.      _table.swap(ht._table);
163.      swap(_n, ht._n);
164. 
165.      return *this;
166.    }
167. 
168.    //析构
169.    ~HashTable()
170.    {
171.      for (size_t i = 0; i < _table.size(); i++)
172.      {
173.        Node* cur = _table[i];
174.        while (cur)
175.        {
176.          Node* next = cur->_next;
177.          delete cur;
178.          cur = next;
179.        }
180.        _table[i] = nullptr;
181.      }
182.    }
183. 
184.    iterator begin()
185.    {
186.      size_t i = 0;
187.      while (i < _table.size())
188.      {
189.        if (_table[i])
190.        {
191.          return iterator(_table[i], this);
192.        }
193.        ++i;
194.      }
195. 
196.      return end();
197.    }
198. 
199.    iterator end()
200.    {
201.      return iterator(nullptr, this);
202.    }
203. 
204.    size_t GetNextPrime(size_t prime)
205.    {
206.      const int PRIMECOUNT = 28;
207.      static const size_t primeList[PRIMECOUNT] =
208.      {
209.        53ul,97ul,193ul,389ul,769ul,
210.        1543ul,3079ul,6151ul,12289ul,24593ul,
211.        49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
212.        1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
213.        50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
214.        1610612741ul, 3221225473ul, 4294967291ul
215.      };
216. 
217.      size_t i = 0;
218.      for (; i < PRIMECOUNT; i++)
219.      {
220.        if (primeList[i] > prime)
221.        {
222.          return primeList[i];
223.        }
224.      }
225. 
226.      return primeList[i];
227.    }
228. 
229.    //插入
230.    pair<iterator,bool> Insert(const T& data)
231.    {
232.      KeyOfT kot;
233.      auto ret = Find(kot(data));
234.      if (ret != end())
235.      {
236.        return make_pair(ret,false);
237.      }
238. 
239.      //仿函数
240.      HashFunc hf;
241. 
242.      //负载因子为1时，进行增容
243.      if (_n == _table.size())
244.      {
245.        vector<Node*> newTable;
246.        newTable.resize(GetNextPrime(_table.size()));
247. 
248.        //取旧表中的结点，重新计算映射到新表中的位置，挂到新表中
249.        for (size_t i = 0; i < _table.size(); i++)
250.        {
251.          if (_table[i])
252.          {
253.            Node* cur = _table[i];
254.            while (cur)
255.            {
256.              Node* next = cur->_next;//保存下一个结点
257.              size_t index = hf(kot(cur->_data)) % newTable.size();//计算结映射到新表中的位置
258. 
259.              //头插
260.              cur->_next = newTable[index];//=nullptr,将cur->_next置空
261.              newTable[index] = cur;//将结点插入到新表
262.              cur = next;//哈希桶往下挪一个
263.            }
264.            _table[i] = nullptr;//当前哈希桶的第一个位置置空
265.          }
266.        }
267.        _table.swap(newTable);
268.      }
269. 
270.      //不需要增容时，头插
271.      size_t index = hf(kot(data)) % _table.size();
272.      Node* newNode = new Node(data);
273. 
274.      newNode->_next = _table[index];//让新节点newNode的next指向第一个桶
275.      _table[index] = newNode;//让新节点newNode做第一个桶
276.      ++_n;//更新哈希表大小  
277. 
278.      return make_pair(iterator(newNode, this), true);
279.    }
280. 
281.    //查找
282.    iterator Find(const K& key)
283.    {
284.      //哈希表为空
285.      if (_table.size() == 0)
286.      {
287.        return end();
288.      }
289. 
290.      KeyOfT kot;
291.      HashFunc hf;
292.      size_t index = hf(key) % _table.size();//计算在哈希表中的位置
293. 
294.      //在哈希表当前位置的所有桶中找key
295.      Node* cur = _table[index];
296.      while (cur)
297.      {
298.        if (kot(cur->_data) == key)
299.        {
300.          return iterator(cur,this);
301.        }
302.        else
303.        {
304.          cur = cur->_next;
305.        }
306.      }
307. 
308.      return end();
309.    }
310. 
311.    //删除
312.    bool Erase(const K& key)
313.    {
314.      size_t index = hf(key) % _table.size();
315.      Node* prev = nullptr;
316.      Node* cur = _table[index];
317. 
318.      while (cur)
319.      {
320.        if (kot(cur->data) == key)//cur这个桶就是key
321.        {
322.          if (_table[index] == cur)//cur是第一个桶
323.          {
324.            _table[index] = cur->_next;
325.          }
326.          else//cur不是第一个桶
327.          {
328.            prev->_next = cur->_next;
329.          }
330. 
331.          --_n;//更新表大小
332.          delete cur;//删除节点
333.          return true;
334.        }
335. 
336.        prev = cur;
337.        cur = cur->_next;
338.      }
339. 
340.      return false;
341.    }
342. 
343.  private:
344.    vector<Node*> _table;
345.    size_t _n = 0;
346.  };
347. }

UnorderedSet.h

1. #pragma once
2. #include "HashTable.h"
3. 
4. namespace delia
5. {
6.  template<class K>
7.  class unordered_set
8.  {
9.    //set就取k
10.     struct SetKeyOfT
11.     {
12.       const K& operator()(const K& k)
13.       {
14.         return k;
15.       }
16.     };
17. 
18.   public:
19.     //如果不加typename，类模板里面找迭代器的类型找不到，因为OpenHash::HashTable<K, K, SetKeyOfT>::iterator没有实例化，因此编译器并不知道它是类型还是成员函数或成员变量，编译无法通过
20.     //用typename表明OpenHash::HashTable<K, K, SetKeyOfT>::iterator是一个类型，不是成员函数或成员变量，不需要等到实例化时才能确定
21.     typedef typename OpenHash::HashTable<K, K, SetKeyOfT>::iterator iterator;
22. 
23.     iterator begin()
24.     {
25.       return _ht.begin();
26.     }
27. 
28.     iterator end()
29.     {
30.       return _ht.end();
31.     }
32. 
33.     pair<iterator, bool> Insert(const K& k)
34.     {
35.       return _ht.Insert(k);
36.     }
37. 
38.   private:
39.     OpenHash::HashTable<K, K, SetKeyOfT> _ht ;
40. 
41.   };
42. 
43.   void test_unordered_set1()
44.   {
45.     unordered_set<int> us;
46.     us.Insert(100);
47.     us.Insert(5);
48.     us.Insert(6);
49.     us.Insert(32);
50.     us.Insert(8);
51.     us.Insert(14);
52.     us.Insert(65);
53.     us.Insert(27);
54.     us.Insert(39);
55. 
56.     unordered_set<int>::iterator it = us.begin();
57.     while (it != us.end())
58.     {
59.       cout << *it << " ";
60.       ++it;
61.     }
62.     cout << endl;
63.   }
64. }

UnorderedMap.h

1. #pragma once
2. #include "HashTable.h"
3. 
4. namespace delia
5. {
6.  template<class K,class V>
7.  class unordered_map
8.  {
9.    //map就取kv的first
10.     struct MapKeyOfT
11.     {
12.       const K& operator()(const pair<K,V>& kv)
13.       {
14.         return kv.first;
15.       }
16.     };
17. 
18.   public:
19.     typedef typename OpenHash::HashTable<K, pair<K,V>, MapKeyOfT>::iterator iterator;
20. 
21.     iterator begin()
22.     {
23.       return _ht.begin();
24.     }
25. 
26.     iterator end()
27.     {
28.       return _ht.end();
29.     }
30. 
31.     pair<iterator, bool> Insert(const pair<K,V>& kv)
32.     {
33.       return _ht.Insert(kv);
34.     }
35. 
36.     V& operator[](const K& key)
37.     {
38.       pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
39.       return ret.first->iterator;
40.     }
41. 
42.   private:
43.     OpenHash::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
44. 
45.   };
46. 
47.   void test_unordered_map1()
48.   {
49.     unordered_map<string,string> um;
50.     um.Insert(make_pair("spring", "春天"));
51.     um.Insert(make_pair("summer", "夏天"));
52.     um.Insert(make_pair("autumn", "秋天"));
53.     um.Insert(make_pair("winter", "冬天"));
54. 
55.     unordered_map<string,string>::iterator it = um.begin();
56.     while (it != um.end())
57.     {
58.       cout << it->first << ":" << it->second << endl;
59.       ++it;
60.     }
61.   }
62. }

Test.cpp

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include "HashTable.h"
3. #include "UnorderedSet.h"
4. #include "UnorderedMap.h"
5. 
6. int main()
7. {
8.  delia::test_unordered_set1();
9.  delia::test_unordered_map1();
10. 
11.   return 0;
12. }

运行结果：

unordered_set:

由于哈希表的初始大小为primeList中的第一个元素53，因此插入时:

100%53=47，

5%53=5，

6%53=6，

8%53=8，

65%53=12，

14%53=14，

27%53=27，

32%53=32，

39%53=39

且都没有发生冲突，因此排列顺序为5，6，8，65，14，27，32，39，100。

unordered_map:

字符串的Hash算法让每个字符*131再求和，再对53取模：

ASCII对照表如下：

97	a
98	b
99	c
100	d
101	e
102	f
103	g
104	h
105	i
106	j
107	k
108	l
109	m
110	n
111	o
112	p
113	q
114	r
115	s
116	t
117	u
118	v
119	w
120	x
121	y
122	z

spring:(((((((115*131)+112)*131)+114)*131+105)*131+110)*131+103)*131=359074819，中间发生了溢出，所以得到结果359074819，再用359074819对53取模，sunmmer，autumn和winter也都这么计算

【C++】-- STL之用哈希桶模拟实现unordered_set和unordered_map（三）

五、完整代码段

热门文章

最新文章

相关课程

相关电子书

97	a
98	b
99	c
100	d
101	e
102	f
103	g
104	h
105	i
106	j
107	k
108	l
109	m
110	n
111	o
112	p
113	q
114	r
115	s
116	t
117	u
118	v
119	w
120	x
121	y
122	z

97	a
98	b
99	c
100	d
101	e
102	f
103	g
104	h
105	i
106	j
107	k
108	l
109	m
110	n
111	o
112	p
113	q
114	r
115	s
116	t
117	u
118	v
119	w
120	x
121	y
122	z

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++】-- STL之用哈希桶模拟实现unordered_set和unordered_map（三）

五、完整代码段

热门文章

最新文章

相关课程

相关电子书

97	a
98	b
99	c
100	d
101	e
102	f
103	g
104	h
105	i
106	j
107	k
108	l
109	m
110	n
111	o
112	p
113	q
114	r
115	s
116	t
117	u
118	v
119	w
120	x
121	y
122	z