C++哈希表终极封装指南：从线性探测到STL兼容的迭代器魔法
- 一. 哈希表的封装
- 1.1 基本结构
- 1.1.1 插入
- 1.1.2 查找
- 1.1.3 删除
- 1.1.4 Begin()
- 1.1.5 End()
- 1.1.6 构造函数
- 1.1.7 析构函数
- 1.2 迭代器设计（重点）
- 1.2.1 重载operator*()
- 1.2.2 重载operator->()
- 1.2.3 重载operator++()
- 1.2.4 重载operator==()
- 1.2.5 重载operator==()
- 1.3 封装 unordered_set
- 1.3.1 基本结构
- 1.4 封装unordered_map
- 1.4.1 基本结构
- 二. 最后
声明：最好在学习了红黑树的封装之后，再来学习哈希表的封装，这里涉及的模版（泛型编程思想）较多，综合较强，两个模块之间相互依赖，需要前置声明。
源码位置：哈希表的封装- Gitee
一. 哈希表的封装
1.1 基本结构
- 使用哈希桶结构封装出哈希表
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{typedef HashNode<T> Node;
public:
private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 表中存储数据个数
};
使用vector容器来存储节点指针，进行线性探测可以挂在后面。
- KeyOfT的作用是返回key值，因为对于set而言是key值，而对于map而言是pair类型。
- Hash作用是将不支持取模类型的数据转换成整数，如string等类型不支持。
1.1.1 插入
查找数据之前，查找该数据是否已经存在，存在则直接返回{该节点已经存在的迭代器，false}，不存在则返回{新插入节点的迭代器，true}，然后计算出该新插入数据节点的哈希值，然后直接头插即可（注：尾插也行，但麻烦，需要找尾），然后返回{当前新插入节点的迭代器，true}即可，将_n++,表示实际存储的数据个数增加了。
- 伪代码如下：
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;
}pair<Iterator, bool> Insert(const T& data)
{KeyOfT kot;Iterator it = Find(kot(data));if (it != End())return { it,false };Hash hs;// 扩容逻辑size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);// 头插到桶里面newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return { Iterator(newnode,this),true };
}
问题1：如果插入的数据，当前空间已经满了？？？怎么办，需要扩容。
- 扩容：
将原哈希表的数据挪动至新表中，然后将旧表与新表交换即可，伪代码：
if (_n == _tables.size())
{size_t newSize = __stl_next_prime(_tables.size() + 1);vector<Node*> newtables(newSize, nullptr);// 遍历旧表，把旧表的节点挪动到新表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// cur头插到新表size_t hashi = hs(kot(cur->_data)) % newSize;cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);
}
1.1.2 查找
将要查找的数据转换成哈希值，然后在当前桶中遍历即可。找到返回当前节点的迭代器即可。未找到返回End()。
Iterator Find(const K& key)
{Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];KeyOfT kot;while (cur){if (kot(cur->_data) == key){return Iterator(cur,this);}cur = cur->_next;}return End();
}
1.1.3 删除
这里直接附上代码即可，在上篇文章已经说过细节：哈希表模拟实现 - CSDN详情看这篇文章。
bool Erase(const K& key)
{Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){// 删除if (prev == nullptr){// 头删_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;
}
1.1.4 Begin()
查找第一个不为空的桶，返回当前节点指针和表指针。都为空则返回nullptr即可。
Iterator Begin()
{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return Iterator(cur, this);}}return End();
}
1.1.5 End()
返回使用{nullptr，表指针}即可。
Iterator End()
{return Iterator(nullptr, this);
}
const迭代器与上述类似。详情看源码即可。
1.1.6 构造函数
将当前容量默认设置为素数表第一个素数即可。
HashTable()
{_tables.resize(__stl_next_prime(1), nullptr);
}
1.1.7 析构函数
依次把当前桶桶中的节点指针析构即可，注意：析构当前节点时，需保存下一个节点指针的地址，未提前保存否则会找不到。
~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;}
}
1.2 迭代器设计（重点）
迭代器里面重要的成员：
- 节点指针：用于遍历当前桶的。
- 表指针：用于查找下一个不为空的表。
struct __HTIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HTIterator<K, T, Ref,Ptr,KeyOfT, Hash> Self;Node* _node;//节点指针const HT* _ht;//表指针__HTIterator(Node* node,const HT* ht): _node(node),_ht(ht){}
}
问题1：这里表指针为啥要const修饰？？？
为了配合const的迭代器，const的迭代器修饰表指针，不用设计权限放大，这是不允许的。
1.2.1 重载operator*()
typedef __HTIterator<K, T, T&,T*,KeyOfT, Hash> Iterator;
typedef __HTIterator<K, T, const T&,const T*,KeyOfT, Hash> ConstIterator;
template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash>
struct __HTIterator ；
直接取节点中的数据即可。
Ref operator*()
{return _node->_data;
}
1.2.2 重载operator->()
返回节点中数据的地址即可。
Ptr operator->()
{return &_node->_data;
}
1.2.3 重载operator++()
- 当前桶中节点未走完，则需要继续往当前桶中继续往后走。
- 当前桶中的节点已经为空，表示已经遍历完了，则需要找下一个不为空的桶。
问题1：如何找下一个不为空的桶？？？ - 将当前节点的数据转换成哈希值，然后将该哈希值++，继续判断，如果当前桶中的节点不为空，则将该节点赋值给_node，如果为空，继续将哈希值++，继续往后查找。
Self operator++()
{if (_node->_next){_node = _node->_next;}else{//当前桶中的链表数据已经遍历完，寻找下一个有数据的桶KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();++hashi;//当前的下一个位置while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{++hashi;}}if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;
}
1.2.4 重载operator==()
直接判断节点相等即可。
bool operator==(const Self& s)
{return _node == s._node;
}
1.2.5 重载operator==()
直接判断节点是否相等即可。
bool operator!=(const Self& s)
{return _node != s._node;
}
1.3 封装 unordered_set
1.3.1 基本结构
template<class K, class Hash = HashFunc<K>>
class unordered_set
{//仿函数struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public:typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;
private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
- 基本都是调用哈希桶中哈希表中的接口。
iterator begin()
{return _ht.Begin();
}
iterator end()
{return _ht.End();
}const_iterator begin()const
{return _ht.Begin();
}
const_iterator end()const
{return _ht.End();
}iterator Find(const K& key)
{return _ht.Find(key);
}
bool Erase(const K& key)
{return _ht.Erase(key);
}pair<iterator, bool> insert(const K& key)
{return _ht.Insert(key);
}
该代码实现了一个STL风格容器适配器，封装底层哈希表的核心功能：1) 提供const/non-const迭代器接口，支持范围遍历；2) insert方法返回插入状态对(迭代器+成功标识)，兼容关联容器规范；3) Find/Erase实现键值查询与删除操作；4) 通过组合模式复用底层实现，提供类型安全的键值存储接口。整体设计遵循STL容器规范，支持迭代器遍历和标准操作接口，实现高效的键值对管理。
1.4 封装unordered_map
1.4.1 基本结构
template<class K, class V, class Hash>
class unoredred_map
{//仿函数struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;
private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
- 基本都是调用哈希桶中哈希表中的接口。
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<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 = _ht.Insert(make_pair(key, V()));return ret.first->second;
}
该代码实现了一个容器适配器，封装了底层哈希表_ht的核心接口：1) 提供迭代器支持(begin/end)，支持范围遍历；2) insert方法返回插入状态对(迭代器+成功标识)；3) Find/Erase实现键值查找与删除；4) 重载operator[]实现类似map的便捷访问——若键不存在则自动插入默认值。整体设计遵循STL容器风格，通过组合模式复用底层哈希表功能，提供类型安全的键值存储与高效操作接口。
二. 最后
本文详细阐述了C++哈希表容器的封装实现，采用vector存储指针数组处理冲突，通过线性探测法解决哈希碰撞，并设计素数表实现动态扩容。核心模块包括：1) 哈希表基类：实现插入(含自动扩容)、查找、删除等操作，提供迭代器接口；2) 迭代器设计：支持跨桶遍历，通过哈希值跳跃实现高效遍历；3) 无序容器适配：通过组合模式封装哈希表，实现unordered_set/unordered_map容器，提供STL标准接口(begin/end/insert/find/erase)，其中unordered_map重载operator[]实现自动值初始化。整体设计遵循RAII原则，内存管理安全，完美兼容STL生态体系。
![[MongoDB] 认识MongoDB以及在Windows和Linux上安装MongoDB](https://i-blog.csdnimg.cn/direct/ceb3148ae94c4f34835d576f94f662d3.png)
