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

C++ STL之哈希封装实现unordered_map/set

news 2025/9/1 12:03:21

一.核心源码分析

这里我们对unordered_map/set的实现讲解细节上不会像之前那么多，因为具体的操作已经在红黑树封装map/set中讲解过。不过这里我们需要重点看看源码中的参数以及迭代器的问题。

1.hash_set的头文件解析

stl的SGI中unordered_set是以hash_set的名字命名的，不过功能上没有什么差异

它的参数分别为：键(Value)，将非整型转为整型HashFcn，支持判断相等EqualKey，空间配置器Alloc。其实可以看到在这里的源码命名依旧十分混乱，我们只需要关注set和map本身存储的数据类型即可。

// stl_hash_set
template <class Value, class HashFcn = hash<Value>,
class EqualKey = equal_to<Value>,
class Alloc = alloc>
class hash_set
{ 
private:
typedef hashtable<Value, Value, HashFcn, identity<Value>,
EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::const_iterator iterator;
typedef typename ht::const_iterator const_iterator;
hasher hash_funct() const { return rep.hash_funct(); }
key_equal key_eq() const { return rep.key_eq(); }
};

2.hash_map的头文件解析

这里的参数类型和上面的hash_set没有什么不同。map我们都知道存储的是一个键值对的pair类型。

// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>,
class EqualKey = equal_to<Key>,
class Alloc = alloc>
class hash_map
{ 
private:
typedef hashtable<pair<const Key, T>, Key, HashFcn,
select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef T data_type;
typedef T mapped_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::iterator iterator;
typedef typename ht::const_iterator const_iterator;
}

3.HashTable的头文件解析

和之前讲红黑树封装实现map/set一样，为了实现泛型编程的目的——用一份HashTable同时支持实现unordered_set/map。我们可以看结点类hashtable_node，存储一个hashtable_node的指针，以及数据val，val既可能是set的键类型，也可能是map的pair类型。

// stl_hashtable.h
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,
class Alloc>
class hashtable {
public:
typedef Key key_type;
typedef Value value_type;
typedef HashFcn hasher;
typedef EqualKey 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(const value_type& obj);
const_iterator find(const key_type& key) const;
}template <class Value>
struct __hashtable_node
{
__hashtable_node* next;
Value val;
};

二.unordered_set/map实现

1.HashTable的迭代器

之前我们写的HashTable，构造，析构，拷贝和迭代器还没有解决，这里重点讲解这些知识。

先来说迭代器。

这个迭代器的思路也比较简单，先讲最重要的operator++的逻辑。如果当前结点所在的桶还有下一个结点，就继续遍历

if (_node->_next)
{_node = _node->_next;
}

当前桶已遍历完，取到当前桶的hashi，从++hashi开始找不为空的桶

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)break;  // 找到非空桶else++hashi; // 继续查找下一个桶
}

如果把所有桶都遍历完，就指向迭代器的end位置(nullptr)

if (hashi == _ht->_tables.size())
{_node = nullptr;
}

完整的operator++的代码

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)break;else++hashi;}// 所有桶都走完了，end()给的空标识的_nodeif (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;
}

那么begin位置和end位置迭代器的逻辑也很容易能得出：

//begin就是找到第一个不为空的桶
Iterator Begin()
{if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){    //从哈希表的0位置开始找Node* cur = _tables[i];//不为空的桶if (cur){return Iterator(cur, this);}}return End();
}//end位置就是一个nullptr
Iterator End()
{return Iterator(nullptr, this);
}

完整的迭代器：需要注意的一点是这里我们加上了HashTable的前置声明，因为迭代器中需要它的哈希表指针，如果不加前置声明编译器不认识HashTable是什么。

// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
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){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}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)break;else++hashi;}// 所有桶都走完了，end()给的空标识的_nodeif (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};

2.对HashTable的处理

这里的处理其实就跟对RBTree的处理一样了。无非就是把该支持的仿函数加上，然后支持泛型即可。析构函数的逻辑就是一个桶一个桶，一个一个结点释放的。

template<class K, class T, class KeyOfT, class Hash>
class HashTable
{// 友元声明template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct HTIterator;typedef HashNode<T> Node;
public:typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;typedef HTIterator<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){return Iterator(cur, this);}}return End();}Iterator End(){return Iterator(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){return ConstIterator(cur, this);}}return End();}ConstIterator End() const{return ConstIterator(nullptr, this);}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;}}pair<Iterator, bool> Insert(const T& data){KeyOfT kot;Iterator it = Find(kot(data));if (it != End())return { it, false};Hash hash;// 负载因子 == 1时扩容if (_n == _tables.size()){/*HashTable<K, V> newht;newht._tables.resize(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){newht.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newht._tables);*/vector<Node*> newTable(__stl_next_prime(_tables.size()+1));for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 头插到新表size_t hashi = hash(kot(cur->_data)) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTable);}size_t hashi = hash(kot(data)) % _tables.size();// 头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return { Iterator(newnode, this), false };}Iterator Find(const K& key){KeyOfT kot;Hash hash;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 End();}bool Erase(const K& key){KeyOfT kot;size_t hashi = 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;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}
private:vector<Node*> _tables; // 指针数组size_t _n = 0;		   // 表中存储数据个数//struct Data//{//	ListNode* _head;//	RBTreeNode* _root;//	size_t _len;  // <= 8 存链表，>8 存红黑树 //};//vector<Data> _tables;//size_t _n = 0;		   // 表中存储数据个数//struct Data//{//	list<pair<K, V>> _list;//	map<K, V> _map;//	size_t _len;  // <= 8 存链表，>8 存红黑树 //};//vector<Data> _tables;//size_t _n = 0;		   // 表中存储数据个数
};

3.unordered_set实现

#pragma once#include"HashTable.h"namespace bit
{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;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 K& key){return _ht.Insert(key);}iterator Find(const K& key){return _ht.Find(key);}bool Erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};

4.unordered_map实现

注意这里unordered_map的逻辑也是复用了Insert的逻辑，具体了解可以移步红黑树封装实现map/set。

#pragma once#include"HashTable.h"// MyUnorderedMap.h
namespace bit
{template<class K, class V, class Hash = HashFunc<K>>class unordered_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;iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin() const{return _ht.Begin();}const_iterator end() const{return _ht.End();}V& operator[](const K& key){pair<iterator, bool> ret = insert({ key, V() });return ret.first->second;}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);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};

http://www.xdnf.cn/news/1414189.html

相关文章：

  • 第4章从一条记录说起-InnoDB记录结构
  • Redis六大常见命令详解：从set/get到过期策略的全方位解析
  • 如何用熵正则化控制注意力分数的分布
  • 【CVTE】C++开发 （提前批一面）
  • 【AI智能体】Dify 实现自然语言转SQL操作数据库实战详解
  • 【Spring】ApplicationListener监听器
  • 【芯片测试篇】：LIN总线
  • AI 赋能 Java 开发效率：全流程痛点解决与实践案例（一）
  • Linux/UNIX系统编程手册笔记：用户和组、进程凭证、时间以及系统限制和选项
  • 利用DeepSeek编写验证xlsx格式文件中是否启用sharedStrings.xml对读写效率影响python程序
  • DRF快速构建RESTful API指南
  • redis详解 (最开始写博客是写redis 纪念日在写一篇redis)
  • C++内存序不迷茫：从CPU缓存一致性理解Memory Order
  • Wi-Fi技术——初识
  • 如何绕过 disable-devtool.js 打开控制台
  • C语言中如何使用NULL
  • 配置 Kubernetes Master 节点不可调度的标准方法
  • stm32F4挂载emmc以及重定义printf
  • ThinkPHP8学习篇(五)：数据库(一)
  • 洛谷p2392kkksc03考前临时抱佛脚 详解（回溯，深度搜索法）
  • Redis常见数据类型及应用场景
  • java 安装流程配置
  • 金仓数据库KingbaseES：中国自主原创的数据库领军者
  • 【四位加密】2022-10-25
  • GDPU操作系统实验：生产者消费者问题
  • 【读数笔记】《你的生存本能正在杀死你》
  • 经典卷积神经网络CNN
  • sublime MAC系统快捷键及常见问题
  • Qwen2.5-VL代码初步解读
  • 恒香全新旗舰店开幕 新店传承百年文化