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

【C++】26：用哈希表封装unordered_set和unordered_map

news 2026/5/1 3:54:22

一、源码和框架分析

二、创建项目结构

三、模拟实现unordered_set和unordered_map

四、测试unordered_set中insert的实现

五、迭代器Iterator的实现

5.1 迭代器类的结构设计

5.2 HashTable中封装迭代器

5.3 unordered_set中封装迭代器

5.4 operator++的实现

5.5 前置声明问题和友元问题

5.6 unordered_set测试代码

5.7 unordered_map中封装迭代器

5.8 map测试代码

5.9 key修改的问题

六、operator[]的实现

6.1 HashTables中Insert和Find修改

6.2 myunordered_map修改insert和operator[]

七、代码

7.1 HashTable.h

7.2 myunordered_set.h

7.3 myunordered_map.h

7.4 test.cpp

一、源码和框架分析

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

// stl_hash_set
template<classValue,classHashFcn= hash<Value>,
classEqualKey = equal_to<Value>,
classAlloc = alloc>
classhash_set
{
private:
typedefhashtable<Value, Value, HashFcn, identity<Value>,
EqualKey, Alloc> ht;
ht rep;
public:
typedef typenameht::key_type key_type;
typedef typenameht::value_type value_type;
typedef typenameht::hasher hasher;
typedef typenameht::key_equal key_equal;
typedef typenameht::const_iterator iterator;
typedef typenameht::const_iterator const_iterator;
hasherhash_funct()const{returnrep.hash_funct(); }
key_equalkey_eq()const{returnrep.key_eq(); }
};
// stl_hash_map
template<classKey,classT,classHashFcn= hash<Key>,
classEqualKey = equal_to<Key>,
classAlloc = alloc>
classhash_map
{
private:
typedefhashtable<pair<constKey, T>, Key, HashFcn,
select1st<pair<constKey, T> >, EqualKey, Alloc> ht;
ht rep;
public:
typedef typenameht::key_type key_type;
typedefT data_type;
typedefT mapped_type;
typedef typenameht::value_type value_type;
typedef typenameht::hasher hasher;
typedef typenameht::key_equal key_equal;
typedef typenameht::iterator iterator;
typedef typenameht::const_iterator const_iterator;
};
// stl_hashtable.h
template<classValue,classKey,classHashFcn,
classExtractKey,classEqualKey,
classAlloc>
classhashtable{
public:
typedefKey key_type;
typedefValue value_type;
typedefHashFcn hasher;
typedefEqualKey key_equal;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef__hashtable_node<Value> node;
vector<node*,Alloc> buckets;
size_type num_elements;
public:
typedef__hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
Alloc> iterator;
pair<iterator,bool>insert_unique(constvalue_type& obj);
const_iteratorfind(constkey_type& key)const;
};
template<classValue>
struct__hashtable_node
{
__hashtable_node* next;
Value val;
};

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

二、创建项目结构

哈希表的实现

我们使用上文哈希表的实现中的链地址法作为实现unordered_set和unordered_map的底层结构，然后创建两个头文件myunordered_set和myunordered_map,将unordered_set和unordered_map的实现放到命名空间zx里面，用来区别库里面的unordered_set和unordered_map。如下所示：

三、模拟实现unordered_set和unordered_map

1:我们这里相比源码调整一下，key参数就用K，value参数就用V，HashTable中的数据类型，我们使用T。我们再unordered_set和unordered_map中创建一个HashTable的变量，如下所示：

2:我们由第二个模板参数来确认哈希表中的数据类型，但是再Hashtable中如何区别是K还是KV结构呢？所以我们要像封装set和map一样，再传入一个模板参数，获取K,如下所示：

3:然后修改HashTables里面的代码，如下所示：

#pragma once #include<iostream> #include<vector> #include<string> using namespace std; 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 size_t(key); } }; template<> struct HashFunc<string> { size_t operator()(const string& s) { size_t hash = 0; for (auto ele : s) { hash += ele; hash *= 131; } return hash; } }; template<class K, class T,class KeyofT, class Hash = HashFunc<K>> class HashTable { typedef HashNode<T> Node; public: HashTable() :_tables(__stl_next_prime(0)) , _n(0) { } ~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[i] = nullptr; } } inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes = 28; static const unsigned long __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } bool Insert(const T& data) { KeyofT kot; if (Find(kot(data))) { return false; } if (_n == _tables.size()) { //扩容 vector<Node*> newtable(__stl_next_prime(_tables.size() + 1)); Hash hash; for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { KeyofT kot; Node* next = cur->_next; size_t hash0 = hash(kot(cur->_data)) % newtable.size(); cur->_next = newtable[hash0]; newtable[hash0] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtable); } Hash hash; size_t hash0 = hash(kot(data)) % _tables.size(); Node* newnode = new Node(data); newnode->_next = _tables[hash0]; _tables[hash0] = newnode; _n++; return true; } Node* Find(const K& key) { Hash hash; KeyofT kot; size_t hash0 = hash(kot(key)) % _tables.size(); Node* cur = _tables[hash0]; while (cur) { if (kot(cur->_data) == key) { return cur; } cur = cur->_next; } return nullptr; } bool Erase(const K& key) { Hash hash; KeyofT kot; size_t hash0 = hash(kot(key)) % _tables.size(); Node* cur = _tables[hash0]; Node* prev = nullptr; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) { _tables[hash0] = cur->_next; } else { prev->_next = cur->_next; } delete cur; _n--; return true; } else { prev = cur; cur = cur->_next; } } return false; } private: vector<Node*> _tables; //指针数组 size_t _n; //记录存储的数据个数 };

四、测试unordered_set中insert的实现

unordered_set中insert的实现如下所示：

#pragma once #include"HashTable.h" namespace zx { template<class K> class unordered_set { struct SetKeyofT { const K& operator()(const K& key) { return key; } }; public: bool insert(const K& key) { return _ht.Insert(key); } private: HashTable<K, K,SetKeyofT> _ht; }; }

测试代码如下所示：

#include"myunordered_set.h" #include"myunordered_map.h" void test1() { zx::unordered_set<int> myset; int a[] = { 3,1,6,7,8,2,1,1,5,6,7,6 }; for (auto ele : a) { myset.insert(ele); } } int main() { test1(); return 0; }

运行代码之后程序没有崩溃，就说明没有问题。

五、迭代器Iterator的实现

iterator实现的大框架跟list的iterator思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为。

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

5.1 迭代器类的结构设计

begin()返回第一个桶中第一个节点指针构造的迭代器，这里end()返回迭代器可以用空表示。

代码如下所示：

template<class K,class T,class Ref,class Ptr,class KeyofT,class Hash> struct HashIterator { typedef HashNode<T> Node; typedef HashTable<K,T, KeyofT, Hash> HT; typedef HashIterator<K,T, Ref, Ptr KeyofT, Hash> Self; Node* _node; HT* _ht; HashIterator(Node* node,HT* ht) :_node(node) ,_ht(ht) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator==(const Self& s) { return _node == s._node; } bool operator!=(const Self& s) { return _node != s._node; } };

5.2 HashTable中封装迭代器

代码如下所示：

typedef HashIterator<K, T, T&, T*, KeyofT, Hash> Iterator; typedef HashIterator<K, T, const T&, const T*, KeyofT, Hash> ConstIterator; Iterator Begin() { if (_n == 0) { return End(); } for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur != nullptr) { return { cur,this}; } } return End(); } Iterator End() { return { nullptr,this }; } ConstIterator Begin() const { if (_n == 0) { return End(); } for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur != nullptr) { return { cur,this }; } } return End(); } ConstIterator End() const { return { nullptr,this }; }

5.3 unordered_set中封装迭代器

typedef typename HashTable<K, K, SetKeyofT>::Iterator iterator; typedef typename HashTable<K, K, SetKeyofT>::ConstIterator 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(); }

5.4 operator++的实现

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

Self& operator++() { if (_node->_next)//当前筒还没有空 { _node = _node->_next; } else { KeyofT kot; Hash hash; size_t hashi = hash(kot(_node->_data)) % (_ht->_tables.size()); ++hashi; while (hashi < _ht->_tables.size()) { _node = _ht->_tables[hashi]; if (_node != nullptr) { break; } ++hashi; } if (hashi == _ht->_tables.size()) { _node = nullptr; } } return *this; }

5.5 前置声明问题和友元问题

前置声明问题

我们在HashIterator中typedef了HashTable，在HashTable中typedef了HashIterator，但是HashIterator声明在HashTable的前面，就会导致类HashIterator找不到HashTable，所以需要在；类HashIterator前面增加一个HashTable的前置声明，如下所示：

template<class K, class T, class KeyofT, class Hash>
class HashTable;

友元问题

我们在HashIterator类中使用了HashTable的指针，但是HashTable中的_tables是私有的，我们在HashIterator类中是使用不了这个成员变量的，因此需要在HashTable类中增加一个友元声明，如下所示：

// 友元声明
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
friend struct HashIterator;

const指针问题

在const迭代器里面，HT的this是const类型的，所以传入到HashIterator中的参数是const类型的，所以我们需要在HT前面加上const。

5.6 unordered_set测试代码

#include"myunordered_set.h" #include"myunordered_map.h" void test1() { zx::unordered_set<int> myset; int a[] = { 31,1,62,73,8,22,1,11,5,65,7,6 }; for (auto ele : a) { myset.insert(ele); } zx::unordered_set<int>::iterator it = myset.begin(); while (it != myset.end()) { cout << *it << " "; ++it; } cout << endl; } int main() { test1(); return 0; }

运行结果如下所示：