- 1如何让知识图谱辅助多轮对话_知识图谱问答多轮对话实体的替换
- 2EHS管理系统避坑指南！这几个关键点需要注意！_ehs系统
- 3Tomcat服务安全加固和优化_tomcat加固使用安全的http请求(3)_linxu系统中tomcat安全加固日志开启
- 4困惑度：一种新的优化方法_困惑度的大小
- 5Stable Diffusion教程：4000字说清楚图生图_stable diffusion拉伸、裁剪、填充
- 6VSCode远程调试Linux程序
- 7刷题LeetCode第三天_leetcode listnode空指针问题
- 8对象加载JVM到GC清除的全过程分析
- 9【数学建模】——【A题 信用风险识别问题】全面解析
- 10Spring事务
【C++】哈希表封装实现 unordered_map 和 unordered_set_c实现封装通用hash表
赞
踩
一、unordered 系列关联式容器
在 C++98 中，STL 提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 O(logN)，即最差情况下只需要比较红黑树的高度次；但是当树中的节点非常多时，其查询效率也不够极致。
最好的查询是，不进行比较或只进行常数次比较就能够将元素找到，因此在 C++11 中，STL 又提供了 4 个 unordered 系列的关联式容器 – unordered_map、unordered_set、unordered_multimap 和 unordered_multiset，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层使用开散列的哈希表来实现。
拓展：有的同学可能会疑惑为什么底层为哈希表的 unordered 系列容器为什么要取名为 unordered_map 和 unordered_set，而不是取名为更加形象的 hashmap 和 hashset？这其实是C++的发展历史导致的。
由于 map 和 set 是 C++98 增加的容器，而 unordered_map 和 unordered_set 则是 C++11 增加的容器，在 C++11 时，人们对 map 和 set 的固有印象已经很深了 – 有序、去重、搜索，但是 unordered_map 和 unordered_set 是无序的，所以为了更好的与 map 和 set 进行区分，C++11 将它们取名为 unordered_map 和 unordered_set，其中 unordered 就是无序的意思；其实最好的方式应该是 C++98 时就把 map 和 set 命名为 treemap 和 treeset。(注：Java 中就不存在这个问题，Java 中的 map 和 set 取名为 TreeMap 和 TreeSet，unordered_map 和 unordered_set 取名为 HashMap 和 HashSet，取名非常贴切)
1、unordered_map
unordered_map 的介绍
-
unordered_map 是存储 <key, value> 键值对的关联式容器，其允许通过 key 快速的索引到与其对应的value – 计算出余数找到下标位置。
-
在 unordered_map 中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
-
在内部, unordered_map 没有对 <kye, value> 按照任何特定的顺序排序, 为了能在常数范围内找到 key 所对应的 value， unordered_map 将相同哈希值的键值对放在相同的桶中 – 哈希冲突。
-
unordered_map 容器通过 key 访问单个元素要比 map 快，但它在遍历元素子集的范围迭代方面效率较低。
-
unordered_map 也重载了直接访问操作符 (operator[])，它允许使用 key 作为参数直接访问 value。
-
unordered_map 的迭代器是一个单向迭代器 – 哈希桶的结构是单链表。
总的来说，unordered_map 和 map 在功能上非常相似，都可以用来去重和查找，它们的不同点在于：
- map 的查询效率为 O(logN)，unordered_map 的查询效率为 O(1)；
- map 通过迭代器遍历得到的一个有序序列，而 unordered_map 遍历得到序列的元素顺序是不确定的；
- map 的底层结构为红黑树，unordered_map 的底层结构为开散列的哈希表；
- map 对 key 的要求是能够比较大小，unordered_map 对 key 的要求是能够转换为整形。
unordered_map 的接口介绍
unordered_map 接口的功能以及使用方法和 map 在大体上是相似，所以下面对于某些接口我不再详细解释，如何对细节有疑惑的老铁建议查阅官方文档 – unordered_map - C++ Reference (cplusplus.com)
构造
在学习了上一节的 哈希 之后，相信大家对于 unordered_map 的构造函数中的 Hash 和 Pred 就不会感到困惑了 – Hash 就是我们模拟实现中的仿函数 HashFunc，它用来将 key 转换为整形，从而使得 key 可以取模并成功映射，其中整形/指针类型和 string 类型的 HashFunc 是系统内置的，而其他自定义类型的 HashFunc 比如 People、Date 则需要我们自己提供仿函数并显式传递给 unordered_map；
而 Pred 则是我们模拟实现中的另一个仿函数 KeyOfT，它的作用是返回 key，之所以要设计它是因为哈希表同时也是 unordered_set 的底层容器，但 unordered_set 是 K模型的容器，而 unordered_map 是 KV模型的容器，而哈希表要能够兼容它们：
capacity
Iterator
可以看到，unordered_map 的迭代器是单向迭代器，这是因为 unordered_map 底层是开散列的哈希表，而开散列的哈希表的哈希桶的结构是单链表，单链表只支持 ++ ，不支持 --：(注意：并不是说哈希桶并一定是单链表，它也有可能是红黑树或其他结构，具体见上一节 哈希)
Element access
和 map 一样，unordered_map 的 operator[] 同时兼具插入、查找和修改的功能：
Element lookup
这里也一样，count 函数是因为 unordered_mulitmap 需要，这里为了统一：
Modifiers
Buckets
buckets 是 unordered_map 提供的与哈希桶相关的一系列函数，但是我们一般并不会使用这些接口：
Hash policy
我们在模拟实现哈希表的时候提到闭散列的哈希表一般在平衡因子达到 0.7 时就需要进行扩容，否则发生哈希冲突的概率太大，影响效率；而开散列的哈希表一般将平衡因子控制在 1，这样大部分元素只需要查找 0~2 次就能够找到；
unordered_map 也提供了一系列与 平衡因子相关的函数，其中 load_factor 是获取当前平衡因子，max_load_factor 是最大平衡因子，也就是什么时候扩容，需要注意的是 max_load_factor 中提供了两个函数，一个用于获取最大平衡因子，一个用于设置最大平衡因子，即用户可以通过 max_load_factor 函数根据自己的业务场景来设定最大平衡因子；其中 unordered_map 中的默认最大平衡因子也是 1：
2、unordered_multimap
和 multimap 和 map 的区别一样，unordered_multimap 和 unordered_map 的区别在于 unordered_multimap 中允许出现重复元素，所以 unordered_multimap 中 count 用来计算 哈希表 中同一 key 值的元素的数量比较方便，但 unordered_multimap 也因此不再支持 operator[] 运算符重载，其他的地方都差不多，对细节有疑惑的老铁建议查阅官方文档 – unordered_multimap - C++ Reference (cplusplus.com)
3、unordered_set
unordered_set 的介绍
unordered_set 和 unordered_map 的区别再于 unordered_set 是 K模型 的容器，而 unordered_map 是 KV模型 的容器，虽然二者底层都是开散列的哈希表，但是哈希表中每个节点的 data 的类型是不同的 – unordered_set 是单纯的 key，而 unordered_map 是 KV 构成的键值对，只是 哈希表 通过 KeyOfT 仿函数使得自己能够兼容 K模型 的 unordered_set 和 KV模型 的 unordered_map 而已。
unordered_set 和 unordered_map 的功能与要求基本一样：
- unordered_set 的查询效率为 O(1)；
- unordered_set 遍历得到序列的元素顺序是不确定的；
- unordered_set 的底层结构为开散列的哈希表；
- unordered_set 对 key 的要求是能够转换为整形。
与 unordered_map 为数不多的不同的地方在于，unordered_set 不需要修改 value，所以也就不支持 operator[] 函数；
unordered_set 的接口
unordered_set - C++ Reference (cplusplus.com)
构造
4、unordered_multiset
unordered_multiset 也一样，与 unordered_set 不同的地方在于其允许出现重复元素：unordered_set - C++ Reference (cplusplus.com)
二、哈希表的迭代器
和红黑树一样，哈希表也需要单独定义一个类来实现迭代器，不过由于哈希表的迭代器是单向的，所以我们不用实现 operator–()；其中，哈希表的 begin() 为第一个哈希桶中的第一个节点，即哈希表中第一个非空位置的数据，哈希表的 end() 这里我们定义为 nullptr；
哈希表迭代器实现的难点在于 operator++，哈希表的迭代器 ++ 分为两种情况：
- 当前哈希桶的下面还有节点，说明当前下标位置的哈希桶还没遍历完，此时迭代器 ++ 到当前哈希桶的下一个节点；
- 当前哈希桶的下面没有节点，即 cur->next == nullptr，说明当前下标位置的哈希桶已经遍历完了，此时迭代器 ++ 到哈希表的下一个非空位置，即下一个哈希桶；
因为我们需要访问哈希表的 _tables 数组来确定下一个哈希桶的位置，所以要在迭代器类中定义一个 HashTable 类型的指针变量，同时，由于 _tables 是 HashTable 类的私有成员，所以我们还需要将在 HashTable 类中将 __HashTableIterator 类声明为友元类，这样我们才能正确实现迭代器 ++ 的功能；
注意：
1、由于我们在迭代器类中增加了一个哈希表的指针变量 _ht，所以我们在 HashTabel 中定义 begin() 和 end() 时除了需要传递节点的指针来初始化 _node，还需要传递 this 指针来初始化 _ht。
2、由于迭代器类中要定义 HashTable 类型的指针变量，同时 HashTable 类中又要 typedef 迭代器类型作为迭代器，所以这里就存在相互引用的问题，为了解决这个问题，我们需要在迭代器类前面提前声明一下 HashTable 类。
代码实现如下：
//提前声明一下HashTable类，解决相互引用问题 template<class K, class T, class Hash, class KeyOfT> class HashTable; //哈希表的迭代器--普通迭代器 template<class K, class T, class Hash, class KeyOfT> struct __HashTableIterator { typedef HashNode<T> Node; typedef __HashTableIterator<K, T, Hash, KeyOfT> Self; typedef HashTable<K, T, Hash, KeyOfT> HT; Node* _node; HT* _ht; __HashTableIterator(Node* node, HT* ht) : _node(node) , _ht(ht) {} bool operator==(const Self& s) const { return _node == s._node; } bool operator!=(const Self& s) const { return _node != s._node; } T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } Self& operator++() { //如果当前桶下面还有节点，则++到下一个节点 if (_node->next) { _node = _node->next; return *this; } //如果当前桶下面没有节点，则++到下一桶 KeyOfT kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size(); //找下一个桶--哈希表中下一个非空位置 while (++hashi != _ht->_tables.size()) { if (_ht->_tables[hashi]) { _node = _ht->_tables[hashi]; return *this; } } //如果走到这里都还没找到，说明迭代器已经走到尾了 _node = nullptr; return *this; } Self& operator++(int) { Self tmp = *this; operator++(); return tmp; } }; //哈希表的迭代器--const迭代器 template<class K, class T, class Hash, class KeyOfT> struct __HashTableConstIterator { typedef HashNode<T> Node; typedef __HashTableConstIterator<K, T, Hash, KeyOfT> Self; typedef __HashTableIterator<K, T, Hash, KeyOfT> iterator; //普通迭代器 typedef HashTable<K, T, Hash, KeyOfT> HT; const Node* _node; const HT* _ht; __HashTableConstIterator(const Node* node, const HT* ht) : _node(node) , _ht(ht) {} //使用普通迭代器构造const迭代器 __HashTableConstIterator(const iterator& it) : _node(it._node) , _ht(it._ht) {} bool operator==(const Self& s) const { return _node == s._node; } bool operator!=(const Self& s) const { return _node != s._node; } const T& operator*() { return _node->_data; } const T* operator->() { return &_node->_data; } Self& operator++() { //如果当前桶下面还有节点，则++到下一个节点 if (_node->next) { _node = _node->next; return *this; } //如果当前桶下面没有节点，则++到下一桶 KeyOfT kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size(); //找下一个桶--哈希表中下一个非空位置 while (++hashi != _ht->_tables.size()) { if (_ht->_tables[hashi]) { _node = _ht->_tables[hashi]; return *this; } } //如果走到这里都还没找到，说明迭代器已经走到尾了 _node = nullptr; return *this; } Self& operator++(int) { Self tmp = *this; operator++(); return tmp; } }; //哈希表 template<class K, class T, class Hash, class KeyOfT> class HashTable { typedef HashNode<T> Node; //友元类--迭代器中要访问哈希表的_tables数组 friend __HashTableIterator<K, T, Hash, KeyOfT>; friend __HashTableConstIterator<K, T, Hash, KeyOfT>; public: //迭代器 typedef __HashTableIterator<K, T, Hash, KeyOfT> iterator; typedef __HashTableConstIterator<K, T, Hash, KeyOfT> const_iterator; iterator begin() { //哈希表中第一个非空位置即第一个桶的头为begin for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) return iterator(_tables[i], this); } return iterator(nullptr, this); } iterator end() { return iterator(nullptr, this); } const_iterator begin() const { //哈希表中第一个非空位置即第一个桶的头为begin for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) return const_iterator(_tables[i], this); } return const_iterator(nullptr, this); } const_iterator end() const { return const_iterator(nullptr, this); } private: vector<Node*> _tables; //指针数组 size_t _n; //表中有效数据的个数 }；
- 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
可以看到，在哈希表的迭代器中，我们并没有通过增加模板参数 Ref 和 Ptr 来解决 const 迭代器问题，而是为 const 迭代器单独定义了一个 __HashTableConstIterator 类；这是因为我们下面要使用哈希表来封装实现 unordered_map 和 unordered_set；
和前面 红黑树封装实现 map 和 set 一样，我们通过封装 哈希表 的普通迭代器来实现 unordered_map 的普通迭代器，封装哈希表的 const 迭代器来实现 unordered_map 的 const 迭代器；在 unordered_map 的 const 迭代器中，由于 _tables 是 vector 类型的变量，所以通过 _tables[] 访问得到的数据，即节点的指针都是 const 类型的：
同时，unordered_map 的 begin() 和 end() 都是直接调用哈希表类型的成员变量 _ht.begin() 和 _ht.end() 来得到；那么，在 HashTable 类中构造 begin() 和 end() 时传递给普通迭代器类构造函数的实参的 _node 和 _ht 的类型都是 const node* 和 const HT* 的，而普通迭代器里面定义构造函数的形参的 _node 和 _ht 的类型都是 node* 和 HT* 的，这里就是问题所在 – const 对象的实参不能赋值给普通对象的形参；
__HashTableIterator(Node* node, HT* ht)
: _node(node)
, _ht(ht)
{}
- 1
- 2
- 3
- 4
那么我们能不能重载一个形参为 const 类型的构造函数来实现构造 const 迭代器呢？如下：
__HashTableIterator(const Node* node, const HT* ht)
: _node(node)
, _ht(ht)
{}
- 1
- 2
- 3
- 4
这样其实也不行，因为普通迭代器类中定义的成员变量 _node 和 _ht 的类型始终是非 const 的，当我们重载一个形参为 const 类型的构造函数其实只是将矛盾从 const 实参赋值给普通形参转变成了使用 const 形参初始化普通变量。
所以，这里我们需要为 const 迭代器单独定义一个类，然后将类中的成员变量 _node 和 _ht 都定义为 const 类型，这样才能真正解决问题。
三、哈希表封装实现 unordered_map 和 unorderd_set
哈希表封装实现 unordered_map 和 unorderd_set 其实与 红黑树封装实现 map 和 set 遇到的问题是差不多的，所以下面某些地方我不再给出错误截图，而是直接解释原因；
注意点一
为了使哈希表能够同时封装 KV模型的 unordered_map 和 K模型的 unordered_set，哈希表不能将节点的数据类型直接定义为 pair<K, V>，而是需要通过参数 T 来确定；同时，由于 insert 函数在求余数时需要取出 T 中的 key 转化为整形，所以上层的 unordered_map 和 unordered_set 需要定义一个仿函数 MapKeyOfT 和 SetKeyOfT 来获取 key (主要是为了 unordered_map 而设计)；
//哈希表的节点结构--单链表 template<class T> struct HashNode { T _data; HashNode<T>* next; HashNode(const T& data) : _data(data) , next(nullptr) {} }; //unorde_set template<class K, class Hash = BucketHash::HashFunc<K>> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; private: BucketHash::HashTable<K, K, Hash, SetKeyOfT> _ht; }; //unordered_map template<class K, class V, class Hash = BucketHash::HashFunc<K>> class unordered_map { //map的仿函数 struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; private: BucketHash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht; };
- 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
注意点二
为了保证 unordered_set 的 key 值不被修改，我们需要使用 哈希表 的 const 迭代器来封装 unordered_set 的普通迭代器，但是这样会导致哈希表的普通迭代器赋值给 const 迭代器的问题，所以我们需要将 unordered_set 的 begin() 和 end() 函数都定义为 const 成员函数；
template<class K, class Hash = BucketHash::HashFunc<K>> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: //迭代器 typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator; typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator; iterator begin() const { return _ht.begin(); } iterator end() const { return _ht.end(); } private: BucketHash::HashTable<K, K, Hash, SetKeyOfT> _ht; };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
注意点三
因为 unordered_map 的 operator[]() 函数兼具插入、查找、和修改功能，所以如果我们要在模拟实现的 unordered_map 中重载 [] 运算符，就需要将 find 函数的返回值改为 iterator，将 insert 函数的返回值改为 pair<iterator, bool>，并且要改的话 哈希表、unordered_map、unordered_set 这三个地方都要改。
同时，unordered_set insert 函数的返回值变为 pair<iterator, bool> 后又会引发普通迭代器赋值给 const 迭代器的问题，所以对于 unordered_set 的 insert 函数，我们要先使用哈希表的普通迭代器构造的键值对去完成插入操作，然后再利用 普通迭代器来构造 const 迭代器进行返回；
而要用普通迭代器构造 const 迭代器，我们又需要在哈希表的 const 迭代器类中增加一个类似于拷贝构造的函数，来将普通迭代器构造为 const 迭代器进行返回；
//哈希表的迭代器--const迭代器 template<class K, class T, class Hash, class KeyOfT> struct __HashTableConstIterator { typedef HashNode<T> Node; typedef __HashTableConstIterator<K, T, Hash, KeyOfT> Self; typedef __HashTableIterator<K, T, Hash, KeyOfT> iterator; //普通迭代器 const Node* _node; const HT* _ht; //使用普通迭代器构造const迭代器 __HashTableConstIterator(const iterator& it) : _node(it._node) , _ht(it._ht) {} };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
代码实现如下：
//哈希表 template<class K, class T, class Hash, class KeyOfT> class HashTable { typedef HashNode<T> Node; public: //插入 pair<iterator, bool> insert(const T& data) { KeyOfT kot; iterator ret = find(kot(data)); if (ret != end()) return make_pair(ret, false); //扩容--当载荷因子达到1时我们进行扩容 //调用仿函数的匿名对象来将key转换为整数 size_t hashi = Hash()(kot(data)) % _tables.size(); //哈希桶头插 Node* newNode = new Node(data); newNode->next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return make_pair(iterator(newNode, this), true); } //查找 iterator find(const K& key) { KeyOfT kot; size_t hashi = Hash()(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return iterator(cur, this); cur = cur->next; } return iterator(nullptr, this); } private: vector<Node*> _tables; //指针数组 size_t _n; //表中有效数据的个数 }; //unordered_map template<class K, class V, class Hash = BucketHash::HashFunc<K>> class unordered_map { public: //迭代器 typedef typename BucketHash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator; typedef typename BucketHash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::const_iterator const_iterator; pair<iterator, bool> insert(const pair<const K, V>& kv) { return _ht.insert(kv); } iterator find(const K& key) { return _ht.find(key); } V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return ret.first->second; } private: BucketHash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht; }; //unordered_set //template<class K, class Hash = BucketHash::HashFunc<K>> class unordered_set { public: //迭代器 typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator; typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator; iterator begin() const { return _ht.begin(); } iterator end() const { return _ht.end(); } //使用普通迭代器构造const迭代器 pair<iterator, bool> insert(const K& key) { pair<typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::iterator, bool> p = _ht.insert(key); return pair<iterator, bool>(p.first, p.second); } pair<iterator, bool> find(const K& key) { return _ht.find(key); } private: BucketHash::HashTable<K, K, Hash, SetKeyOfT> _ht; };
- 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
四、模拟实现完整代码
1、HashTable.h
#pragma once #include <vector> #include <utility> #include <string> using std::pair; using std::vector; using std::string; //开散列 namespace BucketHash { //哈希表的节点结构--单链表 template<class T> struct HashNode { T _data; HashNode<T>* next; HashNode(const T& data) : _data(data) , next(nullptr) {} }; //哈希表的仿函数 template<class K> struct HashFunc { size_t operator()(const K& key) { return key; } }; //类模板特化 template<> struct HashFunc<string> { size_t operator()(const string& key) { //BKDR字符串哈希算法 size_t sum = 0; for (auto ch : key) sum = sum * 131 + ch; return sum; } }; //提前声明一下HashTable类，解决相互引用问题 template<class K, class T, class Hash, class KeyOfT> class HashTable; //哈希表的迭代器--普通迭代器 template<class K, class T, class Hash, class KeyOfT> struct __HashTableIterator { typedef HashNode<T> Node; typedef __HashTableIterator<K, T, Hash, KeyOfT> Self; typedef HashTable<K, T, Hash, KeyOfT> HT; Node* _node; HT* _ht; __HashTableIterator(Node* node, HT* ht) : _node(node) , _ht(ht) {} bool operator==(const Self& s) const { return _node == s._node; } bool operator!=(const Self& s) const { return _node != s._node; } T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } Self& operator++() { //如果当前桶下面还有节点，则++到下一个节点 if (_node->next) { _node = _node->next; return *this; } //如果当前桶下面没有节点，则++到下一桶 KeyOfT kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size(); //找下一个桶--哈希表中下一个非空位置 while (++hashi != _ht->_tables.size()) { if (_ht->_tables[hashi]) { _node = _ht->_tables[hashi]; return *this; } } //如果走到这里都还没找到，说明迭代器已经走到尾了 _node = nullptr; return *this; } Self& operator++(int) { Self tmp = *this; operator++(); return tmp; } }; //哈希表的迭代器--const迭代器 template<class K, class T, class Hash, class KeyOfT> struct __HashTableConstIterator { typedef HashNode<T> Node; typedef __HashTableConstIterator<K, T, Hash, KeyOfT> Self; typedef __HashTableIterator<K, T, Hash, KeyOfT> iterator; //普通迭代器 typedef HashTable<K, T, Hash, KeyOfT> HT; const Node* _node; const HT* _ht; __HashTableConstIterator(const Node* node, const HT* ht) : _node(node) , _ht(ht) {} //使用普通迭代器构造const迭代器 __HashTableConstIterator(const iterator& it) : _node(it._node) , _ht(it._ht) {} bool operator==(const Self& s) const { return _node == s._node; } bool operator!=(const Self& s) const { return _node != s._node; } const T& operator*() { return _node->_data; } const T* operator->() { return &_node->_data; } Self& operator++() { //如果当前桶下面还有节点，则++到下一个节点 if (_node->next) { _node = _node->next; return *this; } //如果当前桶下面没有节点，则++到下一桶 KeyOfT kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size(); //找下一个桶--哈希表中下一个非空位置 while (++hashi != _ht->_tables.size()) { if (_ht->_tables[hashi]) { _node = _ht->_tables[hashi]; return *this; } } //如果走到这里都还没找到，说明迭代器已经走到尾了 _node = nullptr; return *this; } Self& operator++(int) { Self tmp = *this; operator++(); return tmp; } }; //哈希表 template<class K, class T, class Hash, class KeyOfT> class HashTable { typedef HashNode<T> Node; //友元类--迭代器中要访问哈希表的_tables数组 friend __HashTableIterator<K, T, Hash, KeyOfT>; friend __HashTableConstIterator<K, T, Hash, KeyOfT>; public: //迭代器 typedef __HashTableIterator<K, T, Hash, KeyOfT> iterator; typedef __HashTableConstIterator<K, T, Hash, KeyOfT> const_iterator; iterator begin() { //哈希表中第一个非空位置即第一个桶的头为begin for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) return iterator(_tables[i], this); } return iterator(nullptr, this); } iterator end() { return iterator(nullptr, this); } const_iterator begin() const { //哈希表中第一个非空位置即第一个桶的头为begin for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) return const_iterator(_tables[i], this); } return const_iterator(nullptr, this); } const_iterator end() const { return const_iterator(nullptr, this); } //构造 HashTable() : _n(0) { _tables.resize(10, nullptr); } //析构--手动释放哈希表中的每个元素，以及每个元素指向的哈希桶 ~HashTable() { //释放每个元素的哈希桶 for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->next; delete cur; cur = next; } } //释放哈希表 _tables.clear(); } //插入 pair<iterator, bool> insert(const T& data) { KeyOfT kot; iterator ret = find(kot(data)); if (ret != end()) return make_pair(ret, false); //扩容--当载荷因子达到1时我们进行扩容 if (_n == _tables.size()) { //法一：采用闭散列的扩容方法--复用insert接口 //优点：实现简单； //缺点：先开辟节点再释放节点代价大 //HashTable<K, V, Hash> newHT; //newHT._tables.resize(_tables.size() * 2, nullptr); //for (size_t i = 0; i < _tables.size(); ++i) { // Node* cur = _tables[i]; // while (cur) { // newHT.insert(cur->_data); // cur = cur->next; // } //} //_tables.swap(newHT._tables); //法二：取原表中的节点链接到当前表中 //缺点：实现比较复杂 //优点：不用再去开辟新节点，也不用释放旧节点，消耗小 vector<Node*> newTables; newTables.resize(_tables.size() * 2, nullptr); for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->next; //重新计算映射关系--调用仿函数的匿名对象来将key转换为整数 size_t hashi = Hash()(kot(cur->_data)) % newTables.size(); cur->next = newTables[hashi]; newTables[hashi] = cur; cur = next; } } _tables.swap(newTables); newTables.clear(); //不写也可以，局部的vector变量出作用域自动调用析构 } //调用仿函数的匿名对象来将key转换为整数 size_t hashi = Hash()(kot(data)) % _tables.size(); //哈希桶头插 Node* newNode = new Node(data); newNode->next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return make_pair(iterator(newNode, this), true); } //查找 iterator find(const K& key) { KeyOfT kot; size_t hashi = Hash()(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return iterator(cur, this); cur = cur->next; } return iterator(nullptr, this); } //删除 bool erase(const K& key) { KeyOfT kot; //由于单链表中删除节点需要改变上一个节点的指向，所以这里不能find后直接erase size_t hashi = Hash()(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { //删除还要分是否为头结点 if (kot(cur->_data) == key) { if (cur == _tables[hashi]) _tables[hashi] = cur->next; else prev->next = cur->next; delete cur; --_n; return true; } //迭代 prev = cur; cur = cur->next; } return false; } private: vector<Node*> _tables; //指针数组 size_t _n; //表中有效数据的个数 }; }
- 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
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
2、unordered_map
#pragma once #include "HashTable.h" namespace thj { template<class K, class V, class Hash = BucketHash::HashFunc<K>> class unordered_map { //map的仿函数 struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: //迭代器 typedef typename BucketHash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator; typedef typename BucketHash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::const_iterator const_iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } const_iterator begin() const { return _ht.begin(); } const_iterator end() const { return _ht.end(); } pair<iterator, bool> insert(const pair<const K, V>& kv) { return _ht.insert(kv); } iterator find(const K& key) { return _ht.find(key); } bool erase(const K& key) { return _ht.erase(key); } V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return ret.first->second; } private: BucketHash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht; }; }
- 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
3、unordered_set
#pragma once #include "HashTable.h" namespace thj { template<class K, class Hash = BucketHash::HashFunc<K>> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: //迭代器 typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator; typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator; iterator begin() const { return _ht.begin(); } iterator end() const { return _ht.end(); } //使用普通迭代器构造const迭代器 pair<iterator, bool> insert(const K& key) { pair<typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::iterator, bool> p = _ht.insert(key); return pair<iterator, bool>(p.first, p.second); } pair<iterator, bool> find(const K& key) { return _ht.find(key); } bool erase(const K& key) { return _ht.erase(key); } private: BucketHash::HashTable<K, K, Hash, SetKeyOfT> _ht; }; }
- 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
4、test.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> using namespace std; #include "HashTable.h" #include "unordered_map.h" #include "unordered_set.h" void my_unordered_map_test1() { int arr[] = { 18, 8, 7, 27, 57, 3, 38, 23, 15, 22 }; thj::unordered_map<int, int> um; for (auto e : arr) um.insert(make_pair(e, e)); thj::unordered_map<int, int>::iterator it = um.begin(); while (it != um.end()) { cout << it->first << ":" << it->second << endl; ++it; } cout << endl; } void my_unordered_map_test2() { string arr[] = { "苹果", "西瓜", "芒果", "西瓜", "苹果", "梨子", "西瓜","苹果", "香蕉", "西瓜", "香蕉" }; thj::unordered_map<string, int> countMap; for (auto e : arr) countMap[e]++; auto it = countMap.begin(); for (auto& kv : countMap) { cout << kv.first << ":" << kv.second << endl; } cout << endl; } void my_unordered_set_test1() { int arr[] = { 18, 8, 7, 27, 57, 3, 38, 23, 15, 22 }; thj::unordered_set<int> us; for (auto e : arr) us.insert(e); thj::unordered_set<int>::iterator it = us.begin(); while (it != us.end()) { cout << *it << endl; ++it; } cout << endl; } int main() { //my_unordered_map_test1(); //my_unordered_map_test2(); my_unordered_set_test1(); return 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
