当前位置：首页 > article >正文

C++ 哈希表封装unordered_map 和 unordered_set

article 2024/12/23 19:14:52

1.源码框架

SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL 版本，这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表，只容器的名字是hash_map 和hash_set，他是作为⾮标准的容器出现的，⾮标准是指⾮C++标准规定必须实现的，源代码在 hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中

hash_map和hash_set的实现结构框架核⼼部分截取出来如下：

• 这⾥我们就不再画图分析了，通过源码可以看到，结构上hash_map和hash_set跟map和set的完全类似，复⽤同⼀个hashtable实现key和key/value结构，hash_set传给hash_table的是两个 key，hash_map传给hash_table的是pair<const key,value>

• 需要注意的是源码⾥⾯跟map/set源码类似，命名⻛格⽐较乱，这⾥⽐map和set还乱，hash_set 模板参数居然⽤的Value命名，hash_map⽤的是Key和T命名，可⻅⼤佬有时写代码也不规范，乱弹琴。下⾯我们模拟⼀份⾃⼰的出来，就按⾃⼰的⻛格⾛了

2.模拟实现unorde red_map和unordered_set

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

• 参考源码框架，unordered_map和unordered_set复⽤之前我们实现的哈希表。

• 我们这⾥相⽐源码调整⼀下，key参数就⽤K，value参数就⽤V，哈希表中的数据类型，我们使⽤ T。

• 其次跟map和set相⽐⽽⾔unordered_map和unordered_set的模拟实现类结构更复杂⼀点，但是⼤框架和思路是完全类似的。

因为HashTable实现了泛型不知道T参数导致是K，还是pair，那么insert内部进⾏插⼊时要⽤K对象转换成整形取模和K⽐较相等，因为pair的value不参与计算取模，且默认⽀持的是key和value⼀起⽐较相等，我们需要时的任何时候只需要⽐较K对象，所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给 HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K⽐较相等，具体细节参考如下代码实现。

2.2支持iterator的实现

iterator核⼼源代码

iterator实现思路分析

• iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算符实现，迭代器像指针⼀样访问的⾏为，要注意的是哈希表的迭代器是单向迭代器。

• 这⾥的难点是operator++的实现。iterator中有⼀个指向结点的指针，如果当前桶下⾯还有结点，则结点的指针指向下⼀个结点即可。如果当前桶⾛完了，则需要想办法计算找到下⼀个桶。这⾥的难点是反⽽是结构设计的问题，参考上⾯的源码，我们可以看到iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶⾛完了，要计算下⼀个桶就相对容易多了，⽤key值计算出当前桶位置，依次往后找下⼀个不为空的桶即可。

• begin()返回第⼀个桶中第⼀个节点指针构造的迭代器，这⾥end()返回迭代器可以⽤空表⽰。

• unordered_set的iterator也不⽀持修改，我们把unordered_set的第⼆个模板参数改成const K即可， HashTableconst K, SetKeyOfT, Hash> _ht;

• unordered_map的iterator不⽀持修改key但是可以修改value，我们把unordered_map的第⼆个模板参数pair的第⼀个参数改成const K即可， HashTablepair, MapKeyOfT, Hash> _ht;

• ⽀持完整的迭代器还有很多细节需要修改，具体参考下⾯题的代码。