封装哈希表实现unordered_map和unordered_set

          Hello，各人好，本日的这篇博客我们来讲授一下怎样封装哈希表从而实现unordered_map和unordered_set这两个容器，众所周知，这两个容器的底层均是哈希表实现的，但是是怎么实现的呢？我们话不多说，接下来就为各人来讲授这一部门的知识。（下面的内容大概涉及到哈希表相干的知识，链接如下：数据布局——哈希表的实现_jhash实现-CSDN博客）
  目次
1 源码及框架分析
2 模拟实现unordered_map和unordered_set
  2.1 实现出复用哈希表的框架并支持Insert
  2.2 支持iterator的实现
    2.2.1 iterator的实现思绪分析
    2.2.2 代码模拟实现iterator
      2.2.2.1 迭代器的大框架实现
      2.2.2.2 迭代器部门利用实现
  2.3 unordered_map支持[ ]

---

1 源码及框架分析

          要想模拟实现出unordered_map和unordered_set这两个容器，我们就要先通过源代码来详细地相识一下，这两个容器均是C++11之后才更新的，我们这里为了方便起见，我们这里截取了部门源代码来为各人展示。（这里用哈希表封装unordered_map和unordered_set的过程和我们前面所学过的用红黑树封装map和set地实现过程根本上差不多）
  

   为了方便各人利用代码观看，我将代码放在了下面：

1. template < class Value, class HashFcn = hash<Value>, class EqualKey = equal_to<Value>, class Alloc = allocator<Value>>
2. class unordered_set
3. {
4.         private HashTable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht;
5.         ht rep;
6. };
8. template < class Key, class Value, class HashFunc = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = allocator<Key>>
9. class unordered_map
10. {
11.         private HashTable<Key, pair<Key, Value>, HashFunc, Selectlst<pair<const Key, Value>>, EqualKey, Alloc> ht;
12.         ht rep;
13. };
15. template<class Key, class Value, class HashFcn, class KeyOfT, class EqualKey, class Alloc>
16. class HashTable
17. {
18. public:
19.         typedef __hashtable_node<Value> node;
20.         vector<node*, Alloc> buckets;//暂时先不管Alloc这个模板参数，我们这里就当它不存在。
21.         size_t num_elements;
22. };
24. template<class Value>
25. struct __hashtable_node
26. {
27.         Value val;
28.         __hashtable_node* next;
29. };

复制代码

          通过我们上述对源代码的分析可知，在布局上unordered_map和unordered_set跟map和set是完全类似的，复用同一个HashTable，可以同时实现Key和Key/Value这两种布局，unordered_set传给HashTable的是两个Key，而unordered_map传给HashTable的一个是Key，另一个是pair<const Key, Value>。
         1>.这里必要注意的是源码跟map/set的源码类似，定名风格比力乱一些，这里比map和set还乱，unordered_set的模板参数居然用Value定名，unordered_map则用的是Key和Value定名，可见大佬偶尔写代码也不规范，乱奏琴。接下来，我们这里就来自己模拟实现一份unordered_map和unordered_set出来，按照我们自己的定名风格去走。
         2>.除此之外，我以为这里有须要再来表明一下unordered_map和unordered_set的后3个模板参数的寄义，HashFcn这个模板参数着实相当于是一个仿函数的范例，它的作用在这里就是将Key(关键字)转换成整数范例，由于我们的底层是通过哈希表来实现的，通过我们前面临哈希表的讲授可知，确实是必要一个如许的仿函数来找到某一个元素在哈希表中详细的映射位置；identity这个模板参数的重要作用是找到某一个元素的关键字，我们这里的unordered_map和unordered_set这两个容器它们封装的是同一个哈希表，但是这两个容器中所存储的元素是不一样的，unordered_set中存储的元素就相当于是关键字，我们就可以直接得到unordered_set的关键字，而unordered_map中存储的元素是一个pair<const Key, Value>类范例的变量，要通过解引用利用才可以得到该元素的关键字，介于这种缘故原由，这里选择利用identity这个仿函数去找到某个元素的关键字；EqualKey这个模板参数着实本质上也是一个仿函数，它的作用是判定关键字是否雷同，它重要用于查找这个步调中；Alloc就是一个内存池（背面会讲到，这里我们暂时先不管）。
  2 模拟实现unordered_map和unordered_set

  2.1 实现出复用哈希表的框架并支持Insert

          1>.我们接下来要模拟实现的unordered_map和unordered_set要参考源码框架，unordered_map和unordered_set内里封装的谁人哈希表就复用我们前一篇博客所实现的谁人哈希表就可以。
         2>.我们这里模拟实现的代码相较于源码轻微地去调解一下，Key参数就用K，Value参数就用V，哈希表中的数据范例，我们这里用T来表现。
         3>.其次跟map和set相比而言unordered_map和unordered_set在模拟实现类的团体布局时显得更加复杂一些，但是在大抵框架和思绪上是完全类似的。由于HashTable实现了泛型，导致不知道T参数到底是K，照旧pair<const Key, Value>，那么insert内部举行插入时要用K对象转换成整数取模和K比力相当，由于pair类范例的Value不加入盘算取模，且默认支持的是Key和Value一起比力相当，我们必要的是任何时间只必要比力K即可，以是我们在eunordered_map和unordered_set层分别实现一个MapKeyOfT和SetKeyOfT的仿函数传给HashTable中的KeyOfT这个参数，然后HashTable中通过KeyOfT仿函数取出T范例对象中的K（关键字），再转换成整形取模和K比力相当，代码如下所示：

1. //unordered_set
2. template < class K, class HashFcn = hash<K>, class EqualKey = equal_to<K>, class Alloc = allocator<K>>
3. class unordered_set
4. {
5.         struct SetKeyOfT
6.         {
7.                 const K& operator(const K& key)
8.                 {
9.                         return key;
10.                 }
11.         };
12. public:
13.         bool insert(const K& key)
14.     {
15.                 return _ht.Insert(key);
16.     }//...
17.         HashTable<K ,const K, SetKeyOfT, HashFcn> _ht;
18. };
19. //unordered_map
20. template < class K, class V, class HashFcn = hash<K>, class EqualKey = equal_to<K>, class Alloc = allocator<K>>
21. class unordered_map
22. {
23.         struct MapKeyOfT
24.         {
25.                 const K& operator()(const pair<const K, V>& kv)
26.                 {
27.                         return kv.first;
28.                 }
29.         };
30. public:
31.         bool insert(const pair<const K, V>& kv)
32.         {
33.                 return _ht.Insert(kv);
34.         }//...
35.         HashTable<K, pair<const K, V>, MapKeyOfT, HashFcn> rep;
36. };
37. //我们上面模拟实现部分中给HashFcn这个模板参数一个hash<K>这个缺省值，因为我们这里的unordered_map和unordered_set这两个容器中的K有可能本身就为整数类型，是不需要我们在这里进行转换的，也就是说，如果K为int类型的话，是不用给HashFcn传参的，但是为了让其那个兼容Key的所有可能类型，所以这里给HashFcn这个模板参数一个缺省值，这个缺省值就是专门针对Key为整数类型或者是可以直接转换成整数类型的变量用的，代码如下：
38. template<class K>
39. struct HashFnc
40. {
41.         size_t operator()(const K& key)
42.         {
43.                 return (size_t)key;
44.         }
45. };
46. //我们前一篇博客在实现哈希表时是默认哈希表中存放的是pair<const K, V>类类型的变量，因此，哈希表的角度也需换一下。
47. template<class T>
48. struct HashData
49. {
50.         T _data;
51.         HashDataT<T>* _next;
52.         HashData(const T& data)
53.                 :_data(data)
54.                 ,_next(nullptr)
55.         { }
56. };
57. //剩下的就差不多了，还要将前一篇博客中所有的元素全部换一下，换成data，以兼容unordered_map和unordered_set。

复制代码

  2.2 支持iterator的实现

    2.2.1 iterator的实现思绪分析

          1>.iterator实现的大框架跟list中的iterator的思绪是划一的，用一个范例封装一个节点的指针，再通过重载运算符实现，迭代器像指针一样访问的举动，要注意的是哈希表的迭代器是单向迭代器。
         2>.这里的难点是对operator++这个运算符的实现。iterator中有一个指向节点的指针，如果当前桶下面另有节点的话，则节点的指针指向下一个节点即可。如果当前这个桶我们走完了，则必要想办法盘算找到下一个桶，这里的难点是布局筹划的标题，在源码的实现中，我们可以看到iterator中除了有一个节点的指针以外，另有一个哈希表对象范例的指针，如许当桶走完了，要盘算下一个桶就相对容易得多了，用Key值盘算出当前这个桶得位置，依次今后去找下一个不为空的桶即可。
         3>.begin()返回的是第一个桶中得第一个节点指针所构造的迭代器，这里的end()返回的迭代器可以用空指针去表现。
         4>.unordered_set的iterator也不支持修改，我们把unordered_set的第二个参数用const修饰一下即可。

1. HashTable<K ,const K, SetKeyOfT, HashFcn> _ht;

复制代码

         5>.unordered_map的iterator不支持修改K，但是可以修改V，我们把unordered_map的第二个模板参数pair的第一个参数用const修饰即可。

1. HashTable<K, pair<const K, V>, MapKeyOfT, HashFcn> _ht;

复制代码

    2.2.2 代码模拟实现iterator

          我们这里的代码模拟实现分为两部门来写，一部门是迭代器的大框架，另一部门则写迭代器中的一些须要条件。
        2.2.2.1 迭代器的大框架实现

1. template<class K, class V, class Hash = HashFnc<K>, class KeyOfT, class Pred = equal_to<K>, class Alloc = allocator<K>>
2. class HashTable;//这一步操作是对HashTable这个类进行一个前置声明的操作，这里我们之所以要加上这一句代码主要还是因为我们哈希表的结构造成的，通过我们上述的讲解可以得知，哈希表的迭代器中不仅封装了一个节点类型的指针，还封装了一个哈希表类型的指针(至于这里为什么还要再封装一个哈希表类型的指针，原因我们在后面的讲解中会讲到，这里先知道有这个指针的存在就可以了)，根据我们编译器的运行路径(从上往下，我们这里默认是先写Iterator这个类，然后再写HashTable这个类)来看，当编译器运行到Iterator这个类中的定义哈希表类型的这句代码时，编译器它不认识哈希表的那个类型，就会往前去找，但是我们的HashTable这个类是在Iterator这个类的下面定义的，往上找就根本找不到，因此，编译器在这里就会报错，为了解决这个问题，我们要在Iterator这个类的前面对HashTable这个类做一个前置声明即可解决问题。
3. template<class K,class T,class Ptr,class Ref,class KeyOfT,class Hash>
4. struct Iterator
5. {
6.         typedef HashNode<T> Node;
7.         typedef Iterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;
8.         typedef HashTable<K, T, KeyOfT, Hash > HT;
9.         Node* _node;
10.         const HT* _ht;
11.         Iterator(Node* node,HT* ht)
12.                 :_node(node)
13.                 ,_ht(ht)
14.         { }
15.         //...
16. };
18. template<class K, class T, class Hash = HashFnc<K>, class KeyOfT, class Pred = equal_to<K>, class Alloc = allocator<K>>
19. class HashTable
20. {
21.         template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
22.         friend struct Iterator;//这里的这两句代码是对Iterator类进行友元声明操作，这里之所以要对Iterator进行友元操作，其本质原因还是哈希表的结构问题，我们在实现operator++这个重载运算符时，如果当前节点的下一个节点为空的话，那么我们++后下一个访问的节点是哈希表的下一个桶的第一个节点，也就是说，如果遇到这种情况时，我们就需要借助哈希表的对象去求出当前节点在哈希表中的映射位置，从这个映射位置开始，继续往后去找下一个桶，我们这里既然要求出当前节点的映射位置，首先就得找到当前所在的这个哈希表，而前面我们在Iterator中定义的那个哈希表类型的指针恰好就可以帮助我们找到，这就是Iterator类中需要定义哈希表类型的指针的原因，找到当前节点所在的哈希表，我们要的是哈希表的大小，也就是HashTable类中的那个顺序表_tables的大小，但是_tables在HashTable中属于是私有成员，外界不可访问(Iterator和HashTable属于两个不同的类)，为了解决这个问题，有两个方法，一种是将HashTable中的那个顺序表传到Iterator类中，二种是让Iterator成为HashTable的友元类，这样在Iterator中也可以访问HashTable中的私有成员了。我们这里选择第二种，自我感觉第二种比第一种更方便，模板的友元声明如上述代码所示(我们之前没遇到，这里强调一下)。
23.         typedef HashNode<T> Node;
24. public:
25.         typedef Iterator<K, T, T*, T&, KeyOfT, Hash> HTIterator;
26.         typedef Iterator<K, T, const T*, const T&, KeyOfT, Hash> ConstHTIterator;
27.         //...
28. private:
29.         vector<Node*> _tables;
30.         size_t _n = 0;
31. };
33. template < class K, class HashFcn = hash<K>, class EqualKey = equal_to<K>, class Alloc = allocator<K>>
34. class unordered_set
35. {
36.         struct SetKeyOfT
37.         {
38.                 const K& operator(const K& key)
39.                 {
40.                         return key;
41.                 }
42.         };
43.         HashTable<K, const K, HashFcn, SetKeyOfT, EqualKey, Alloc> _ht;
44. public:
45.         typedef typename HashTable<K, const K, HashFcn, SetKeyOfT, EqualKey, Alloc>::HTIterator iterator;
46.         typedef typename HashTable<K, const K, HashFcn, SetKeyOfT, EqualKey, Alloc>::ConstHTIterator const_iterator;
47.         //...
48. };
50. template < class K, class V, class HashFcn = hash<K>, class EqualKey = equal_to<K>, class Alloc = allocator<K>>
51. class unordered_map
52. {
53.         struct MapKeyOfT
54.         {
55.                 const K& operator()(const pair<const K, V>& kv)
56.                 {
57.                         return kv.first;
58.                 }
59.         };
60.         HashTable<K, pair<const K, V>, HashFcn, SetKeyOfT, EqualKey, Alloc> _ht;
61. public:
62.         typedef typename HashTable<K, pair<const K, V>, HashFcn, SetKeyOfT, EqualKey, Alloc>::HTIterator iterator;
63.         typedef typename HashTable<K, pair<const K, V>, HashFcn, SetKeyOfT, EqualKey, Alloc>::ConstHTIterator const_iterator;
64.         //...
65. };

复制代码

      2.2.2.2 迭代器部门利用实现

          迭代器中最重要的成员函数着实就是重载operator++利用符，以及解引用利用，因此我们这里只实现重载++运算符和重载解引用利用符这两个利用就可以了。

1. Ref operator*()
2. {
3.         return _node->_data;
4. }
5. Self operator++()
6. {
7.         if (_node->_next)//如果当前节点的下一个节点不为空的话，就说明当前这个桶还没有遍历完，返回下一个节点的迭代器即可。
8.         {
9.                 _node = _node->_next;
10.         }
11.         else//当前节点的下一个节点是空节点，那么说明当前这个桶全部都遍历完了，下一个访问的节点在另一个桶上，应该先找到当前这个节点在哈希表中映射的位置，从映射的这个位置开始往后去找下一个桶。
12.         {
13.                 KeyOfT kot;//找到_data中的关键字。
14.                 Hash hash;//将关键字转换成整数类型。
15.                 size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();//求出当前节点在哈希表中映射的位置。
16.                 ++hahsi;//我们在求出当前这个节点在哈希表中映射的那个位置后，让其++一下，如果当前节点的下一个位置为空，就说明当前这个节点所在的这个桶已经走完了，hashi在未++前，它代表的是当前这个节点所在的这个桶所在哈希表中映射的位置，也就是说，下一个要访问的节点是在当前这个桶的下一个桶中，hashi++之后，hashi表示的是当前这个桶在哈希表中映射的位置的下一个位置。
17.                 while (hashi < _ht->_tables.size())//接下来的操作就是通过循环从哈希表中下标未hashi这个位置开始往后去找下一个桶。
18.                 {
19.                         _node = _ht->_data->_tables[hashi];
20.                         if (_ht->_tables[hashi])//如果_node不为空，则说明中的下一个桶了。
21.                         {
22.                                 break;//结束循环。
23.                         }
24.                         else//说明哈希表中下标为hashi的位置没有桶，继续往下一个位置去找。
25.                         {
26.                                 hashi++:
27.                         }
28.                 }//若出了while循环的话，则有2种情况：一种是找到了下一个桶，break出来了，另一个是走到哈希表的末尾(也就是hashi==_tables.size())了，因此我们这里还需要判断一下。
29.                 if (hashi == _ht->_tables.size())//说明是走到哈希表的末尾了。
30.                 {
31.                         _node = nullptr;
32.                 }//这个if语句其实在这里可有可无，因为前面有"_node = _ht->_data->_tables[hashi];"这一行代码，无论是以哪种情况出现出while循环，_node它指向的都是我们想要的那个结果。
33.         }
34.         return *this;
35. }

复制代码

  2.3 unordered_map支持[ ]

          1>.unordered_map要支持[ ]重要必要修改insert返回值支持，修改HashTable中的insert返回值为pair<HTIterator,bool> Insert(const T& data)。
         2>.有了insert支持，[ ]的头脑就很简单了。
           OK，本日我们就先讲到这里了，那么，我们下一篇再见，谢谢各人的支持！