• <unordered_set、unordered_map的模拟实现>——《C++高阶》


    目录

     1.unordered_set、unordered_map的结构分析:

    1.1 哈希表的改造

    1.2 unordered_map模型分析:

    2.unordered_set、unordered_map模拟实现:

    2.1 unordered_set模拟实现:

    2.2 unordered_map模拟实现:

    2.3 附用的模拟实现的开散列哈希表

    后记:●由于作者水平有限,文章难免存在谬误之处,敬请读者斧正,俚语成篇,恳望指教!

                                                                               ——By 作者:新晓·故知


     1.unordered_set、unordered_map的结构分析:

    1.1 哈希表的改造

    1. 模板参数列表的改造
    1. // K:关键码类型
    2. // V: 不同容器V的类型不同,如果是unordered_map,V代表一个键值对,如果是
    3. unordered_set,V 为 K
    4. // KeyOfValue: 因为V的类型不同,通过value取key的方式就不同,详细见
    5. unordered_map/set的实现
    6. // HF: 哈希函数仿函数对象类型,哈希函数使用除留余数法,需要将Key转换为整形数字才能
    7. 取模
    8. template<class K, class V, class KeyOfValue, class HF = DefHashF >
    9. class HashBucket;
    2. 增加迭代器操作
    1. // 为了实现简单,在哈希桶的迭代器类中需要用到hashBucket本身,
    2. template<class K, class V, class KeyOfValue, class HF>
    3. class HashBucket;
    4. // 注意:因为哈希桶在底层是单链表结构,所以哈希桶的迭代器不需要--操作
    5. template <class K, class V, class KeyOfValue, class HF>
    6. struct HBIterator
    7. {
    8. typedef HashBucket HashBucket;
    9. typedef HashBucketNode* PNode;
    10. typedef HBIterator Self;
    11. HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr);
    12. Self& operator++()
    13. {
    14.         // 当前迭代器所指节点后还有节点时直接取其下一个节点
    15. if (_pNode->_pNext)
    16. _pNode = _pNode->_pNext;
    17. else
    18. {
    19. // 找下一个不空的桶,返回该桶中第一个节点
    20. size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode- >_data))+1;
    21. for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
    22. {
    23. if (_pNode = _pHt->_ht[bucketNo])
    24. break;
    25. }
    26. }return *this;
    27. }
    28. Self operator++(int);
    29.    V& operator*();
    30. V* operator->();
    31. bool operator==(const Self& it) const;
    32. bool operator!=(const Self& it) const;
    33. PNode _pNode;             // 当前迭代器关联的节点
    34. HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
    35. };
    3. 增加通过key获取value操作
    1. template<class K, class V, class KeyOfValue, class HF = DefHashF >
    2. class HashBucket
    3. {
    4. friend HBIterator;
    5.    // ......
    6. public:
    7. typedef HBIterator Iterator;
    8. //
    9.    // ...
    10. // 迭代器
    11. Iterator Begin()
    12. {
    13. size_t bucketNo = 0;
    14. for (; bucketNo < _ht.capacity(); ++bucketNo)
    15. {
    16. if (_ht[bucketNo])
    17. break;
    18. }
    19. if (bucketNo < _ht.capacity())
    20. return Iterator(_ht[bucketNo], this);
    21. else
    22. return Iterator(nullptr, this);
    23. }
    24. Iterator End(){ return Iterator(nullptr, this);}
    25.    Iterator Find(const K& key);
    26. Iterator Insert(const V& data);
    27. Iterator Erase(const K& key);
    28.    
    29.    // 为key的元素在桶中的个数
    30. size_t Count(const K& key)
    31. {
    32. if(Find(key) != End())
    33.            return 1;
    34.        
    35.        return 0;
    36. }
    37.    
    38.    size_t BucketCount()const{ return _ht.capacity();}
    39.    size_t BucketSize(size_t bucketNo)
    40.   {
    41.        size_t count = 0;
    42.    PNode pCur = _ht[bucketNo];
    43.        while(pCur)
    44.       {
    45.            count++;
    46.            pCur = pCur->_pNext;
    47.       }
    48.        
    49.        return count;
    50.   }
    51.    
    52.    // ......
    53. };

    1.2 unordered_map模型分析:

    1. // unordered_map中存储的是pair的键值对,K为key的类型,V为value的类型,HF哈希
    2. 函数类型
    3. // unordered_map在实现时,只需将hashbucket中的接口重新封装即可
    4. template<class K, class V, class HF = DefHashF>
    5. class unordered_map
    6. {
    7. typedef pair ValueType;
    8. typedef HashBucket HT;
    9. // 通过key获取value的操作
    10. struct KeyOfValue
    11. {
    12. const K& operator()(const ValueType& data)
    13. { return data.first;}
    14. };
    15. public:
    16. typename typedef HT::Iterator iterator;
    17. public:
    18. unordered_map(): _ht()
    19. {}
    20. iterator begin(){ return _ht.Begin();}
    21. iterator end(){ return _ht.End();}
    22. // capacity
    23. size_t size()const{ return _ht.Size();}
    24. bool empty()const{return _ht.Empty();}
    25. ///
    26. // Acess
    27. V& operator[](const K& key)
    28. {
    29. return (*(_ht.InsertUnique(ValueType(key, V())).first)).second;
    30. }
    31. const V& operator[](const K& key)const;
    32. //
    33. // lookup
    34. iterator find(const K& key){ return _ht.Find(key);}
    35. size_t count(const K& key){ return _ht.Count(key);}
    36. /
    37. // modify
    38. pairbool> insert(const ValueType& valye)
    39. { return _ht.Insert(valye);}
    40. iterator erase(iterator position)
    41. { return _ht.Erase(position);}
    42. // bucket
    43. size_t bucket_count(){ return _ht.BucketCount();}
    44. size_t bucket_size(const K& key){ return _ht.BucketSize(key);}
    45. private:
    46. HT _ht;
    47. };

    2.unordered_set、unordered_map模拟实现:

    2.1 unordered_set模拟实现:

    1. #include"OpenHT.h"
    2. namespace my
    3. {
    4. template<class K, class HashFunc = DefaultHash>
    5. class unordered_set
    6. {
    7. //内部类
    8. struct SetKeyOfT
    9. {
    10. const K& operator()(const K& key)
    11. {
    12. return key;
    13. }
    14. };
    15. public:
    16. typedef typename Bucket::HashTable::iterator iterator;
    17. iterator begin()
    18. {
    19. return _ht.begin();
    20. }
    21. iterator end()
    22. {
    23. return _ht.end();
    24. }
    25. //bool insert(const K& key)
    26. pairbool> insert(const K& key)
    27. {
    28. return _ht.Insert(key);
    29. }
    30. iterator find(const K& key)
    31. {
    32. return _ht.Find(key);
    33. }
    34. bool erase(const K& key)
    35. {
    36. return _ht.Erase(key);
    37. }
    38. private:
    39. Bucket::HashTable _ht;
    40. };
    41. }

     2.2 unordered_map模拟实现:

     

    1. #include"OpenHT.h"
    2. namespace my
    3. {
    4. template<class K, class V, class HashFunc = DefaultHash>
    5. class unordered_map
    6. {
    7. //内部类
    8. struct MapKeyOfT
    9. {
    10. const K& operator()(const pair& kv)
    11. {
    12. return kv.first;
    13. }
    14. };
    15. public:
    16. //定义map的迭代器
    17. typedef typename Bucket::HashTable, MapKeyOfT, HashFunc> ::iterator iterator;
    18. iterator begin()
    19. {
    20. return _ht.begin();
    21. }
    22. iterator end()
    23. {
    24. return _ht.end();
    25. }
    26. //bool insert(const pair& kv)
    27. pairbool> insert(const pair& kv)
    28. {
    29. return _ht.Insert(kv);
    30. }
    31. iterator find(const K& key)
    32. {
    33. return _ht.Find(key);
    34. }
    35. bool erase(const K& key)
    36. {
    37. return _ht.Erase(key);
    38. }
    39. V& operator[](const K& key)
    40. {
    41. //pair ret = insert(make_pair(key, V()));
    42. auto ret = insert(make_pair(key, V()));
    43. return ret.first->second; //first是迭代器,而map里面访问second要用->,其实这里有两个->,但为了可读性
    44. }
    45. private:
    46. Bucket::HashTable, MapKeyOfT,HashFunc> _ht;
    47. };
    48. }

    2.3 附用的模拟实现的开散列哈希表

    OpenHT.h:

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. using namespace std;
    10. //仿函数
    11. template<class K>
    12. struct DefaultHash //1.普通类直接强转
    13. {
    14. size_t operator()(const K& key)
    15. {
    16. return(size_t)key; //支持取模,强转为整数
    17. }
    18. };
    19. template<>
    20. struct DefaultHash //String类特化
    21. {
    22. size_t operator()(const string& key)
    23. {
    24. //4.BKDR法
    25. size_t hash = 0;
    26. for (auto ch : key)
    27. {
    28. hash = hash * 131 + ch;
    29. }
    30. return hash;
    31. }
    32. };
    33. namespace Bucket
    34. {
    35. template<class T>
    36. struct HashNode
    37. {
    38. T _data;
    39. HashNode* _next;
    40. HashNode(const T& data)
    41. :_data(data)
    42. , _next(nullptr)
    43. {}
    44. };
    45. template<class K, class T, class KeyOfT, class HashFunc>
    46. class HashTable;
    47. template<class K, class T, class KeyOfT, class HashFunc>
    48. class __HTIterator //单向迭代器
    49. {
    50. typedef HashNode Node;
    51. typedef __HTIterator Self;
    52. public:
    53. Node* _node;
    54. HashTable* _pht;
    55. __HTIterator(){} //默认哈希迭代器构造函数
    56. __HTIterator(Node* node, HashTable* pht)
    57. :_node(node)
    58. ,_pht(pht)
    59. {}
    60. Self& operator++()
    61. {
    62. if (_node->_next)
    63. {
    64. _node = _node->_next;
    65. }
    66. else
    67. {
    68. KeyOfT kot;
    69. HashFunc hf;
    70. size_t hashi = hf(kot(_node->_data))%_pht->_tables.size();
    71. ++hashi;
    72. //找下一个不为空的桶
    73. for (; hashi < _pht->_tables.size(); ++hashi)
    74. {
    75. if (_pht->_tables[hashi])
    76. {
    77. _node = _pht->_tables[hashi];
    78. break;
    79. }
    80. }
    81. // 没有找到不为空的桶,用nullptr去做end标识
    82. if (hashi == _pht->_tables.size())
    83. {
    84. _node = nullptr;
    85. }
    86. }
    87. return *this;
    88. }
    89. T& operator*()
    90. {
    91. return _node->_data;
    92. }
    93. T* operator->()
    94. {
    95. return &_node->_data;
    96. }
    97. bool operator!=(const Self& s) const
    98. {
    99. return _node != s._node;
    100. }
    101. bool operator==(const Self& s) const
    102. {
    103. return _node == s._node;
    104. }
    105. };
    106. //unordered_set--->HashTable _ht;
    107. //unordered_map--->HashTable, MapKeyOfT> _ht;
    108. template<class K, class T, class KeyOfT, class HashFunc>
    109. class HashTable
    110. {
    111. template<class K, class T, class KeyOfT, class HashFunc>
    112. friend class __HTIterator;
    113. typedef HashNode Node;
    114. public:
    115. typedef __HTIterator iterator;
    116. iterator begin()
    117. {
    118. for (size_t i = 0; i < _tables.size(); ++i)
    119. {
    120. Node* cur = _tables[i];
    121. if (cur)
    122. {
    123. return iterator(cur, this);
    124. }
    125. }
    126. return end();
    127. }
    128. iterator end()
    129. {
    130. return iterator(nullptr, this);
    131. }
    132. //手动实现Node的析构函数
    133. ~HashTable()
    134. {
    135. for (size_t i = 0; i < _tables.size(); ++i)
    136. {
    137. Node* cur = _tables[i];
    138. while (cur)
    139. {
    140. Node* next = cur->_next;
    141. delete cur;
    142. cur = next;
    143. }
    144. _tables[i] = nullptr;
    145. }
    146. }
    147. ///
    148. HashTable() = default; //强制生成默认构造函数
    149. 链表桶的深拷贝
    150. //HashTable(const HashTable ht)
    151. //{
    152. // int sz = ht._tables.size();
    153. // for (int i = 0; i < sz; i++)
    154. // {
    155. // Node* cur = ht._tables[i];
    156. // while (cur)
    157. // {
    158. // this->Insert(cur->_kv);
    159. // cur = cur->_next;
    160. // }
    161. // }
    162. // _n = ht._n;
    163. //}
    164. 链表桶的赋值重载
    165. //HashTable& operator=(HashTable ht)
    166. //{
    167. // //现代写法
    168. // ht._tablle.swap(_tables);
    169. // _n = ht._n;
    170. //}
    171. ///
    172. size_t GetNextPrime(size_t prime)
    173. {
    174. const int PRIMECOUNT = 28;
    175. static const size_t primeList[PRIMECOUNT] =
    176. {
    177. 53ul, 97ul, 193ul, 389ul, 769ul,
    178. 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    179. 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    180. 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    181. 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    182. 1610612741ul, 3221225473ul, 4294967291ul
    183. };
    184. // 获取比prime大那一个素数
    185. size_t i = 0;
    186. for (; i < PRIMECOUNT; ++i)
    187. {
    188. if (primeList[i] > prime)
    189. return primeList[i];
    190. }
    191. return primeList[i];
    192. }
    193. //bool Insert(const T& data)
    194. pairbool> Insert(const T& data)
    195. {
    196. HashFunc hf;
    197. KeyOfT kot;
    198. //if (Find(kot(data))) //使用仿函数,不知道data是set还是map
    199. //if (Find(kot(data))!=end()) //使用仿函数,不知道data是set还是map
    200. iterator pos = Find(kot(data));
    201. if(pos!=end())
    202. {
    203. //return false;
    204. return make_pair(pos,false);
    205. }
    206. //负载因子(这里设置为1) 扩容
    207. if (_tables.size() == _n)
    208. {
    209. //写法2:扩容
    210. //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    211. //写法3:
    212. size_t newSize = GetNextPrime(_tables.size());
    213. if (newSize != _tables.size())
    214. {
    215. vector newTable;
    216. newTable.resize(newSize, nullptr);
    217. for (size_t i = 0; i < _tables.size(); ++i)
    218. {
    219. Node* cur = _tables[i];
    220. while (cur)
    221. {
    222. size_t hashi = hf(kot(cur->_data)) % newSize; //hf转换为整型,kot()取k
    223. cur->_next = newTable[hashi];
    224. newTable[hashi] = cur;
    225. cur = cur->_next;
    226. }
    227. _tables[i] = nullptr;
    228. }
    229. newTable.swap(_tables);
    230. }
    231. }
    232. size_t hashi = hf(kot(data)); //两层仿函数调用
    233. hashi %= _tables.size();
    234. //头插到对应的桶即可
    235. Node* newnode = new Node(data);
    236. newnode->_next = _tables[hashi];
    237. _tables[hashi] = newnode;
    238. ++_n;
    239. //return true;
    240. return make_pair(iterator(newnode,this),false);
    241. }
    242. //Node* Find(const K& key)
    243. iterator Find(const K& key)
    244. {
    245. if (_tables.size() == 0)
    246. {
    247. //return nullptr;
    248. return iterator(nullptr,this);
    249. }
    250. KeyOfT kot;
    251. //写法1:有名对象
    252. HashFunc hf;
    253. size_t hashi = hf(key);
    254. //写法2:匿名对象
    255. //size_t hashi = HashFunc()(key);
    256. hashi %= _tables.size();
    257. Node* cur = _tables[hashi];
    258. while (cur)
    259. {
    260. if (kot(cur->_data) == key)
    261. {
    262. //return cur;
    263. return iterator(cur, this);
    264. }
    265. cur = cur->_next;
    266. }
    267. //return nullptr; //效率高,是因为直接返回了指针
    268. return iterator(nullptr, this);
    269. }
    270. bool Erase(const K& key)
    271. {
    272. if (_tables.size() == 0)
    273. {
    274. return false;
    275. }
    276. KeyOfT kot;
    277. //写法1:有名对象
    278. HashFunc hf;
    279. size_t hashi = hf(key);
    280. hashi %= _tables.size();
    281. Node* cur = _tables[hashi];
    282. Node* prev = nullptr;
    283. while (cur)
    284. {
    285. if (kot(cur->_data) == key)
    286. {
    287. if (prev == nullptr)
    288. {
    289. _tables[hashi] = cur->_next;
    290. }
    291. else
    292. {
    293. prev->_next = cur->_next;
    294. }
    295. delete cur;
    296. return true;
    297. }
    298. cur = cur->_next;
    299. }
    300. return false;
    301. }
    302. private:
    303. //指针数组
    304. //没有使用list,是因为list是双向链表,成本大 vector> _tables; 但不用手动写析构函数
    305. vector _tables;
    306. //开散列采用挂起,如果新表扩容,那么当旧表释放,vector会将自己的释放,
    307. //但是挂在vector的结点Node* 不会自动释放,因为Node* 是内置类型,需要手动释放。
    308. size_t _n = 0;
    309. };
    310. }

    Test.cpp: 

    1. #include"OpenHT.h"
    2. #include"UnorderedSet.h"
    3. #include"UnorderedMap.h"
    4. //
    5. //1.库中的UnorderedSet、UnorderedMap测试
    6. void test_std_UnorderedSet()
    7. {
    8. std::unordered_set<int> s;
    9. s.insert(9);
    10. s.insert(7);
    11. s.insert(2);
    12. s.insert(1);
    13. s.insert(6);
    14. s.insert(5);
    15. //1.迭代器遍历
    16. //unordered_set::iterator it = s.begin();
    17. //auto it = s.begin();
    18. //写法2:
    19. std::unordered_set<int>::iterator it;
    20. it = s.begin();
    21. while (it != s.end())
    22. {
    23. cout << *it << " ";
    24. ++it;
    25. }
    26. cout << endl;
    27. //2.范围for遍历
    28. for (auto e : s)
    29. {
    30. cout << e << " ";
    31. }
    32. cout << endl;
    33. }
    34. void test_std_UnorderedMap()
    35. {
    36. std::unordered_map dict;
    37. dict.insert(make_pair("sort", "排序"));
    38. dict.insert(make_pair("left", "左边"));
    39. dict.insert(make_pair("left", "剩余"));
    40. dict["string"];
    41. dict["left"] = "剩余";
    42. dict["string"] = "字符串";
    43. //迭代器遍历
    44. //std::unordered_map::iterator it = dict.begin();
    45. auto it = dict.begin();
    46. while (it != dict.end())
    47. {
    48. cout << it->first << " " << it->second << endl;
    49. ++it;
    50. }
    51. cout << endl;
    52. //范围for遍历
    53. for (auto& kv : dict)
    54. {
    55. cout << kv.first << " " << kv.second << endl;
    56. }
    57. }
    58. //
    59. //2.模拟实现UnorderedSet、UnorderedMap测试
    60. void test_my_UnorderedSet()
    61. {
    62. my::unordered_set<int> s;
    63. s.insert(9);
    64. s.insert(7);
    65. s.insert(2);
    66. s.insert(1);
    67. s.insert(6);
    68. s.insert(5);
    69. //1.迭代器遍历
    70. //my::unordered_set::iterator it = s.begin();
    71. //auto it = s.begin();
    72. //写法2:
    73. my::unordered_set<int>::iterator it;
    74. it = s.begin();
    75. while (it != s.end())
    76. {
    77. cout << *it << " ";
    78. ++it;
    79. }
    80. cout << endl;
    81. //2.范围for遍历
    82. for (auto e : s)
    83. {
    84. cout << e << " ";
    85. }
    86. cout << endl;
    87. }
    88. void test_my_UnorderedMap()
    89. {
    90. my::unordered_map dict;
    91. dict.insert(make_pair("sort", "排序"));
    92. dict.insert(make_pair("left", "左边"));
    93. dict.insert(make_pair("left", "剩余"));
    94. dict["string"];
    95. dict["left"] = "剩余";
    96. dict["string"] = "字符串";
    97. //迭代器遍历
    98. //my::unordered_map::iterator it = dict.begin();
    99. auto it = dict.begin();
    100. while (it != dict.end())
    101. {
    102. cout << it->first << " " << it->second << endl;
    103. ++it;
    104. }
    105. cout << endl;
    106. //范围for遍历
    107. for (auto& kv : dict)
    108. {
    109. cout << kv.first << " " << kv.second << endl;
    110. }
    111. }
    112. int main()
    113. {
    114. //test_std_UnorderedSet();
    115. //test_std_UnorderedMap();
    116. //test_my_UnorderedSet();
    117. test_my_UnorderedMap();
    118. return 0;
    119. }

     

    测试示例:

     

     

     

     

    后记:
    ●由于作者水平有限,文章难免存在谬误之处,敬请读者斧正,俚语成篇,恳望指教!

                                                                               ——By 作者:新晓·故知

     

  • 相关阅读:
    CentOS 7.3 Linux系统安装过程介绍
    MarkText快捷键(随时补充中)
    PromQL 查询监控数据
    行为型:发布订阅模式
    RHCSA 05 - 管理Selinux
    Science子刊 | 将CAR-T细胞疗法与造血干细胞移植相结合 或许 能治疗所有血液癌症...
    【 OpenGauss源码学习 —— (hash_search)】
    solidworks导入stl保持为曲面且可编译的注意项
    Java基础教程详解:多线程(1)-----多线程概念
    nprogress进度条的安装与使用
  • 原文地址:https://blog.csdn.net/m0_57859086/article/details/126861898